Algoritmo de búsqueda de polígonos duplicados

Question

Tengo un grupo de polígonos. Mi objetivo es encontrar los polígonos duplicados de este grupo de polígonos.

Utilizando NetTopologySuite (Un port c# de JTS), es posible comparar dos geometrías y comprobar si son iguales. El método de fuerza bruta (comprobar cada polígono contra cada otro polígono) es la única idea que me viene a la mente, pero no es utilizable si hay un gran número de polígonos. ¿Existe algún algoritmo que mejore la fuerza bruta en este caso?

He encontrado este script que parece contener ideas de lo que estoy buscando (los comentarios indican un enfoque de divide y vencerás pero no hay muchos detalles en los comentarios). Pero tengo que admitir que no puedo sacar nada de ella :) .. Se hizo para ArcView, que no estoy familiarizado con.

Nota: No busco una solución PostGIS/base de datos como en esta pregunta . Busco algo que pueda integrarse en AutoCAD, Quantum GIS o productos SIG de escritorio mediante personalización (c#, c++, python, etc.).

Answer 1

Si los polígonos son realmente idénticos, y si tiene una forma sencilla de calcular su área, calcule el área de cada polígono, ordénelos por área y compruebe sólo los polígonos con el área coincidente. Una variante de esta idea es ordenar los polígonos según la coordenada de su punto más septentrional (rompiendo los empates seleccionando el punto más oriental de los empatados). Compruebe sólo los polígonos cuyos puntos más septentrionales coincidan. Si los polígonos varían lo suficiente, basta con ordenarlos por el número de puntos.

Podría seguir, pero ya te haces una idea.

Answer 2

Recientemente tuve que escribir una prueba para detectar características duplicadas en el shapefile utilizando NetTopologySuite. He utilizado un enfoque muy simple, pero funcionó para mis necesidades. Acabo de serializar la geometría a un texto bien conocido:

            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();

Para detectar casos más complicados con, por ejemplo, con diferente ordenación de los contornos, podría utilizar la normalización de la geometría antes de la serialización.

Answer 3

Si los objetos geométricos que está comprobando son idénticos, ¿qué le parece crear un diccionario de las geometrías cuya clave sea la geometría y cuyo valor sea el identificador del objeto?

Se recorre la lista una vez, añadiendo valores al diccionario por cada objeto. Comprueba si la clave existe antes de añadirla, y se te notificará si tienes una geometría duplicada. En ese momento, sumérgete en un bucle para solucionar el problema. Esto debería darle una pasada a través de los objetos.

Answer 4

Después de mucho leer, llegué a la conclusión de que un índice espacial es lo que se necesita. El comentario de @Peter Smith me hizo mirar en Rtree .

Definición Wiki para RTree,

Los árboles R son estructuras de datos en forma de árbol que se utilizan para métodos de acceso espacial, es decir, para indexar información multidimensional como coordenadas geográficas coordenadas geográficas, rectángulos o polígonos.

Así que creé un índice en NetTopologySuite y consulté el índice utilizando la envolvente de cada característica. De este modo, las comparaciones se limitaron a muy pocas características.

Cómo se hizo utilizando NTS se describe en esta respuesta .