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

Question

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

Point1 находится в некотором положении в момент времени 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

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

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

Answer 2

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

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

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

Update

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

Хорошо, у меня есть более ясное представление о проблеме сейчас, и она вдохновлена ​​предложением @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 обозначают х и у координаты точки 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-и-П2" -время мы следующее:

для каждого препятствия вершина 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-through-by-between-p1-and-p2» вычисляются, это простая задача, чтобы выяснить остальное. (То есть, выяснить, если это «становится в видимости», «становление-вне поле зрения» или «ни» тип прохождения):

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