Jak odwzorować wielokąt z otworami?

Question

Zazwyczaj popularne jest pracować z wielokątami z ich wierzchołkami posortowanymi CW lub CCW w wektorach (macierze 2 * 1 lub 1 * 2). Jak jednak określić wielokąty z dziurami w wektorach?

Zamierzam zastosować różne procesy na tych wielokątach, więc chcę sposobu na reprezentowanie, z którym mógłbym pracować łatwo lub wydajnie. (Tj. Jak określić tego rodzaju wielokąty w moim programie w celu złagodzenia moich algorytmów ?)

wielokąty są 2D i programuję w MATLAB.

EDYCJA 1: Zamierzam obliczyć visibility graph tych wielokątów (z otworami lub bez).

Answer 1

Tak jak wspominali inni, wielokąt z dziurami może być reprezentowany jako zewnętrzna granica plus zero lub więcej wewnętrznych granic, z których wszystkie są nawzajem nienakładające się * .Jeśli użyjesz niezerowego winding number do określenia wewnątrz/na zewnątrz, pamiętaj, aby określić swój wewnętrzny r granice w przeciwnym kierunku niż granice zewnętrzne (w kierunku przeciwnym do kierunku ruchu wskazówek zegara i w kierunku zgodnym z ruchem wskazówek zegara dla wnętrza lub odwrotnie), tak aby całki konturu były równe zero w otworach.

FYI, ten rodzaj definicji/reprezentacji został sformalizowany w specyfikacji OpenGIS Simple Features (PDF).

ile reprezentacji:

ja pewnie ma szereg komórek k macierzy NX2, przy czym pierwszy element macierzy komórkowej jest granica zewnętrzna, przy czym kolejne elementy (jeśli występują) w komórkach tablica to granice wnętrza. Chciałbym użyć tablicy komórek, ponieważ może nie być tej samej liczby punktów na każdej granicy.

* Nonoverlapping = z wyjątkiem pojedynczych punktów, np. diament wewnątrz kwadratu:

Answer 2

Wielokąt, a także lista wielokątnych otworów. Po prostu upewnij się, że różne wielokąty nie przecinają się.

Co zamierzasz z tym zrobić?

Answer 3

Wygląda na to, że każdy otwór jest wielokątem wewnątrz samego wielokąta. Być może możesz przechowywać wektor taki jak opisujesz dla zewnętrznego wielokąta, a następnie wektor większej liczby wektorów wielokąta dla dziur.

Answer 4

Co dokładnie masz na myśli pod "grafem widoczności"?

Dwa "pełne" poligony, możliwe dwa stany, +1 lub -1.

Jeśli reprezentujesz dziurę, masz jedną ze stanem +1 i jedną ze stanem -1, który reprezentuje dziurę, powodując stan 0.
Jeśli masz nakładające się wielokąty, W efekcie powstanie stan> 1. Następnie możesz obliczyć granice nowego wielokąta.
Jeśli masz dwa wielokąty z przecinanymi dziurami, to najpierw obliczyć stan nowego wielokąta, który składa się z zewnętrznych granic dwóch starych, a następnie rozprawić się z dziurami.

W każdym razie ... Myślę, że otrzymujesz ogólną zasadę.

Nie mam pojęcia, jak to zrobić w Matlab, użyłem go tylko marginalnie, a nawet to dla bardzo prostych rzeczy.

Answer 5

Można podzielić wielokąt z otworem na dwa kształty bez otworu. Gdy wykonujesz integrację konturową na złożonej płaszczyźnie, możesz utworzyć "cięcie" z jednej krawędzi wielokąta, która prowadzi do krawędzi otworu; zintegrować z jedną stroną otworu i pleców; następnie przemierzaj drugą stronę dla drugiego wielokąta. Kończy się z dwiema całkami ścieżek wzdłuż każdego cięcia, które znoszą się nawzajem.

"wykres widoczności" - czy jest to obliczenie współczynnika promieniowania z zacienieniem? Lub algorytm graficzny śledzenia promieni?

Answer 6

Prawdopodobnie będziesz chciał mieć strukturę drzewa, jeśli chcesz, aby była tak ogólna, jak to możliwe (tj. Wielokąty z wielokątnymi otworami, w których znajdują się wielokąty z otworami w środku, ...). Matlab nie jest zbyt dobry w wydajnym reprezentowaniu struktur drzewa, ale oto jeden pomysł ...

Masz strukturę wielokątów.

Każdy wielokąt jest strukturą z dwoma polami, "rogami" i "dziećmi".

Pole "narożniki" zawiera macierz współrzędnych (x, y) narożników, dostępnych jako "dane {polyIdx} .corners (:, cornerIdx)".

Pole "dzieci" jest strukturą wielokątów.

Oto przykład jakiegoś kodu, aby trójkąt z dziećmi fałszywych które są otwory (nie są one bardzo ważne, choć, ponieważ będą one prawdopodobnie pokrywać:

polygon = struct; 
npoints = 3; 
polygon.corners = rand(2,npoints); 
polygon.children = struct; 
nchildren = 5; 
for c=1:nchildren 
    polygon.children(c).corners = rand(2,npoints); 
    polygon.children(c).children = struct; 
end 

Można nadal rekurencyjnie określić dzieciom, że alternatywny między tworzeniem otworów a ich wypełnianiem