Algoritmos para hacer coincidir segmentos

23

¿Cuáles son los mejores algoritmos para unir segmentos?

Estoy tratando de hacer coincidir los segmentos correspondientes de dos fuentes de mapas, una menos precisa pero con nombres de segmentos, y otra más precisa sin nombres de segmentos. Quiero aplicar semiautomáticamente los nombres de los segmentos al mapa más preciso.

El algoritmo solicitado tiene una descripción bastante vaga porque una "coincidencia" no está bien definida, y muchos factores (orientación, longitud relativa, distancia) pueden tener un peso diferente en diferentes escenarios; Sin embargo, estoy buscando un conocimiento básico sobre los enfoques generales para manejar este problema.

Las implementaciones de trabajo para entornos de código abierto (PostGIS, shapely, ...) son muy bienvenidas.

Segmentos de muestra : vea la descripción debajo de las imágenes.

    
pregunta Adam Matan 31.01.2011 - 12:47

6 respuestas

14

La distancia de Hausdorff se puede usar: los segmentos coincidentes podrían ser segmentos "cercanos" según esta distancia. Es bastante simple calcular en segmentos.

Una implementación java gratuita está disponible en JTS : consulte Paquete de distancia JTS . También puede consultar el JCS Conflation Suite (ahora abandonado, copia de las fuentes, por ejemplo, en enlace ).

    
respondido por el julien 31.01.2011 - 13:02
10

No sé cuál sería el "mejor", porque eso dependerá de los detalles de sus segmentos.

Un enfoque generalmente bueno es agrupar los segmentos en información geométrica crucial . Esto incluiría, como mínimo, la ubicación del centro (x, y), la orientación (0 a 180 grados) y la longitud. Con los pesos adecuados aplicados y algunas mejoras en la orientación (porque 180 "vueltas" a 0), puede aplicar casi cualquier estadístico algoritmo de agrupación a la colección de todos los segmentos. ( K-means sería una buena opción, pero la mayoría de los métodos jerárquicos deberían funcionar bien. Tales los análisis de conglomerados tienden a ser rápidos y fáciles de aplicar.) Idealmente, los segmentos se producirán en pares (o singletons para segmentos no coincidentes) y el resto es fácil.

Una forma de lidiar con el problema de la orientación es hacer una copia de los segmentos etiquetados. Agregue 180 grados a la orientación de la primera copia, si es menos de 90, y reste 180 grados de la orientación. Esto amplía su conjunto de datos (obviamente) pero por lo demás no cambia el algoritmo de ninguna manera.

Los pesos son necesarios porque las diferencias de coordenadas, longitudes y orientaciones pueden significar cosas muy diferentes con respecto a las similitudes de sus segmentos correspondientes. En muchas aplicaciones, las diferencias entre los segmentos surgen de las diferencias en las ubicaciones de sus puntos finales. Como una aproximación aproximada, podemos esperar que la variación típica en las longitudes de los segmentos sea aproximadamente la misma que la variación típica entre sus puntos finales. Por lo tanto, los pesos asociados con x, y, y la longitud deben ser aproximadamente iguales. La parte difícil es la orientación de la ponderación, ya que la orientación no se puede equiparar con la distancia y, lo que es peor, es más probable que los segmentos cortos estén mal orientados que los segmentos largos. Considere un método de prueba y error que equipara algunos grados de desorientación al tamaño de un espacio típico entre segmentos y luego lo ajusta hasta que el procedimiento parece funcionar bien. Para orientación, sea L una longitud de segmento típica. Un cambio de orientación con un ángulo pequeño t grados barrerá una distancia de aproximadamente L / 2 * t / 60 (el 60 se aproxima al número de grados en un radián), que es L / 120 veces t . Eso sugiere comenzar con los pesos de unidad para x, y, y la longitud y un peso de L / 120 para la orientación.

En resumen , esta sugerencia es:

  1. Haga copias de los segmentos etiquetados (como se describe en el párrafo sobre cómo ajustar la orientación).

  2. Convierta cada segmento en la cuádruple (x, y, longitud, L / 120 * orientación) donde L es una longitud de segmento típica.

  3. Realice un análisis de grupo de las cuádruples. Utilice un buen paquete estadístico ( R es gratis).

  4. Use la salida del análisis de clúster como una tabla de búsqueda para asociar segmentos etiquetados con segmentos cercanos no etiquetados.

