Linie do wielokątów

11

Nie udało mi się znaleźć „nazwy” algorytmu, który pozwoliłby na konwersję linii na wielokąty. Ponieważ zagadnienie to przecina GIS oraz dziedziny geometrii obliczeniowej i informatyki. Nie jestem pewien, co jeszcze dodać do miksu. Nie chcę podawać listy tego, czego szukałem, ponieważ chciałbym również wiedzieć, co inni ludzie uznaliby za swój pierwszy wybór kryteriów wyszukiwania.

Scenariusz ... Mam linie (dwa punkty potrzebne do zbudowania linii) ... każda linia jest połączona z co najmniej jedną inną linią. Przestrzeń pośrednia między połączonymi liniami tworzy wielokąt. Najprostszym scenariuszem byłby trójkąt ... prostokąt ... i można przejść dalej do funkcji wielosegmentowych.

Przepraszam za jakiekolwiek niejasne opisy, ale jak powiedziałem, nie chcę kierować możliwymi rozwiązaniami ścieżką, którą już odwiedziłem, ponieważ interesuje mnie „pierwsza myśl”, a nawet ostateczne rozwiązanie.

polygon algorithm geometry-conversion Germán Carrillo
źródło
Czy linie mogą się pokrywać? Czy linie mogą się krzyżować? (tj. czy jest czysty?) Jeśli tak, mam nadzieję, że wywołanie tego procesu Kompilacja nie będzie zbyt specyficzna dla aplikacji.
Kirk Kuykendall
Linie Kirka Coincyta i inne „defekty” zostałyby usunięte przed zbudowaniem wielokątów… Próbuję znaleźć „nazwę algorytmu”, który jestem pewien, że został zaimplementowany w różnych pakietach GIS (np. Arcgis). Krótko mówiąc, weź pod uwagę, że wszystkie warunki zdegenerowane zostały rozwiązane i że masz czyste linie (2 linie punktowe), które pokrywają się w węzłach, które powinieneś być w stanie zbudować wielokąty. Kluczem jest to, że linie istnieją, nie ma warunków zdegenerowanych, a przestrzeń pośrednią należy przekształcić w wielokąty. Dzięki
Czy punkty są na płaszczyźnie czy na kuli?
Kirk Kuykendall
Kirk ... Na płaszczyźnie, metryczne współrzędne x, y, a nie sferyczne. Załóżmy na przykład, że masz segmenty linii, które utworzyłyby diagram voronoi, ale wszystko, co masz, to segmenty, które je tworzą, ale nie faktyczna struktura danych, do której doprowadziły. Krótko mówiąc, każdy segment jest połączony, a każdy segment jest unikalny.

Odpowiedzi:

4

Może „wypełnienie obszaru”? Zobacz tutaj i tutaj .

Edytować

Inną możliwością jest ograniczona triangulacja . (Łącze prowadzi do apletu Java, który pozwala narysować wykres za pomocą myszy, a następnie ilustruje algorytm przemiatania płaszczyzny w celu triangulacji.) Wynik takiej triangulacji, bez względu na sposób jej przeprowadzenia, można łatwo przetworzyć utwórz pożądane wielokąty: po prostu połącz wszystkie sąsiednie trójkąty, które mają nowo utworzoną krawędź.

Przykład

Oryginalny wykres:

Oryginalny wykres

Wykres trójkątny:

wprowadź opis zdjęcia tutaj

Whuber
źródło
Bill Idzie do głosowania, ponieważ nie spotkałem się z tym ... nie chcę ograniczać innych komentarzy ludzi z różnych dyscyplin.
Chociaż w dużej mierze dotyczy wypełnień rastrowych, jest to najbliższa odpowiedź. Nadal nie mam nazwy algorytmu, chyba że jest on dołączony do rastra lub wektora, ale algorytm „wyciągnięcia po ścieżce” może wystarczyć, ale przez całe życie nie mogę zrozumieć, dlaczego współrzędne byłyby sortowane według Y zamiast X ( który jest łatwy do wdrożenia w większości języków).
@Dan Sortowanie według y lub x jest nieistotne, jak sugerujesz. Masz również rację, że w grę wchodzą algorytmy przemiatania płaszczyzny lub przemiatania linii, ale niestety jest to ogólna technika, która obejmuje prawie wszystkie procedury geometrii obliczeniowej, więc nie jest to odpowiedni termin na wyszukiwanie twojego algorytmu. Zauważ, że ten konkretny problem nie jest wyłącznie teorią graficzną, ponieważ wiąże się z osadzeniem kompleksu polilinii w płaszczyźnie (lub kuli), a zatem dobry algorytm musi przechowywać informacje o osadzaniu: dlatego tak naprawdę jest to problem z wypełnieniem obszaru w sercu.
whuber
5

