Find Duplicate Polygons Algorithm

Question

I have a group of polygons. My objective is to find the duplicate polygons from these group of polygons.

Using NetTopologySuite(A c# port of JTS), it is possible to compare two geometires and check if they are equal. The brute-force method(checking each polygon against every other polygon) is the only idea that comes to my mind but it is not usable if there are large number of polygons. Are there any algorithm's which would better the brute-force in this case?

I found this script which seems to contain ideas to what i am looking for(the comments indicate a divide and conquer approach..but not much details in the comments). But I have to admit i cannot get anything out of it :) .. It was done for ArcView, which I am not familiar with.

Note: I am not looking for a PostGIS/database solution as in this question. I am looking for something that can be integrated to AutoCAD, Quantum GIS or such desktop GIS products through customization(c#,c++, python etc..)

Answer 1

If the polygons are truly identical, and if you have an easy way to compute their area, just compute the area of each polygon, then sort by area, and only check polygons with matching area. A variant of this idea is to sort the polygons on the coordinate of their northern-most point (breaking ties by selecting the eastern-most of the tied points). Only check polygons whose northern-most points match. If the polygons vary enough, just sort on the number of points.

I could keep going, but you get the idea.

Answer 2

Recently I had to write a test to detect duplicated features in the shapefile using NetTopologySuite. I used a very simple approach, but it worked for my needs. I just serialized geometry to well-known text:

            using var reader = new ShapefileDataReader(path, new GeometryFactory());

            var geometryWktStrings = new HashSet<string>();

            while (reader.Read())
                Assert.True(geometryWktStrings.Add(reader.Geometry.ToText()));

            reader.Close();

To detect more complicated cases with, i.e. with different contour ordering, you could use geometry normalization before serialization.

Answer 3

If the geometry objects you are checking are identical, how about creating a dictionary of the geometries with the key being the geometry and the value being the object identifier.

You pass through the list once, adding values to the dictionary for each object. Check if the key exists before adding, and you'll be notified if you have a duplicate geometry. At that point, dive off into a loop to fix the issue. This should give you a one pass through the objects.

Answer 4

After a lot of reading, I came to the conclusion that a spatial index is what is required. The comment by @Peter Smith made me look into Rtree.

Wiki definition for RTree,

R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons

So I created an index in NetTopologySuite and queried the Index using each feature's envelope. The comparisons were thus limited to very few features.

How it was done using NTS is described in this answer.