respondido por el whuber 31.01.2011 - 17:15
4

Trabajé en un proyecto con un requisito similar hace unos 5 años. Se trataba de combinar coordenadas de líneas centrales de calles (con una precisión de coordenadas relativamente alta) con Sistema de monitoreo del rendimiento de la carretera > (HPMS) enlaces de red de tráfico.

En el momento en que la FHWA no proporcionó ninguna herramienta para hacer este tipo de cosas. Eso puede haber cambiado, es posible que desee comprobar. Incluso si no está trabajando con datos de carreteras, las herramientas podrían ser relevantes.

Lo escribí con ArcGIS, pero el algoritmo debería funcionar en código abierto, siempre que proporcione capacidades de seguimiento similares a ISegmentGraph :

// features is a collection of features with higher geometry
// Links are a collection features with attributes but low res geometry
For each Link in lowResFeatureclass
    point startPoint = SnapToClosestPoint(Link.StartPoint, hiResfeatures);
    if(startPoint == null)
       continue;
    point endPoint = SnapToClosest(Link.EndPoint, hiResfeatures);
    if(endPoint == null)
       continue;
    polyline trace = Trace(hiResfeatures,startPoint,endPoint);
    if(polyline != null)
    {
        // write out a link with high precision polyline
        Write(Link,polyline);
    }
Next Link
    
respondido por el Kirk Kuykendall 31.01.2011 - 18:49
4

Aquí viene una idea

Si rompe uno de los cadenas lineales para comparar y probar si los puntos de vértice se encuentran a cierta distancia de la otra cadena lineal para comparar, puede controlar la prueba de muchas maneras.

esos ejemplos funcionan en PostGIS (quien podría adivinar :-))

Primero, si decimos que hay una coincidencia si todos los puntos de vértice en una serie de líneas en la tabla_1 son 0.5 metros (unidades de mapa) o más cerca de una serie de líneas en la tabla_2:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points,
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(*)=num_of_points;

Luego podemos decir que hay una coincidencia si más del 60% de los puntos de vértice en una serie de líneas en table_1 está dentro de la distancia de una serie de líneas en table_2

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)/num_of_points::float > 0.6

O podemos aceptar que un punto no está dentro del rango:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)-num_of_points <= 1;

También tendrás que ejecutar la consulta con table_1 y table_2 en roles invertidos.

No sé qué tan rápido será. ST_Dumppoints es actualmente una función sql en PostGIS y no una función C, lo que la hace más lenta de lo que debería ser. Pero creo que será bastante rápido de todos modos.

Los índices espaciales ayudarán mucho para que ST_Dwithin sea efectivo.

HTH Nicklas

    
respondido por el Nicklas Avén 31.01.2011 - 20:03
4

He escrito código para manejar la coincidencia de segmentos de línea descuidados (y se superponen) en Boundary Generator. Escribí las matemáticas (bastante elementales) detrás de esto aquí: enlace . El código es de código abierto y amp; enlazado desde esa entrada de blog.

El código sigue un enfoque muy simple:

  • Una prueba de segmento a segmento que le dirá si dos segmentos de línea se superponen dentro de las tolerancias de ángulo y distancia dadas, y la cantidad de superposición.
  • Un índice espacial quick'n'dirty que elimina la necesidad de probar cada segmento de línea en el conjunto de datos contra todos los demás segmentos de línea en el conjunto de datos.

La principal ventaja de este enfoque es que obtiene perillas muy precisas para el ángulo, las distancias y la longitud de superposición válidos; en el lado negativo, no es una forma de medir la similitud de dos segmentos de línea, por lo que es mucho más difícil, por ejemplo. haga un agrupamiento estadístico para determinar las coincidencias posibles: está atascado con los mandos precisos.

Nota: supongo que con suficientes chuletas de SQL podría agrupar la prueba segmento-segmento en una cláusula WHERE ... :)

¡Salud!

    
respondido por el Dan S. 01.02.2011 - 00:15
0

He implementado un prototipo aproximado para la correspondencia de mapas aquí , que es relativamente fácil de usar. Se basa en el motor de enrutamiento de código abierto y está escrito en Java. El algoritmo utilizado se describe aquí .

    
respondido por el Karussell 12.01.2015 - 16:24

Lea otras preguntas en las etiquetas