Is Thiessen polygons the same thing as Voronoi polygons? I am using ArcMap 10 and also QGIS 2.4 and I would like please to know the exact difference (If any) between the two methods.
asked Sep 16, 2014 at 12:53
-
Could you please describe any research you have done on the subject and what in particular you need clarification on?– Aaron ♦Commented Sep 16, 2014 at 13:14
-
1We were actually having a discussion on whether to combine the two tags on meta: meta.gis.stackexchange.com/questions/3677/…– Chris WCommented Sep 16, 2014 at 19:07
Add a comment
|
2 Answers
Yes, they are the same thing. In the field of GIS we tend to refer to them as Thiessen polygons, after the American meteorologist who frequented their use. In other fields, particularly mathematics and computer science, they are generally referred to as Voronoi diagrams, in honour of the mathematician Georgy Voronyi. Both uses are acceptable.
answered Sep 16, 2014 at 13:06
-
While the concept is the same, I wonder if the implementation in each software is...– Chris WCommented Sep 16, 2014 at 19:09
-
@ChrisW That's a worthwhile question but a rather tough one to answer, I'm guessing. I'd think that, like most spatial problems, there's more than one way to come to the solution, which would suggest that there are different implementations. Commented Sep 16, 2014 at 19:34
-
Sorry, I was more being rhetorical. I just wanted to point out that while the concepts were the same, and you'll get generally the same result (or at least type of result) in the two softwares, how they go about it might not be the same and the results might not be exactly the same. Basically choosing to read more into the question than might really be necessary, but could matter if you went deep enough.– Chris WCommented Sep 16, 2014 at 20:00
-
@ChrisW Yep, that's how I interpreted your question. And it's a really valid point you raise. I would think that implementation details in any two GIS offering a Thiessen polygon tool would lead to slight differences in the same way that a flow-accumulation or watershed tool applied to the same data in two different GIS might differ slightly. There's a lot that goes between the theoretical workings of an algorithm and its computer code implementation. Commented Sep 16, 2014 at 20:07
-
@ChrisW Incidentally, it is exactly your question that led me to the notion of 'open-access' software and Whitebox GAT in the first place. If the OP had asked how Whitebox GAT's Thiessen polygon tool works, the answer would be as simple as pressing the 'View Code' button on the tool's dialog. See linked blog for details on what I mean: whiteboxgeospatial.wordpress.com/2014/05/04/… Commented Sep 16, 2014 at 21:22
We cannot know the exact difference because we cannot see the source code of ESRI's implementation. However, it appears from a cursory glance that the two implementations do, in fact, utilize the same method that is a rough translation of Steven Fortune's classic sweepline algorithm.
Here you can have a look at the actual source code that is used in QGIS. It includes the following description:
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.
Now we can't see ESRI's proprietary code that drives their tool, but their documentation's description immediately reveals that the basis behind both tools is the same:
Thiessen proximal polygons are constructed as follows:
All points are triangulated into a triangulated irregular network (TIN) that meets the Delaunay criterion. The perpendicular bisectors for each triangle edge are generated, forming the edges of the Thiessen polygons. The location at which the bisectors intersect determine the locations of the Thiessen polygon vertices.
The actual nuances of the code driving the two are obviously different, as it has been demonstrated that Bill Simon's translation has known bugs that are not present in ESRI's version.
There are (as has been stated in comments above) several other different ways to generate Voronoi diagrams, even in GIS, such as this raster based methodology. There are also other vector based methods to generate Voronoi diagrams in GIS.
There are several advantages and disadvantages to each of the methods. For example, Fortune's algorithm is relatively fast and well documented, but currently there is no known way to generate multiplicatively weighted Voronoi diagrams using his direct implementation.
Raster methods are generally much slower computationally but allow for creation of different types of Voronoi diagrams (such as farthest point Voronoi diagrams) without completely reinventing methodology.
Full disclosure: I have worked as a research assistant to the professor who wrote the paper for the raster based methodology for generating Voronoi Diagrams.
TL;DR: Though the actual implementations differ slightly, they are based upon the same algorithm and both should produce the same result (aside from the few edge cases that produce the bugs noted in Dan Patterson's question linked above).
