Generuj wielokąty z zestawu przecinających się linii

10

Jest to proste i dość powszechne pytanie, które zostało już zadane w różnych celach (patrz ten link i to też , na przykład), tutaj jednak szukamy nie pakietu oprogramowania, ale algorytmy , które moglibyśmy spróbować wdrożyć powiedzmy w Python .

Tak więc, jak pokazano poniżej, zmapowany jest zestaw linii (są już przycięte, BTW).
Algorytmy / pomysły do ​​generowania wielokątów (jak pokazano na czerwono) ?

wprowadź opis zdjęcia tutaj

algorithm polygonize geometry-conversion Deweloper
źródło
Czy znana jest zewnętrzna granica kwadratu, czy też też należy ją odczytać z linii wejściowych?
Devdatta Tengshe,

Odpowiedzi:

6

Cóż, podajemy tutaj odpowiedź, która nie jest pełną odpowiedzią na nasze pytanie, tzn. Pytanie pozostanie „ otwarte na udzielenie odpowiedzi ”. Jest to jednak rozwiązanie problemu w pytaniu. Oto sztuczka, której użyliśmy:

Najpierw zobaczmy wyniki :
wprowadź opis zdjęcia tutaj

Więc podane linie w leftzbudowanych wielokątach pokazane w middle. Są to prawdziwe wielokąty, jak pokazano w right;)

Dla podanego poniżej algorytmu użyliśmy Shapelypakietu w Pythonie .

  • linie ==> MultiLineString {:: M}
  • dodaj malutki buffer, powiedz eps{:: MB}
  • region ==> Polygon {:: P} (region to kwadrat)
  • P.difference(MB) {powstałe wielokąty}

Zauważ , że działa szybko cicho. Jednak brakującym punktem jest to, że algorytm nie jest oryginalną metodą budowania wielokąta z linii . Niemniej jednak zadziałało idealnie w przypadku problemu, który mieliśmy w ręku.

Deweloper
źródło
4

Pakiet JTS Topology Suite ma klasę Polygonizer, która prawie to robi.

Możesz rzucić okiem na kod źródłowy, dostępny tutaj i przekonwertować go na Python.

Devdatta Tengshe
źródło
Jak wynika z opisu kodu, nie będzie działać zgodnie z oczekiwaniami autora pytania: „krawędzie muszą być odpowiednio nodowane; to znaczy muszą się spotykać tylko w punktach końcowych. Polygonizer będzie działał na niepoprawnie nodowanych danych wejściowych, ale nie będzie tworzyć wielokątów z innych niż -nodowane krawędzie ”
Pablo
1
W JTS istnieje operacja polegająca na prawidłowym podziale linii w wierzchołkach. Może OP też może na to spojrzeć.
Devdatta Tengshe
3

Możesz rzucić okiem na pakiet Python Shapely, szczególnie polygonize ()

Dave
źródło
Szybka notatka, która poligonizuje w Shapely ( from shapely.ops import polygonize), używa GEOS.Polygonize z GEOS . To jest link, w którym znajduje się link do linku ...: |
Deweloper
Nasze próby polygonizew ogóle się nie udały. Jednak dziękuję za przypomnienie, Shapelydzięki któremu możemy znaleźć rozwiązanie (w rzeczywistości sztuczkę) w formie zamieszczonej jako odpowiedź.
Deweloper
2

Oto inne rozwiązanie, które możemy znaleźć.

Za pomocą DCELmożemy tworzyć bloki z dotykających się linii.

Dla Pythona jest pakiet {tutaj} . Jest to niewielka implementacja z kilkoma błędami. Niemniej jednak przy pewnym wysiłku można go wykorzystać do rozwiązania tego problemu. Zwróć również uwagę na następujące etapy:

Etap wstępnego przetwarzania, w którym znajdują się wszystkie przecięcia między liniami. Następnie odpowiednio wszystkie linie są dzielone na segmenty w punktach interakcji. Lista punktów przecięcia i lista powiązanych krawędzi są potrzebne do DCEL.

Deweloper
źródło
Ponieważ ta metoda jest oryginalnym rozwiązaniem i zapewnia znacznie lepszą wydajność w porównaniu z inną metodą, w której differenceużywana jest operacja.
Deweloper