Wataru

> а почему тут работает ОТТ, если оно доказывается с помощью теоремы Пифагора?

От того, в каком порядке вы применяете доказанные теоремы, их истинность не меняется. ОТТ - доказано для любого значения угла. Все, независимо от того, в треугольнике ли вы чего-то считаете или матрицу поворота плоскости на заданный угол, или считаете площадь вашего куска пирога.

ОТТ применимо всегда! Для любых аргументов. Но, возможно вас именно это и запутало, после применения ОТТ и взятия корня, по идее, у вас получится +-sqrt(...). Потому что x^2=9 => x=3 или -3. Два варианта извлечения корня, 2 варианта для синуса.

Но, поскольку вы знаете, что угол в треугольнике не может превышать 180 градусов, вы знаете, что синус этого угла всегда неотрицательный. Поэтому -sqrt() можно отбросить как лишнее значение и получить вашу формулу. В формальном доказательстве эти рассуждения надо учитывать.

Как я уже писал в другом вопросе - вам не нужны касательные из каждой точки на все полигоны. Нужны лишь общие касательные к каждой паре полигонов. Если полигоны не пересекаются, то таких всего 4 штуки. Если же они пересекаются, то их может быть сколько угодно.

Как-то сильно ускорить мне не удалось, но можно брать каждую точку одного полигона, строить 2 касательные на другой полигон и оставлять только те, которые одновременно являются касательными к первому полигону.
Это проверяется через векторные произведения веторов-сторон и вектора отрезка между полигонами. Отрезок между полигонами должен быть между двумя векторами сторон (если они ориентированны в одну сторону, скажем, против часовой стрелки). Это должно уже в почти в 4 раза уменьшить количество отрезков у вас.

Еще, возможно, тут проблема не в касательных. Вот у вас 20 полигонов, в каждом по 8 точек - это 160 точек начал. Для нахождения касательных к полигону можно перебрать все вершины. Это еще раз по 20*8=160. Итого, получается 160^2=25600 операций. Операции сложные (найти 3 вектора, взять векторные произведения), да. Но жаже если умножить это на 50, получается 1,280,000 элементарных операций. Современные процессоры выполняют миллиарды таких операций в секунду. Т.е по этой грубой прикидке - построение всех касательных занимает считанные миллисекунды.

У вас очень тормозит проверка на пересечения возможных кандидатов с полигонами.
Во-первых, как только вы нашли пересечение - можно дальше не проверять. Разделите циклы по intersect_any_1 и intersect_any_2 и останавливайтесь, как только нашли пересечение. Во-вторых, вы для каждой касательной заново строите объекты turf.js. Это, возможно, очень медленно.

Ну и, похоже turf.js слишком тормозной. Моя демка на C++ для 100 полигонов находит все хорошие касательные без пересечений за 30мс. А если отсекать полигоны по bounding box, то 16-20мс. Ну в 10 раз javascript медленнее. У вас явно что-то совсем не то делается где-то.

Логика у вас правильная - взять середину отрезка AB и отложить от него перпендикуляр длинной sqrt(3)/2*d.

Но не надо искать углы, вектор перпендикуляр находится тривиально - это {y2-y1, x1-x2} (Можно доказать перпендикулярность через скалярное произведение, например). Более того, длина этого вектора будет уже d (это ведь повернутый на 90 градусов вектор по стороне треугольника). Значит его остается тупо домножить на sqrt(3)/2.

Таким образом формула x3 = (x1+x2)/2 +sqrt(3)/2*(y2-y1).

векторная формула: A + (B-A)/sqrt(|A-B|)*3

В числах
x = Ax+(Bx-Ax)*3/sqrt((Ax-Bx)^2+(Ay-By)^2)
y = Ay+(By-Ay)*3/sqrt((Ax-Bx)^2+(Ay-By)^2)

Похожую задачу решает GPS (если забить на всякие физические эффекты).

У вас будет 3 переменные - координаты источника сигнала (x, y) и время отправки сигнала (t).
Вам даны координаты трех точек (x_i, y_i, i=0..2), три времени получения сигнала (t_1, t_2, t_3) и скорость сигнала (v).

Время переведите в секунды относительно минимального из трех времен (вам ведь только относительные задержки нужны), чтобы числа не были слишком большими. Т.е. минимальное из трех времен будет 0, а два остальных - разницей с этим временем.

Уравнения, что сигнал проходит заданное расстояние за заданное время с известной скоростью:

(x_i-x)^2+(y_i-y)^2 = ((t-t_i)*v)^2

Можно время считать не в секундах, а в 1/v, тогда уравнения чуть упрощаются (коэффициент перед t^2 везде 1, а не v^2).

Можно решать аналитически. Вычтите первое уравнение из двух остальных. У вас получится 2 линейных уравнения с тремя неизвестными x, y, t. Считайте, что t - это константа и решите уравнения относительно x и y (Через определители, или метод Краммера). У вас будет какая-то линейная зависимость x и у от t (большие формулы, да). Можно упростить вычисления, если cначала записать уравнения в виде A1x+B1y=C1+D1t.

Потом подставьте эти зависимости в первое уравнение и у вас будет квадратичное уравнение на t.

Решите его. Подставьте t в известные уравнения для x и y - и вот ваш центр (заодно вы знаете, когда был отравлен сигнал).

Из двух значений t, одно будет в будущем (положительное), его надо будет отбросить.

Получите 2 вектора вдоль этих прямых (если прямые заданы параметрически - вы их уже знаете, если Ax+By+C=0, то это {-B,A}). Теперь угол между двумя векторами a и b - ваш искомый угол. Тут надо вспомнить, что векторное произведение - это |a|*|b|*sin x, а скалярное - |a|*|b|*cos x. Теперь вы знаете sin и cos искомого угла (поделив скалярное/векторное произведение на длины векторов). Можно скормить эти значения atan или еще какой-то обратной тригонометрической функции. Но на практике сам угол редко нужен, нужны в вычеслениях его sin и cos, а их вы уже знаете.

Ваш алгоритм надо лишь немного доработать.

1) найти ближайший сверху (слева/снизу/справа) из тех, которые имеют перекрытие.
2) повторить операцию, найдя следующий сверху. Расстояние между ними взять за d.
3) продолжить идти вверх. Если следующий ближайший тоже на расстоянии d - нарисовать промежуток. Если нет, то остановится.
4) Зная ближайший прямоугольник из пункта 1) и расстояние d - можно его отступить вниз и у вас есть точка примагничивания.

Можно ускорить алгоритм немного. Сначала за один проход выделите все прямоугольники, которые выше данного, но пересекаются с ним по оси X. Отсортируйте их снизу вверх по нижней границе. Теперь в пунктах 1,2,3 надо рассматривать только один следующий прямоугольник из списка.

Если есть пересечения то можно или выбрасывать прямоугольники, пересекающиеся с текущим, или остановится, как будто следующего прямоугольника нет.

Что бы ускорить еще больше, когда у вас очень много прямоугольников на экране, можно хранить их в quad tree и из него вытаскивать прямоугольники, которые перекрываются с заданным и выше его уже в правильном порядке. Но скорее всего просто пройтись по списку всех прямоугольников будет достаточно.