Encontre o algoritmo de polígonos duplicados

Eu tenho um grupo de polígonos. Meu objetivo é encontrar os polígonos duplicados desse grupo de polígonos.

Usando o NetTopologySuite (uma porta c # do JTS), é possível comparar dois geometires e verificar se são iguais. O método da força bruta (comparar cada polígono com outro polígono) é a única ideia que me vem à cabeça, mas não é utilizável se houver um grande número de polígonos. Existe algum algoritmo que melhoraria a força bruta nesse caso?

Encontrei esse script que parece conter idéias para o que estou procurando (os comentários indicam uma abordagem de dividir e conquistar .. mas não há muitos detalhes nos comentários). Mas tenho que admitir que não consigo tirar nada disso :) .. Foi feito para o ArcView, com o qual não estou familiarizado.

Nota: Não estou procurando uma solução PostGIS / banco de dados como nesta pergunta . Estou procurando algo que possa ser integrado ao AutoCAD, Quantum GIS ou a esses produtos GIS de desktop através da personalização (c #, c ++, python etc.)

Se os polígonos forem realmente idênticos e se você tiver uma maneira fácil de calcular sua área, apenas calcule a área de cada polígono, classifique por área e verifique apenas os polígonos com a área correspondente. Uma variante dessa idéia é classificar os polígonos na coordenada do ponto mais ao norte (quebrando os laços selecionando o ponto mais ao leste dos pontos empatados). Verifique apenas os polígonos cujos pontos mais ao norte correspondem. Se os polígonos variarem bastante, basta classificar o número de pontos.

Eu poderia continuar, mas você entendeu.

Se os objetos de geometria que você está verificando são idênticos, que tal criar um dicionário das geometrias com a chave como geometria e o valor como identificador do objeto.

Você passa pela lista uma vez, adicionando valores ao dicionário para cada objeto. Verifique se a chave existe antes de adicionar e você será notificado se tiver uma geometria duplicada. Nesse ponto, mergulhe em um loop para corrigir o problema. Isso deve lhe dar uma passagem pelos objetos.

Depois de muita leitura, cheguei à conclusão de que é necessário um índice espacial . O comentário de @Peter Smith me fez olhar para Rtree .

Definição da wiki para RTree,

Árvores R são estruturas de dados em árvore usadas para métodos de acesso espacial, ou seja, para indexar informações multidimensionais, como coordenadas geográficas, retângulos ou polígonos

Então, criei um índice no NetTopologySuite e consultei o índice usando o envelope de cada recurso. As comparações foram, portanto, limitadas a muito poucos recursos.

Como isso foi feito usando o NTS está descrito nesta resposta .