Проверьте, какой элемент сетки находится внутри исходных полигонов

Question

У меня есть набор непересекающихся полигонов.Эти многоугольники могут иметь общие узлы, ребра, но строго не перекрывать друг друга.

Теперь я собираюсь объединить их, используя технику триангуляции с ограниченным Делоне (CDT).Я могу получить сетку без проблем.

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

Есть ли эффективные способы сделать это (с точки зрения времени выполнения Big O)?В моих проектах задействованы десятки тысяч полигонов, и я не хочу, чтобы скорость замедлялась.

Редактировать: Убедитесь, что все вершины в элементе сетки имеют общую грань, работать не будет, потому что есть случаи, когда все вершины могут иметь более одной общей грани, как показано ниже (пунктирная линия).линия образует элемент сетки, вершины которого имеют 2 общие грани):

Answer 1

Я могу вспомнить два варианта, оба как-то упомянутых:

1. Поддерживать информацию в ваших точках / вершинах.См. Этот другой связанный вопрос .

2. Пересчитайте информацию, как вы это сделали, расположив каждый центроид элемента сетки в исходном многоугольнике, но это можно оптимизировать с помощьюspatial_sort и их последовательное расположение во входном полигоне (используя предыдущий результат в качестве подсказки для начала расположения следующей точки).

Answer 2

Может быть, вы можете вызвать CDT отдельно для каждого многоугольника и пометить треугольники их многоугольником после каждого вызова.

Answer 3

Как говорит Майкеб, пометьте все ваши исходные вершины идентификатором многоугольника.

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

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

Answer 4

Создайте новый граф G (V, E) следующим образом. Для каждой сетки создайте узел в V. Для каждого пунктирного ребра создайте ребро в E, которое соединяет две соответствующие сетки. Не отображайте сплошные ребра в ребра в E.

Запустите ConnectedComponents (G).

Каждая сетка будет помечена меткой (с отношением 1: 1 к полигонам.)

Answer 5

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