18

Related question here.

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?

|improve this question
  • 2
    There is another ArcGIS GP tool, called "Integrate", that has a brief explanation of the algorithm in the help resource: help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//… -- However it is not specified well. – Allan Adair Sep 22 '11 at 5: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
  • 1
    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 3:42
6

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

|improve this answer
  • +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
10
+25

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:

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

|improve this answer
4

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.
|improve this answer
3

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.

|improve this answer
1

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.

|improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.