Algorithm to fix topological errors in GIS software apps

Question

I notice that ensuring topological correctness is essential for GIS applications, this is because the input from user or polygon boolean operation can have severe topological problems ( even though the polygons look correct) that would compromise on the quality of the subsequent operations.

Clean polygon is how Geo Wizards do to ensure the correctness of the topology.

Arcgis also has a command to clean up the slivers.

My question is not about how to use the existing software packages to ensure that the polygon input data is topologically correct; rather, my question is about how these software packages implement those cleaning procedures. In other words, what is the algorithm I can use to make sure that I can fix all the topological errors, given a set of polygonal inputs?

There is another ArcGIS GP tool, called "Integrate", that has a brief explanation of the algorithm in the help resource: http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00170000002s000000 -- However it is not specified well. — Allan Adair, Sep 22 '11 at 05:51
Your own link from Geo Wizards actually represents the algorithms fairly well. What more do you expect? — johanvdw, Sep 22 '11 at 14:29
@hohanvdw, what the link shows is not algorithm, but rather steps on how to use the software to activate the algorithm to clean the polygon. The difference between the two are huge. — Graviton, Sep 22 '11 at 15:29
Searching for planarization algorithms might turn up something useful. — Kirk Kuykendall, Sep 22 '11 at 17:55
@KirkKuykendall, I don't quite know how does the planarization algo help; I thought it is more applicable to graph theory rather than this kind of computational geometry stuff? — Graviton, Sep 23 '11 at 03:42
If the graph of a polygon isn't planar then it's an indication of a topological error. — Kirk Kuykendall, Sep 26 '11 at 17:35
@KirkKuykendall, I get what you mean, but the planarization of a polygon is just one of the condition, but not all. — Graviton, Sep 27 '11 at 02:03
I can't remember for sure, but if none of the rings of a polygon intersect each other and if each ring is planar, isn't that sufficient to be topologically clean (i.e. free of errors)? — Kirk Kuykendall, Sep 27 '11 at 02:26
@KirkKuykendall, what I mean is while planarization is one necessary condition for clean polygons, it is not sufficient, there are other conditions like there should be no sliver polygon between two polygons, polygon lines shouldn't intersect with one another etc. Ensuring the planarity of the polygon is not sufficient to ensure the rest. — Graviton, Sep 27 '11 at 02:36

score 11 · Answer 1 · answered Sep 26 '11 at 18:26

You can find a detailed description of topological cleaning routines in the source code and manuals of GRASS GIS: http://grass.osgeo.org/programming7

The cleaning routines are coded here: http://trac.osgeo.org/grass/browser/grass/trunk/vector/v.clean

Examples for the underlying routines:

Select dangles: http://grass.osgeo.org/programming7/vector_8h.html#a40e09e816c8bcb93d247710c834d93ab
Remove duplicates: http://grass.osgeo.org/programming7/vector_8h.html#a7c0deda52a08dd5a02bc05ccbe311c60
Snap lines: http://grass.osgeo.org/programming7/vector_8h.html#a563fb4e4b42695cfbfbf2dc17d42028a
etc.

The underlying concepts are outlined here: http://grass.osgeo.org/programming7/vectorlib.html#vlibTopoExamples

blah238 · Accepted Answer · 2011-09-30T23:04:36.160

8

A quick Google Scholar search turned up the following well-cited articles:

Thierry Ubeda and Max J. Egenhofer. Topological error correcting in GIS. Advances in Spatial Databases, Lecture Notes in Computer Science, 1997, Volume 1262/1997, 281-297, DOI: 10.1007/3-540-63238-7_35 (PDF)
Sylvie Servigne, Thierry Ubeda, Alain Puricelli and Robert Laurini. A Methodology for Spatial Consistency Improvement of Geographic Databases. GeoInformatica, 2000, Volume 4, Number 1, 7-34, DOI: 10.1023/A:1009824308542 (PDF)

edited Sep 30 '11 at 23:04

answered Sep 30 '11 at 21:06

blah238

35,793
7
94
195

+1 Looks like a well thought out paper. I wish the authors would define what they mean by "scene" though. – Kirk Kuykendall Sep 30 '11 at 22:34
Thanks, I added a second article (by one of the same authors), but at first glance I still can't tell what a 'scene' is. – blah238 Sep 30 '11 at 23:06

score 4 · Answer 3 · answered Sep 26 '11 at 14:34

Although not an algorithm, this page gives you some info as to what types of topology errors "check geometry" looks for in the ArcGIS tools Check Geometry/Repair Geometry. http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00170000003v000000

Null geometry: The record will be deleted from the feature class. To keep records with null geometry, uncheck the tool dialog option Delete Features with    Null Geometry, or in scripting set the delete_null parameter to KEEP_NULL.
Short segment: The geometry's short segment will be deleted.
Incorrect ring ordering: The geometry will be updated to have correct ring ordering.
Incorrect segment orientation: The geometry will be updated to have correct segment orientation.
Self intersections: the areas of overlap in a polygon will be dissolved.
Unclosed rings: The unclosed rings will be closed by connecting the ring's end points.
Empty parts: The parts that are null or empty will be deleted.
Duplicate vertex: One of the vertices will be deleted.
Mismatched attributes: The Z or M coordinate will be updated to match.
Discontinuous parts: Multiple parts will be created from the existing discontinuous part.
Empty Z values: The Z value will be set to 0.

score 3 · Answer 4 · answered Sep 26 '11 at 17:18

I don't think there is a way to completely automate correcting topological errors in a given dataset. Some things, such as dangles might be able to automate splitting and then deleting the resultant dangle. But then what about slivers between two adjacent polygons, which polygon should be merged with which sliver to eliminate it? That type of question seems to need user input. To identify the errors however I think the algorithms use some sort of variation of the DE-9IM (Dimensionally extended 9 something something). I think your best bet would be to look at the Java Topology Suite (JTS). Specifically the Geometry Graph class. I think this could be used to build the different components of a particular geometry, and then used to check different topology problems. I've never done it, but looked into it not long ago. I think QGIS includes a plugin to check for errors in geometry, you might try and find the source code for that plugin to see how they did it.

If you are not familiar with Java, GEOS is the C++ flavor of JTS, or NetTopologySuite is the C# flavor.

Hope that helps.

score 1 · Answer 5 · answered Aug 06 '12 at 13:00

ArcGIS' Integrate command documentation has already been mentioned, but ESRI have also produced a technical paper Understanding Geometric Processing in ArcGIS documenting the processing logic that is used by Integrate (and Geoprocessing operations involving tolerance more generally). This is focussed on the avoidance and correction of topological errors generated from geoprocessing. There are a few references given that may also be useful.

Algorithm to fix topological errors in GIS software apps

5 Answers5