Określanie przecięcia i przecięcia wieloboku

Question

Mam zestaw prostych wielokątów (bez dziur, bez samozacieleń) i muszę sprawdzić, czy się nie przecinają (jedno może być całkowicie zawarte w innym, to jest w porządku). Mogę to sprawdzić, po prostu sprawdzając wnętrze jednego wierzchołka w stosunku do innych wielokątów.

Muszę również określić drzewo ograniczające, które jest zbiorem relacji, które mówią, który wielokąt zawiera dowolny dany wielokąt. Ponieważ żaden wielokąt nie może się przecinać z żadnym innym, wtedy każdy zawarty wielokąt ma unikalny pojemnik; "następny większy". Innymi słowy, jeśli A zawiera B zawiera C, to A jest rodzicem B, a B jest rodzicem C, a nie uważamy A rodzicem C.

Pytanie: Jak skutecznie określić relacje powstrzymywania i sprawdzić kryterium braku przecięcia? Pytam to jako jedno pytanie, ponieważ być może połączony algorytm jest bardziej wydajny niż rozwiązywanie każdego problemu osobno. Algorytm powinien przyjąć jako dane wejściowe listę wielokątów, określoną przez listę ich wierzchołków. Powinien generować boolowskie B, jeśli żaden z wielokątów nie przecina żadnego innego wielokąta, a także, jeśli B = prawdziwy, listę par (P, C), gdzie wielobok P jest rodzicem dziecka C.

To nie jest Praca domowa. To jest dla projektu hobby, nad którym pracuję.

Answer 1

Po pierwsze, twój algorytm testowania powstrzymywania nie testuje poprawnie przecięcia. Wyobrazić sobie dwa prostokąty tak:

+--+ 
+--+--+--+ 
| | | | 
+--+--+--+ 
    +--+ 

Wierzchołki będzie w (1, 2) (1,3) (4,2) (4,3) i (2,1) (3,1) (2 , 4) (3,4) - żaden wierzchołek nie leży wewnątrz żadnego wielokąta, ale wielokąty faktycznie przecinają się.

Aby przetestować tego rodzaju skrzyżowanie, należy określić, czy którekolwiek z wielokątów "krawędzie przecinają się. Dla twoich potrzeb, jeśli krawędzie przecinają się, ale jeden wielokąt nie jest zawarty w drugim, to wiesz, że nakładają się one w niedozwolony sposób.

Jeśli chodzi o określenie drzewa przechowującego, jednym ze sposobów jest sortowanie wielokątów od najmniejszego do największego według obszaru. Pod warunkiem, że wielokąty nie zachodzą na siebie bez blokowania, wówczas rodzic dowolnego wielokąta w drzewie będzie pierwszym zawierającym wielobok przychodzący po nim na liście.

Edycja: Och, radzę napisać szybką procedurę nakładania się obwiedni lub obwódki i użyć tego, aby uniknąć konieczności wykonywania wszystkich testów przecięcia linii i ograniczania wierzchołków. Jeśli nadal nie jest wystarczająco szybki, prawdopodobnie chcesz zbudować quad lub drzewo BSP; to trochę komplikuje sprawy, ale całkowicie wyeliminuje również wiele kontroli skrzyżowań.

Answer 2

Ustalenie, czy żaden z wielokątów nie może się przeciąć w O(n*log(n)) przez zastosowanie Shamos-Hoey algorithm. Zależnie od tego, co zwraca algorytm Shamos-Hoey, wielokąt Pi zawiera wielobok P _j, który jest wykonywany w O(n) dla dwóch wielokątów.

Answer 3

Kod, patrz gpc.

Answer 4

Aby przetestować skrzyżowania, można użyć mojej darmowej biblioteki klipsów: http://sourceforge.net/projects/polyclipping/.

Aby przetestować izolację, najpierw wykluczyć skrzyżowania jak powyżej. Następnie użyj Clipper ponownie dodając wszystkie wielokąty - Clipper.AddPolygon().Następnie wykonaj operację Union (boolean OR) na wielokątach - Clipper.Execute (ctUnion, solution). Jeśli właściwość Clipper.ForceAlternateOrientation ma wartość true, Clipper powróci w zewnętrznych poligonach rozwiązania zgodnie z ruchem wskazówek zegara i zawiera wielokąty (dziury) w kierunku przeciwnym do ruchu wskazówek zegara. Powinna wtedy być prosta sprawa testowania orientacji wielokątów i stosowania PointInPolygon z jednego wierzchołka w wielokącie przeciwnie do ruchu wskazówek zegara względem innych wielokątów zgodnych z ruchem wskazówek zegara.