Wataru

Возьмите центр вписанной (и описанной) окружности. Разделите каждую сторону на 3 равные части. Проведите отрезки из центра во все 5 вершин и 10 точек на сторонах. Вы получите 15 треугольников, с одинаковыми внешними сторонами (1/3 стороны пятиугольника). Еще у всех этих треугольников одинаковые высоты (радиус вписанной окружности). Поэтому они все одинаковой площади. Теперь разбейте их на 3 группы по 5 подряд идущих треугольников - вот и ваши 3 равные по площади куска пятиугольника.

Это работает не только для правильных пятиугольников - достаточно чтобы можно было вписать окружность в многоугольник. После чего проведите отрезки из центра вписанной окружности на границу так, чтобы длины периметров получившихся частей были одинаковыми. Площади будут равны длинам периметра * радиус окружности пополам.

Вот описание алгоритма пересечения двух окружностей.
Стройте 2 окружности и пересекаете по этим формулам. У вас будет 2 точки. Проверьте, какая из них лежит на третьей окружности - это и будет искомый ответ.

Аккуратно с крайними случаями - три центра окружностей не должны лежать на одной и той же прямой, иначе вы не сможете понять, какая из двух точек вам нужна.

Похоже автор напутал. Слышал где-то про логарифмический алгоритм, знает, что за логарифм обычно работают сбалансированные бинарные деревья, вот и связал это воедино.

В случае с трассировкой лучей, за логарифм нет реализации вообще - ибо у невыпуклого многоугольника может быть O(n) пересечений с лучем (представьте себе пилу).

В случае с ближайшей точкой - если и есть структура, то это то-то вроде trapezoidal map - это такая мозговыносящая штука, что не советую о ней даже думать. Нужно разбить пространство на области, ближайшие к каждой стороне.

За логарифм есть решение через бинарный поиск.
Разбейте пространство на вертикальные колонны всеми x координатами всех вершин многоугольника. Внутри каждой из них будет проходить четное количество сторон. Составьте для каждой стороны уравнение и отсортируйте их по высоте.

При запросе, сначала бинпоиском найдите, в какой колонне лежит точка. Потом еще одним бинпоиском найдите, между какими из двух прямых лежит точка. Тут сравнения будут уже непросто чисел, а надо будет подставлять точку в уравнения прямых и смотреть, лежит ли точка выше или ниже. Если точка лежит так, что выше ее (и ниже) нечетное количество прямых - то точка внутри.

Проблема этого метода, что он требует O(n^2) памяти в худшем случае и такую же предобработку.
Но, для выпуклых многоугольников, прямых в каждой колонне будет всего две. Вот описание метода с реализацией для этого упрощенного случая.

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

Составьте 6 уравнений сторон шестиугольника в виде Ax+By+C=0, так что C положительно (если нет - домножте на -1). Подставьте в эти 6 уравнений координаты точки, все они должны дать положительные значения (или нули, если точка на границе считается лежащей внутри в вашей задаче).

Почему это работает? Мы просто проверяем, что точка лежит с той же стороны от всех 6 прямых, что и центр (0, 0).

Как составить уравнения? Найдите координаты 6-ти углов. Если сторона = a, то координаты точек (a, 0), (a/2, sqrt(3)*a/2), (-a/2, sqrt(3)*a/2), (-a, 0) ...

Для уравнения одной из сторон возьмите в виде A разность по у у соседних точек, а в виде B разность по x (но с другим знаком). Потом подставьте туда координаты одной из точек и возьмите C так, чтобы был 0.

Можно все 6 уравнений составить на бумажке и закодировать в программе.

Пример для первой стороны:
A = sqrt(3)*a/2-0 = sqrt(3)*a/2
B = a - a/2 = a/2
C = -A*a - B*0 = -sqrt(3)*a*a/2.

Поскольку C отрицательно, меняем знаки:
A = -sqrt(3)*a/2
B = -a/2
C = sqrt(3)*a*a/2

Для второй прямой будет 0*x-a*y+sqrt(3)*a*a/2 = 0

И да, это работает, если предположить, что шестиугольник маленький или на плоскости. если у вас кривизна земли играет роль, то все сильно усложняется.

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

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

ОТТ применимо всегда! Для любых аргументов. Но, возможно вас именно это и запутало, после применения ОТТ и взятия корня, по идее, у вас получится +-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 и из него вытаскивать прямоугольники, которые перекрываются с заданным и выше его уже в правильном порядке. Но скорее всего просто пройтись по списку всех прямоугольников будет достаточно.