W teorii grafów operacja ta nazywana jest obliczeniem powierzchni . Jest to związane z obliczeniem podwójności danego wykresu.

Na przykład w bibliotece GeOxygène java na wykresie (o nazwie CarteTopo ) znajduje się metoda getFaces w celu pobrania jej powierzchni .

Nazywa się to poligonizacją w JTS

Julien
źródło
Dobre linki. Wszyscy jednak zakładają, że problem @ Dana został już rozwiązany: możliwość nazwania wykresu „planarnym” oznacza, że ​​już zidentyfikowałeś ściany wielokątne. Chce przede wszystkim wiedzieć, w jaki sposób można przekształcić dowolną kolekcję łuków (w płaszczyźnie) w planarny wykres uczciwości do dobra. Wymaga to zbudowania reprezentacji jego „topologii”, takiej jak DCEL.
whuber
Wielkie dzięki, whuber, jesteś źródłem wiedzy! Zastanawiam się, jak ktoś może być tak błyskotliwy.
Julien
4

Oprogramowanie hosta RepRap konwertuje listę segmentów linii (w nieznanej losowej kolejności) na listę wielokątów, która brzmi podobnie do tego, co próbujesz zrobić.

W szczególności algorytm „dopasowywania końca” RepRap obsługuje wiele przypadków patologicznych.

Niestety, oprogramowanie RepRap zakłada, że ​​każdy narożnik ma do niego parzystą liczbę krawędzi - 2 linie przechodzące do narożnika na normalnym obiekcie; 4 linie idące razem, gdy róg jednego obiektu styka się z rogiem innego obiektu itp. Nie wiem, jak trudno byłoby dostosować ten algorytm do obsługi diagramów voronoi, które zwykle mają 3 krawędzie przechodzące do każdego rogu.

David Cary
źródło
+1 Ciekawe znalezisko! Uważaj jednak: chociaż to oprogramowanie wydaje się być w stanie rozwiązać wiele problemów związanych z łączeniem linii w wielokąty, może zrobić zbyt wiele : wygląda na to, że próbuje również uprościć funkcje, co może być niepożądanym efektem ubocznym. (Np. Może zniszczyć integralność topologiczną.)
whuber
3

czy sprawdziłeś bazę kodu GRASS, aby znaleźć rozwiązanie swojego problemu? -> http://old.nabble.com/Polyline-to-Polygon-operation-td20257839.html

oeon
źródło
1
Dzięki ... ale nie szukam konkretnego „spakowanego” rozwiązania, ale bazowy algorytm i / lub jego nazwę, która miałaby pochodzić z różnych obszarów GIS, Comp Geom i / lub Comp Sci ... kontynuuj pomysły
Myślałem o szczegółowym spojrzeniu na kod źródłowy 2 wspomnianych procesów w moim łączu, który może ci pomóc.
oeon
Myślę, że musiałbym zainstalować oprogramowanie, aby zobaczyć kod, ponieważ nie widzę żadnych wpisów na tych stronach, chyba że czegoś brakuje.
1
Możesz przeglądać źródło GRASS online: trac.osgeo.org/grass/browser
underdark
@underdark Dzięki za wskaźnik. O ile mogę stwierdzić main.cw v.typeźródle, wszystko, co się dzieje, to to, że funkcje są ponownie oznaczane jako granice: rzeczywiste przetwarzanie nie występuje. Z perspektywy czasu nie jest to zbyt zaskakujące: jeśli (nie jestem pewien) funkcje są utrzymywane z pełną informacją topologiczną 2D, wówczas wszystkie obliczenia w celu zidentyfikowania regionów wielokątnych odbywają się automatycznie podczas tworzenia lub importu obiektów i są zachowywane przez cały czas wszystkie operacje geoprzetwarzania.
whuber
3

Halo

Nie sądzę, że to, czego szukasz, to określony algorytm. Zadanie może być dość trudne lub bardzo proste w zależności od zestawu danych.

