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

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.

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.

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).