Проверьте соединение между двумя точками на двумерной плоскости

SO,

Проблема

У меня есть вопрос об алгоритме определения того, связаны ли две точки на 2D-плоскости. У меня есть:

Массив 2D-линий. Каждая строка ограничена двунаправленной точкой начала конца. Каждая точка представляет собой простой массив из двух элементов [x,y] - то есть каждая строка выглядит как ['start'=>[X0, Y0], 'end'=>[X1, Y1]]. Пусть этот набор строк будет называться L. Линии могут принадлежать друг другу (т.е. Могут быть частью другого), их можно пересечь только одной точкой e.t.c. - то есть нет ограничений для них на двумерной плоскости. Но строка не может быть точкой - то есть начало строки не может быть равно концу строки.
Две точки S и E, то есть массивы [Xs, Ys] и [Xe, Ye]

Теперь все строки из L рисуются на плоскости. Затем также рисуются S и E, и мне нужно ответить на вопрос: может ли E быть достигнуто из S без пересечения любых строк в L? И, если быть более конкретным - какой алгоритм будет оптимальным? Под "может быть достигнуто" я имею в виду, что есть путь на плоскости от S до E без пересечения любой строки из L - и, быть может, это может быть что угодно, а не только строка.

Пример

- как видите, в образце S и E не подключены. Также в образце есть случай, когда одна строка полностью принадлежит другому (серые и фиолетовые линии) - и случай, когда одна строка имеет начало/конец на другой строке (зеленые и розовые линии).

Мой подход

В настоящее время для этого я имею недетерминированный полиномиальный (NP) алгоритм. Это шаги:

Найти все пересечения для каждой пары линий.
Создайте новый набор строк из точек первого шага. Если две линии имеют одно пересечение, то в начале каждой новой строки будут четыре новые линии с точкой пересечения - или это могут быть 3 новые строки, если первая строка имеет начало/конец второй строки - или это может быть 2 новых строки, если первая строка имеет начало/конец, точно соответствует началу/концу второй линии. То есть:

поэтому 1-й случай приведет к 4 новым строкам, 2-4 случаям в 3 новых строках и 5 случаям в 2 новых строках. (строки [A, B] и [C, D])

Далее, в строках, начиная с 2-го шага, я ищу все полигоны. Многоугольник - это замкнутое линейное множество (т.е. Оно содержит замкнутую часть области)
Я определяю для подмножества S таких многоугольников, которые содержат S. Для этого я использую простой алгоритм - подсчет числа пересечений с краями многоугольника и некоторой строки из S на внешнюю плоскость (если он нечетный, то S находится внутри многоугольника, а если он четный - затем снаружи). Это алгоритм ray-casting. Тогда я делаю это для E
Теперь, когда у меня есть многоугольники, установленные для S и E, я просто сравниваю оба набора. Если они равны, то E может быть достигнуто от S и не может быть - в противном случае.

Почему этот NP?

Ответ прост: на 3-м шаге я выполняю поиск целых всех циклов в 2D-графике. Поскольку проблема нахождения максимальной/минимальной длины петли, если NP, то моя тоже (потому что я могу получить максимальную/минимальную длину цикла просто с настройкой набора циклов сортировки). Хорошая информация об этом находится здесь.

Вопрос

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

Ответ 1

В основном проблема сводится к:
1) Определите все полигоны, охватывающие некоторое пространство, которое не содержит другого полигона. В приведенном выше примере у вас есть 3 формы/циклы/многоугольники, которые не содержат других: четырехугольник, содержащий S, четырехугольник, содержащий E, и треугольник ниже 2 из них.
2) Определите, являются ли S и E противоположными внутри/вне любого из этих полигонов.

Для части 1 вам нужно построить график:

Создайте массив точек пересечения данной строки, это N ^ 2. Запомните, из каких двух линий каждая точка пересечения. Эти точки пересечения - это вершины вашего графика.

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

Теперь вы хотите найти многоугольники в своем макете. График вообще может содержать экспоненциальное число циклов. Однако каждое ребро может ограничивать только два "внутренних" многоугольника, поэтому нас интересует только полиномиальное подмножество циклов. Поэтому выберите край, затем найдите следующий край в многоугольнике и продолжайте повторять, пока вы не вернетесь туда, где вы начали, или определите, что первый край не был частью многоугольника.

