Jaka jest różnica między narzędziem Utwórz wielokąty Thiessena (ArcGIS) a narzędziem Wielokąty Voronoi (QGIS)?

12

Czy wielokąty Thiessen to to samo, co wielokąty Voronoi? Używam ArcMap 10, a także QGIS 2.4 i chciałbym poznać dokładną różnicę (jeśli w ogóle) między tymi dwiema metodami.

Maria Karypidou
źródło
Czy mógłbyś opisać wszelkie badania, które przeprowadziłeś na ten temat, a w szczególności czego potrzebujesz wyjaśnienia?
Aaron
1
W rzeczywistości rozmawialiśmy o tym, czy połączyć dwa tagi na meta: meta.gis.stackexchange.com/questions/3677/...
Chris W

Odpowiedzi:

20

Tak, są tym samym. W dziedzinie GIS zwykle nazywamy je wielokątami Thiessena, po amerykańskim meteorologu, który często ich używał. W innych dziedzinach, szczególnie w matematyce i informatyce, są one ogólnie nazywane diagramami Voronoi, na cześć matematyka Georgy Voronyi. Oba zastosowania są dopuszczalne.

WhiteboxDev
źródło
Chociaż koncepcja jest taka sama, zastanawiam się, czy implementacja w każdym oprogramowaniu jest ...
Chris W
@ChrisW To warte zachodu pytanie, ale raczej trudne do odpowiedzi, tak sądzę. Sądzę, że podobnie jak większość problemów przestrzennych, istnieje więcej niż jeden sposób na rozwiązanie, co sugerowałoby, że istnieją różne implementacje.
WhiteboxDev
Przepraszam, byłem bardziej retoryczny. Chciałem tylko zauważyć, że chociaż koncepcje były takie same, a generalnie uzyskasz ten sam wynik (lub przynajmniej typ wyniku) w obu programach, to , jak sobie z tym poradzą, może nie być taki sam, a wyniki mogą nie być dokładnie taki sam. Zasadniczo decydujesz się przeczytać więcej na pytanie, niż może być to naprawdę konieczne, ale może mieć znaczenie, jeśli zagłębisz się wystarczająco.
Chris W
@ChrisW Tak, tak interpretowałem twoje pytanie. I to jest naprawdę ważna kwestia, którą podnosisz. Sądzę, że szczegóły implementacji w dwóch dowolnych systemach GIS oferujących narzędzie wielokąta Thiessen doprowadziłyby do niewielkich różnic w taki sam sposób, jak narzędzie do gromadzenia przepływu lub przełomu zastosowane do tych samych danych w dwóch różnych systemach GIS może się nieznacznie różnić. Między teoretycznym działaniem algorytmu a jego implementacją kodu jest wiele rzeczy.
WhiteboxDev,
@ChrisW Nawiasem mówiąc, to właśnie twoje pytanie doprowadziło mnie do pojęcia oprogramowania „open-access” i Whitebox GAT. Gdyby OP zapytał, jak działa narzędzie wielokąta Thiessen Whitebox GAT, odpowiedź byłaby tak prosta, jak naciśnięcie przycisku „Wyświetl kod” w oknie dialogowym narzędzia. Zobacz połączony blogu szczegóły na co mam na myśli: whiteboxgeospatial.wordpress.com/2014/05/04/...
WhiteboxDev
9

Nie możemy znać dokładnej różnicy, ponieważ nie widzimy kodu źródłowego implementacji ESRI. Jednak z pobieżnego spojrzenia wynika, że ​​obie implementacje wykorzystują w rzeczywistości tę samą metodę, co zgrubne tłumaczenie klasycznego algorytmu zamiatania Stevena Fortune .

Tutaj możesz rzucić okiem na rzeczywisty kod źródłowy używany w QGIS. Zawiera następujący opis:

For programmatic use two functions are available:

   computeVoronoiDiagram(points)

        Takes a list of point objects (which must have x and y fields).
        Returns a 3-tuple of:

           (1) a list of 2-tuples, which are the x,y coordinates of the
               Voronoi diagram vertices
           (2) a list of 3-tuples (a,b,c) which are the equations of the
               lines in the Voronoi diagram: a*x + b*y = c
           (3) a list of 3-tuples, (l, v1, v2) representing edges of the
               Voronoi diagram.  l is the index of the line, v1 and v2 are
               the indices of the vetices at the end of the edge.  If
               v1 or v2 is -1, the line extends to infinity.

   computeDelaunayTriangulation(points):

        Takes a list of point objects (which must have x and y fields).
        Returns a list of 3-tuples: the indices of the points that form a
        Delaunay triangle.

Teraz nie widzimy zastrzeżonego kodu ESRI, który napędza ich narzędzie , ale opis ich dokumentacji natychmiast ujawnia, że ​​podstawa obu narzędzi jest taka sama:

Proksymalne wielokąty Thiessena są zbudowane w następujący sposób:

Wszystkie punkty są triangulowane w trójkątną nieregularną sieć (TIN), która spełnia kryterium Delaunaya. Generowane są prostopadłe dwusieczne dla każdej krawędzi trójkąta, tworząc krawędzie wielokątów Thiessena. Położenie, w którym przecinają się dwusieczne, określa położenia wierzchołków wielokąta Thiessena.

Rzeczywiste niuanse kodu kierującego tymi dwoma są oczywiście różne, ponieważ wykazano, że tłumaczenie Billa Simona zna błędy , których nie ma w wersji ESRI.

Istnieje (jak stwierdzono w komentarzach powyżej) kilka innych sposobów generowania diagramów Voronoi, nawet w GIS, takich jak ta metodologia oparta na rastrze . Istnieją również inne metody oparte na wektorze do generowania diagramów Voronoi w GIS.

Każda z metod ma kilka zalet i wad. Na przykład algorytm Fortune jest stosunkowo szybki i dobrze udokumentowany, ale obecnie nie ma znanego sposobu generowania multipleksowo ważonych diagramów Voronoi przy użyciu jego bezpośredniej implementacji.

Metody rastrowe są na ogół znacznie wolniejsze obliczeniowo, ale pozwalają na tworzenie różnych typów diagramów Voronoi ( takich jak najdalsze diagramy Voronoi ) bez całkowicie nowej metodyki.

Pełne ujawnienie: pracowałem jako asystent naukowy dla profesora, który napisał artykuł na temat metodologii opartej na rastrze do generowania diagramów Voronoi.


TL; DR: Chociaż rzeczywiste implementacje różnią się nieznacznie, opierają się na tym samym algorytmie i oba powinny dawać ten sam wynik (poza kilkoma przypadkowymi przypadkami, w których występują błędy odnotowane w pytaniu Dana Pattersona powyżej).

Conor
źródło