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

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

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

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

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

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


c++ matlab algorithm cgal
person Graviton    schedule 06.12.2011    source источник
comment
Во-первых, вы не потеряете эту информацию, если будете правильно вести бухгалтерский учет во время триангуляции. Если вы используете библиотеку, убедитесь, что она принимает набор точек в терминах объектов. Затем просто сохраните ссылки на исходные полигоны в точечных объектах.   -  person wnrph    schedule 06.12.2011
comment
Привет, Гравитон, ты нашел ответ на этот вопрос с тех пор, как опубликовал его?   -  person lrineau    schedule 17.02.2014

Ответы (5)


arrow_upward
1
arrow_downward

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

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

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

person Sylvain Pion    schedule 20.11.2012

arrow_upward
0
arrow_downward

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

person Mikeb    schedule 06.12.2011
comment
это не сработает, так как я могу найти встречный пример, где все 3 вершины имеют 2 общих идентификатора многоугольника (вместо 1). - person Graviton; 06.12.2011
comment
Я тебе верю, но мне трудно это представить - person Mikeb; 06.12.2011
comment
Что, если перед выполнением триангуляции вы наложите на полигоны выпуклое ограничение? Таким образом, ваш крайний случай, когда один обертывает другой, будет разделен на несколько подполигонов. - person Mikeb; 06.12.2011

arrow_upward
0
arrow_downward

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

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

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

person Seph    schedule 06.12.2011

arrow_upward
0
arrow_downward

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

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

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

person cyborg    schedule 06.12.2011
comment
Run ConnectedComponents(G). Не могли бы вы подробнее рассказать, как это решит проблему? - person Graviton; 06.12.2011

arrow_upward
0
arrow_downward

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

person cyborg    schedule 07.12.2011