Как найти покрывающий многоугольник, если я знаю точку, все линии вокруг нее

Question

У меня есть набор линий на моей диаграмме, и у меня также есть точка. Что я хочу, так это набор линий, которые вместе образуют многоугольник через упорядоченный обход. Мне не нужна реализация или что-то еще, все, что я хочу, это чтобы кто-то направлял меня к алгоритму, который я могу использовать. Подобная проблема, как это было задано, но не будет работать для меня, потому что

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

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

Извините за всю путаницу: смотрите это для ясности https://ibb.co/nzbxGF

Answer 1

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

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

Вы можете использовать алгоритм Sweep Line для построения списка двояко связанных границ в O(nlog(n)+klog(n)) где n это количество сегментов и k является сложностью полученного подразделения (общее количество вершин, ребер и граней). Вам не нужно кодировать его с нуля, так как эта структура данных и ее алгоритм построения уже были реализованы много раз (например, вы можете использовать реализацию DCEL в CGAL).

Со структурой данных Doubly Connected Edge List вы можете решить свою проблему, применяя подход, который вы предложили в своем посте: учитывая точку ввода, решите задачу Точка в многоугольнике для каждого лица в Doubly Connected Edge List и верните набор сегменты, ограничивающие лицо, которое вы нашли. Тем не менее, этот подход, хотя может быть достаточно хорошим для нескольких простых подразделений, не является эффективным для сложных.

Лучший подход заключается в том, чтобы преобразовать Двусторонне связанный пограничный список в структуру данных, которая специализируется на запросах местоположения точек: карта трапеции. Эта структура данных может быть построена в O(nlog(n)) ожидаемое время и для любой точки запроса ожидаемое время поиска O(log(n)), Как и в случае с Doubly Connected Edge List, вам не нужно реализовывать его самостоятельно (опять же, вы можете использовать реализацию CGAL Trapezoidal Map).