# Find Duplicate Polygons Algorithm

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..)

-
I imagine a modification using something like toblerity.github.com/rtree would help greatly. Build a spatial index and check for duplicates while building the index – Peter Smith Aug 3 '12 at 20:51
@PeterSmith - I think this is a nice idea! ..why don't you add this as an answer .. I think NetTopologySuite has Rtree built-in .. will have to dig in.. – vinayan Aug 4 '12 at 0:36

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.

-
Llaves, this idea looks pretty simple and easy, even without having any other GIS software or api. – vadivelan Sep 12 '12 at 15:07

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.

-
It looks very interesting..but I am not sure it would work..I will try it out and come back.. – vinayan Aug 4 '12 at 0:33

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.

-