Was ist der Unterschied zwischen dem Werkzeug "Thiessen-Polygone erstellen" (ArcGIS) und dem Werkzeug "Voronoi-Polygone" (QGIS)?

12

Sind Thiessen-Polygone dasselbe wie Voronoi-Polygone? Ich verwende ArcMap 10 und auch QGIS 2.4 und möchte bitte den genauen Unterschied (falls vorhanden) zwischen den beiden Methoden kennen.

Maria Karypidou
quelle
Könnten Sie bitte Ihre Recherchen zu diesem Thema beschreiben und worüber müssen Sie sich im Einzelnen informieren?
Aaron
1
Wir hatten tatsächlich eine Diskussion darüber, ob die beiden Tags auf meta kombiniert werden sollen: meta.gis.stackexchange.com/questions/3677/…
Chris W

Antworten:

20

Ja, sie sind dasselbe. Auf dem Gebiet der GIS bezeichnen wir sie nach dem amerikanischen Meteorologen, der sie häufig verwendete, als Thiessen-Polygone. In anderen Bereichen, insbesondere Mathematik und Informatik, werden sie zu Ehren des Mathematikers Georgy Voronyi allgemein als Voronoi-Diagramme bezeichnet. Beide Verwendungen sind akzeptabel.

WhiteboxDev
quelle
Obwohl das Konzept das gleiche ist, frage ich mich, ob die Implementierung in jeder Software ...
Chris W
@ ChrisW Das ist eine lohnende Frage, aber eine ziemlich schwierige Frage, denke ich. Ich würde denken, dass es, wie bei den meisten räumlichen Problemen, mehr als einen Lösungsweg gibt, der darauf schließen lässt, dass es unterschiedliche Implementierungen gibt.
WhiteboxDev
Entschuldigung, ich war eher rhetorisch. Ich wollte nur darauf hinweisen , dass , während die Konzepte waren die gleiche, und Sie werden in der beide Software im Allgemeinen das gleiche Ergebnis (oder zumindest Ergebnistyp) erhalten, wie sie gehen über es nicht das gleiche sein könnten und die Ergebnisse könnten nicht genau das gleiche sein. Grundsätzlich ist es wichtig, mehr über die Frage zu lesen, als wirklich notwendig ist, aber es könnte von Bedeutung sein, wenn Sie tief genug gehen.
Chris W
@ ChrisW Ja, so habe ich deine Frage interpretiert. Und das ist ein wirklich gültiger Punkt, den Sie ansprechen. Ich würde denken, dass Implementierungsdetails in zwei beliebigen GIS, die ein Thiessen-Polygon-Tool anbieten, zu geringfügigen Unterschieden führen würden, genauso wie ein Flow-Accumulation- oder Watershed-Tool, das auf dieselben Daten in zwei unterschiedlichen GIS angewendet wird, geringfügige Unterschiede aufweisen könnte. Es gibt eine Menge zwischen der theoretischen Funktionsweise eines Algorithmus und seiner Computercode-Implementierung.
WhiteboxDev
@ ChrisW Übrigens ist es genau Ihre Frage, die mich überhaupt zur Idee von Open-Access-Software und Whitebox GAT geführt hat. Wenn das OP gefragt hätte, wie das Thiessen-Polygon-Tool von Whitebox GAT funktioniert, wäre die Antwort so einfach wie das Drücken der Schaltfläche „Code anzeigen“ im Dialogfeld des Tools. Siehe verlinkten Blog für Details zu dem, was ich meine: whiteboxgeospatial.wordpress.com/2014/05/04/…
WhiteboxDev
9

Wir können den genauen Unterschied nicht erkennen, da wir den Quellcode der ESRI-Implementierung nicht sehen können. Aus einem flüchtigen Blick geht jedoch hervor, dass die beiden Implementierungen tatsächlich dieselbe Methode verwenden, die eine grobe Übersetzung des klassischen Sweepline-Algorithmus von Steven Fortune darstellt .

Hier können Sie sich den tatsächlichen Quellcode ansehen, der in QGIS verwendet wird. Es enthält die folgende Beschreibung:

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.

Jetzt können wir den proprietären Code von ESRI, der das Tool steuert , nicht sehen , aber die Beschreibung der Dokumentation zeigt sofort, dass die Basis beider Tools dieselbe ist:

Die proximalen Polygone von Thiessen sind wie folgt aufgebaut:

Alle Punkte werden zu einem triangulierten unregelmäßigen Netzwerk (TIN) trianguliert, das das Delaunay-Kriterium erfüllt. Die senkrechten Winkelhalbierenden für jede Dreieckskante werden erzeugt und bilden die Kanten der Thiessen-Polygone. Die Position, an der sich die Winkelhalbierenden schneiden, bestimmt die Positionen der Thiessen-Polygonscheitelpunkte.

Die tatsächlichen Nuancen des Codes, der die beiden steuert, unterscheiden sich offensichtlich, da nachgewiesen wurde, dass die Übersetzung von Bill Simon Fehler aufweist , die in der ESRI-Version nicht vorhanden sind.

Es gibt (wie bereits in den obigen Kommentaren erwähnt) verschiedene andere Möglichkeiten, Voronoi-Diagramme zu generieren, auch in GIS, beispielsweise diese rasterbasierte Methodik . Es gibt auch andere vektorbasierte Methoden zum Generieren von Voronoi-Diagrammen in GIS.

Jede der Methoden hat verschiedene Vor- und Nachteile. Zum Beispiel ist der Fortune-Algorithmus relativ schnell und gut dokumentiert, aber derzeit ist keine Möglichkeit bekannt, mit seiner direkten Implementierung multiplikativ gewichtete Voronoi-Diagramme zu erstellen .

Rastermethoden sind im Allgemeinen viel langsamer in der Berechnung, ermöglichen jedoch die Erstellung verschiedener Arten von Voronoi-Diagrammen ( z. B. Voronoi-Diagramme mit dem höchsten Punkt ), ohne die Methodik vollständig neu zu erfinden.

Vollständige Offenlegung: Ich habe als wissenschaftlicher Mitarbeiter des Professors gearbeitet, der die Arbeit für die rasterbasierte Methode zur Erstellung von Voronoi-Diagrammen verfasst hat.


TL; DR: Obwohl sich die tatsächlichen Implementierungen geringfügig unterscheiden, basieren sie auf demselben Algorithmus und sollten beide das gleiche Ergebnis liefern (abgesehen von den wenigen Randfällen, die die in Dan Pattersons Frage oben genannten Fehler hervorrufen).

Conor
quelle