Итак, предположим, что вы исходите из ребра E = (U, V) и хотите найти следующее ребро в многоугольнике (используя одну и ту же вершину V).
1) Создайте вектор T как U - V.
2) Создайте множество ребер A, которые смежны с вершиной V. Удалите E из этого набора.
3) Если набор пуст, то край не является частью многоугольника.
4) Для каждого ребра (Q, V) в построим вектор R при Q - V. (Помните, что Q и V представляют точки в 2D плоскости).
5) Нормализовать R: делить его на длину, чтобы создать вектор длины 1.
6) Определите CrossProductValue (T, R).
7) Край в с наименьшим значением CrossProductValue является следующим краем в одном соседнем полигоне. Край в с наибольшим значением CrossProductValue является следующим краем в другом многоугольнике.

CrossProductChecker(2D T, 2D R) {
  return (T.x*R.y - T.y*R.x); // cross product for 2 dimensions
}

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

============

Теперь, когда у вас есть все ваши полигоны, все, что вам нужно сделать, это проверить, есть ли в нем S, а E - вне, или наоборот.

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

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

Ответ 2

Вы можете построить так называемый "График видимости" , который соединяет две вершины препятствия, если они видны непосредственно. Самый короткий путь в этом графике (с добавлением S и E) будет самым коротким путем без препятствий между S и E в вашем конфигурационном пространстве. Алгоритмы и оптимизация графиков видимости хорошо известны и широко описаны.

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

EDIT:

Итак, позвольте мне быть более формальным: постройте график G(Ver, Edg), где Ver содержит все конечные точки сегмента, S и E; и Edg содержит все пары вершин, которые непосредственно видны (включая следующий сегмент).

Ответ 3

Для алгоритма есть два шага.

1. Find out the maximum polyogn encompassing S and E 
    (which could possibly be an open polygon, so convex hull algorithm needs 
    to be modified)
2. E can be reached from S if
    (Case 1) The polygons are the same
    (Case 2) Both are open polygons.

Пояснение:

Шаг 1: Найдите максимальный охватывающий многоугольник точки P

Form a set of points by adding the end-points and all possible 
    intersections. (O(n^2))
Eliminate points that can only be reached from P by crossing another line. 
    This can be done by finding the intersection of the line joining P to each 
    point with all other lines (O (n^3)).
Form a convex hull of the remaining points. 
    Here it should be noted that the resulting polygon may not be closed. 
    So, the convex hull algorithm needs to be modified to get rid of 
    those possible edges which don't have a direct connection. 
    This can be efficiently done by an appropriate data structure 
    like a graph (O(n^2) in worst case)

Шаг 2: Для сравнения потребуется некоторая сортировка вершин многоугольника. Это было бы максимальным O (n long n)

Таким образом, результирующая сложность алгоритма будет O (n ^ 3)

Ответ 4

найти все пересечения между сегментами линии
удалите все точки, имеющие ранг = 1; т.е. конечной точкой, к этой точке подключен только один сегмент линии.
найдите сегмент линии, ближайший к точке S
найти многоугольник, с одной стороны которого ранее был найден сегмент линии, используя следующий подход:
- начальный сегмент линии задан
- отметьте оба конца начального сегмента, start = lsS, end = lsE
- найдите все сегменты линий, подключенные к lsE, за исключением начального сегмента
- из найденных сегментов выбирает тот самый сегмент, ближайший к ближайшей строке точки S, тот, центр которого можно соединить с точкой S без пересечения любой из рассмотренных строк
- удалить все остальные рассмотренные сегменты строк из проблемного пространства
- повторить, пока у вас не будет полного многоугольника
если полный многоугольник содержит обе точки E и S, они связаны

Он немного похож на первый поиск глубины.

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

Ответ 5

Вычислите плоский прямой график, сформированный отрезками линии, и найдите грани, к которым принадлежат S и E. Существует путь тогда и только тогда, когда S и E принадлежат одному и тому же лицу. Первые два этапа - это стандартные, полиномиально-временные алгоритмы из вычислительной геометрии, с множеством описаний и реализаций.