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

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

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

Предположим, что p1 движется по линии AB , а p2 движется (одновременно) по CD в качестве параметра ] t изменяется от 0 до 1. (То есть в момент времени t = 0,5 , p1 находится в середине AB и p2 в середине CD .)

Если Ax и Ay обозначают координаты x и y точки A (и аналогично для B , C и D ) мы можем выразить p1 и p2 как функции of 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-вершина-проходит-между-p1- and-p2 "-time делаем следующее:

Для каждого obsta cle vertex 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 фактически находится между (расширенной) AB линией и (расширенной) линией CD . Если t также находится между 0 и 1, вершина v фактически проходит по линии p1-p2 за время, пока точки перемещаются по этим сегментам (поскольку когда t , скажем, 1,3, точки уже будут на новых участках).

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

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

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

Если вам нужен временной интервал (при котором точки p1 и p2 не находятся в пределах прямой видимости), вы можете выполнить вышеупомянутую проверку для разных значений t (желательно с относительно небольшими различиями) и между «видимым-t» и "invisible-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 или чему-то подобному, то точка все время находится на линии, и в этом случае вам придется задуматься о своей политике.