Как определить, когда две движущиеся точки становятся видны друг другу?

Хорошо, теперь у меня есть более четкое представление о проблеме, и, вдохновленный предложением @walkytalky, вот более подробный ответ.

Вы упомянули, что p1 и p2 перемещаются по отрезкам прямой. Я не знаю, выровнены ли эти сегменты таким образом, что p1 и p2 всегда начинают новые сегменты одновременно. Однако вы всегда можете разрезать отрезок на два отрезка (с одинаковым наклоном), чтобы p1 и p2 всегда начинали новые отрезки одновременно.

Предположим, что p1 движется по линии A-B, а p2 движется (одновременно) по C-D, поскольку параметр t изменяется от 0 до 1. (То есть в момент времени t=0.5 p1 находится в середине A-B, а p2 в середине C-D. .)

Позволив Ax и Ay обозначать координаты x и y точки A (и аналогично для B, C и D), мы можем выразить p1 и p2 как функции t следующим образом:

p1(t) = (Ax + t*(Bx - Ax), Ay + t(By - Ay))
p2(t) = (Cx + t*(Dx - Cx), Cy + t(Dy - Cy))

(Например, когда t=0, Ax + t*(Bx - Ax) оценивается как Ax, а когда t=1 оценивается как Bx.)

Чтобы найти каждую «вершину-проходит-между-p1-и-p2»-время, мы делаем следующее:

Для каждой вершины препятствия v=(Vx, Vy) нам нужно найти t так, чтобы p1(t), p2(t) и v находились на одной линии друг с другом.

Это можно сделать, решив следующие уравнения (два уравнения и два неизвестных, t и k):

Vx=p1(t).x + k*(p2(t).x - p1(t).x)
Vy=p1(t).y + k*(p2(t).y - p1(t).y)`

Если k лежит между 0 и 1, вершина многоугольника v на самом деле между (расширенной) линией A-B и (расширенной) линией C-D. Если t также находится между 0 и 1, то вершина v фактически проходит линию p1-p2 за время прохождения точек по этим отрезкам (поскольку, когда t будет, скажем, 1,3, точки уже будут на новых отрезках).

После того, как все времена «вершина-проходит-между-p1-и-p2» были вычислены, вычислить остальное несложно. (То есть выяснение, является ли это типом прохождения «попадание в поле зрения», «становление вне поля зрения» или «ни то, ни другое»):

Для всех пар t0 и t1 последовательных моментов прохождения вершин вы проверяете, свободна ли линия p1((t1-t0)/2)-p2((t1-t0)/2) от пересечений с ребром полигона. Если он свободен от пересечений, то точки будут находиться на прямой видимости весь период (t0-t1), в противном случае они будут вне поля зрения весь период (поскольку никакие другие вершины не пройдены за этот период времени).

Легко проверить, пересекаются ли две линии. Используйте это, чтобы проверить пересечение линии (p1, p2) и каждого ребра полигона. Если у вас есть какое-либо пересечение, линия (p1, p2) перекрывается каким-то препятствием.

Если вам нужен временной интервал (в котором p1 и p2 не находятся на прямой видимости), вы можете выполнить вышеуказанную проверку для разных значений t (желательно с относительно небольшими различиями) и между «видимым-t» и «невидимым -t" вы можете выполнять бинарный поиск, пока не достигнете достаточно малого порога, например, eps.

Изменения видимости могут происходить только тогда, когда вершина препятствия лежит на отрезке линии Point1-Point2. Итак, подсчитайте время всех таких столкновений вершин. (Интуитивно это должен быть относительно простой тест, поскольку конечные точки перемещаются линейно, но мне нужно будет на самом деле проработать его, чтобы проверить. Я попробую позже и вернусь.)

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

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

Обновить

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

Рассмотрим только один период времени и шкалу t в диапазоне [0,1]. Каждая функция положения линейна по t, поэтому определите x1(t) = x10 + x1m * t (т. е. x10 — это начальное значение, а x1m — градиент), и аналогично для y1(t), x2(t) и y2(t). Для вершины V = (vx, vy) время (если есть), в которое V лежит на отрезке, соединяющем точки, определяется уравнением At^2 + Bt + C = 0, где:

A = x1m * y2m - x2m * y1m
B = vx * (y1m - y2m) + vy * (x2m - x1m)
     + x10 * y2m - x20 * y1m
     + y20 * x1m - y10 * x2m
C = vx * (y10 - y20) + vy * (x20 - x10)
     + x10 * y20 + x20 * y10

(Или что-то в этом роде. Учитывая вероятность ошибок транскрипции на обратной стороне конверта, я настоятельно рекомендую проверить это самостоятельно перед реализацией!)

Если у этого есть действительное решение в диапазоне [0,1], Боб твой дядя. Если оно уменьшится до 0 = 0 или около того, то точка все время будет на кону, и в этом случае вы должны учитывать свою политику.