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

Question

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

Точка1 находится в некоторой позиции в момент времени t, и ее положение определяется непрерывными функциями x1 (t) и y1 (t), задающими координаты x и y в момент времени t. Эти функции не дифференцируемы, они построены кусочно из отрезков.

Точка 2 одинакова, с x2 (t) и y2 (t), каждая функция имеет одинаковые свойства.

Препятствия, которые могут помешать видимости, - это простые (и неподвижные) полигоны.

Как я могу найти граничные точки для видимости?

т.е.. Есть два вида границ: где точки становятся видимыми и становятся невидимыми.

Для становящейся видимой границы i существует некоторое ϵ> 0, такое что для любого действительного числа a, a ∈ (i-ϵ, i), Point1 и Point2 не видны (то есть отрезок прямой, который соединяет (x1(a), y1(a)) до (x2(a), y2(x)) пересекает некоторые препятствия).

Для b ∈ (i, i + ϵ) они видны.

И наоборот - становится невидимым.

Но могу ли я найти точную такую ​​границу, и если да, то как?

Answer 1

Хорошо, теперь у меня есть более четкое представление о проблеме, и вдохновленный предложением @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.)

Чтобы найти каждое время "a-vertex-is-pass-by-Между-p1-and-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, точки уже будут быть на новых сегментах).

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

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

Answer 2

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

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

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

Обновление

Процесс идентификации столкновений вершин действительно достаточно прост, он просто включает решение слегка утомительного квадратного уравнения в 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 или как-то так, то точка находится на линии все время, и в этом случае вы должны рассмотреть свою политику.

Answer 3

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

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