Powinieneś podzielić problem na co najmniej 2 części. 1) jest bardziej problemem sieciowym, jak znaleźć zamknięte pierścienie z liniami. 2) wyrazić zamknięty znacznik liniowy jako wielokąt

Druga część, czyli „konwersja linii na wielokąty”, zależy bardziej od formatu niż reprezentacja wielokąta / oznaczenia linii. Mam na myśli przejście z:

LINESTRING (1 1, 2 2)
LINESTRING (2 2, 2 1)
LINESTRING (2 1, 1 1)

na:
POLYGON ((1 1,2 2,2 1,1 1))

przekształca linię w wielokąt, ale chyba nie o tym mówisz. Trudniejsza część jest pierwsza. Jeśli masz spaghetti linii, jak zamówić je jako zamknięte linie.

Wydaje mi się, że odpowiedź na to pytanie zależy od wielu zbiorów danych. Jak pyta Kirk, czy linie mogą przekroczyć problem jest znacznie większy. Jeśli wiesz, że wszystkie „kolekcje linii” są częścią zamkniętego oznaczenia linii, staje się łatwiejsze. Następnie możesz złapać dowolną linię i przejść się ścieżką, dopóki nie wrócisz, a następnie przejdź do kroku drugiego powyżej.

Chodzi mi o to, że stan zestawu danych określa wszystkie zasady dotyczące tego, jak to zrobić. Jeśli chcesz znaleźć wszystkie możliwe wielokąty w spaghetti z liniami liniowymi, zakładam, że będzie musiało być wiele różnych algorytmów, aby umieścić punkty wierzchołków na wszystkich skrzyżowaniach, przeszukać wszystkie możliwe ścieżki i tak dalej.

W PostGIS funkcja nazywa się ST_Polygonize. Ta funkcja tworzy wszystkie możliwe wielokąty z podanych linii.

Jest to wykonywane przez GEOS, dzięki czemu można znaleźć algorytmy zarówno w kodzie GEOS, jak i JTS.

Tylko kilka myśli

/ Nicklas

Nicklas Avén
źródło
1

Możesz spróbować poszukać algorytmu „Forward Star”. Powiedziano mi, że jest ogólna, ale jedyne dyskusje na ten temat, które kiedykolwiek czytałem, zawsze dotyczyły arkgis. Może zajrzyj do odniesień cytowanych w tych notatkach do wykładu dotyczących gwiazdy naprzód.

Kirk Kuykendall
źródło
1
Skomentuję tutaj, mimo że ten komentarz dotyczy również innych proponowanych rozwiązań: problemu nie można przedstawić w sieci (ani na wykresie). Wymaga informacji o sposobie łączenia linii w dwuwymiarowej powierzchni . Zatem reprezentacje gwiazd do przodu / do tyłu byłyby mało przydatne; potrzebny jest DCEL lub coś podobnego.
whuber
@ whuber - Zakładałem, że komentarz Dana, że ​​wszystkie „wady” zostały usunięte, sugerował, że linie były czyste. W związku z tym powinno być możliwe sprowadzenie tego do problemu przejścia przez wykres znajdowania wszystkich cykli na wykresie. Na początku myślałem, że gwiazda Forward pomoże w algorytmach, które poruszają się po wykresie, wykonując najostrzejszy możliwy skręt w prawo w każdym węźle. Jednak patrząc trochę więcej, wydaje się, że są lepsze sposoby. stackoverflow.com/questions/261573/... Ale nadal zakłada to, że problem można ponownie określić jako wykres.
Kirk Kuykendall
1
Znajdowanie cykli na wykresie to nie to samo, co znajdowanie ścian na wykresie planarnym. Rozważmy abstrakcyjny wykres z wierzchołkami {a, b, c, d} i krawędziami {a, b}, {a, c}, {b, c}, {b, d}, {c, d}. Podstawą dla cykli są a-> b-> d-> c-> a oraz a-> b-> c-> a. W osadzeniu planarnym a -> (0,1), b -> (2,2), c -> (2,0), d -> (3,1) (gdzie wszystkie krawędzie są segmentami linii), cykl a-> b-> d-> c-> a nie jest twarzą, ale jeśli przesuniemy d do (1,1), to jest twarz. To pokazuje, dlaczego pojęcie „twarzy” wymaga osadzenia wykresu w płaszczyźnie i dlaczego ścian nie można obliczyć wyłącznie z abstrakcyjnej struktury wykresu.
whuber