Проверете кой мрежест елемент е вътре в оригиналните полигони

Имам набор от неприпокриващи се многоъгълници. Тези полигони могат да споделят възли, ръбове, но строго без припокриване.

Сега ще ги свържа с помощта на техниката на ограничена триангулация на Делоне (CDT). Мога да взема мрежата без проблем.

Проблемът ми е, че след мрежата искам да знам кой елемент на мрежата към кой оригинален полигон принадлежи. МОЯТ сегашен подход е да изчисля центроида за всеки елемент на мрежата и да проверя в кой от оригиналния многоъгълник попада този центроид. Но не ми харесва този подход, тъй като изисква много изчисления.

Има ли някакви ефективни начини да направите това (по отношение на Big O времето за изпълнение)? Моите проекти включват десетки хиляди полигони и не искам скоростта да се забавя.

Редактиране: Уверете се, че всички върхове в мрежест елемент споделят общо лице, няма да работи, защото има случаи, в които всички върхове могат да имат повече от едно общо лице, както по-долу (пунктираната линия образува мрежест елемент, чийто върховете имат 2 общи лица):


c++ matlab algorithm cgal
person Graviton    schedule 06.12.2011    source източник
comment
Първоначално няма да загубите тази информация, ако водите правилно счетоводството си по време на триангулацията. Ако използвате библиотека, уверете се, че приема зададената точка по отношение на обекти. След това просто запазете препратки към оригиналните полигони в точковите обекти.   -  person wnrph    schedule 06.12.2011
comment
Здравей Graviton, намери ли отговор на този въпрос, откакто го публикуваш?   -  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

Какво ще кажете за етикетиране на всеки от вашите оригинални върхове с идентификатор на многоъгълник (или няколко, предполагам, тъй като polys могат да споделят върхове). След това, ако разбирам правилно 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

Както казва Mikeb, маркирайте всичките си оригинални върхове с идентификатор на многоъгълник.

Тъй като искате този, който е вътре в многоъгълника, просто се уверете, че обикаляте многоъгълниците само по посока на часовниковата стрелка, това гарантира, че ако точките се припокриват за два полигона, ще получите този, обърнат в правилната посока.

Бих очаквал този подход да остане близо до O(n), където n представлява брой точки, тъй като всеки триъгълник може да има само един или два многоъгълника, които припокриват и трите точки.

person Seph    schedule 06.12.2011

arrow_upward
0
arrow_downward

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

Стартирайте ConnectedComponents(G).

Всяка мрежа ще бъде етикетирана с етикет (със съответствие 1 към 1 на полигоните.)

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