Algoritmos para la correspondencia de segmentos

Question

¿Cuáles son los mejores algoritmos para que coincida con los segmentos?

Estoy tratando de coincidir con los correspondientes segmentos de dos de mapa de fuentes, uno menos precisa pero con nombres de segmento, y uno de los más precisos sin nombres de segmento. Quiero semi-aplicar automáticamente los nombres de segmento para el mapa más exacto.

La solicitada algoritmo tiene una vaga descripción debido a un "partido" no está bien definido, y muchos factores (orientación, en relación longitud, distancia) puede tener un peso diferente en diferentes escenarios; sin Embargo, estoy en busca de un conocimiento básico acerca de los criterios generales para el manejo de este problema.

Implementaciones de trabajo para el entorno de código abierto (PostGIS, bien formada, ...) son una calurosa bienvenida.

Muestra de segmentos : Vea a continuación la descripción de las imágenes.

Answer 1

La distancia de Hausdorff se puede utilizar: segmentos correspondientes podrían ser 'cerrar' los segmentos de acuerdo a esta distancia. Es muy simple de calcular en segmentos.

Gratis java de la aplicación está disponible en el STC - ver aquí. Usted también puede tener una mirada en el JCS Combinación Suite.

Answer 2

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

En general un buen método es que el hash de los segmentos en crucial la información geométrica. Esto incluiría, como mínimo, la ubicación del centro (x,y), orientación (de 0 a 180 grados), y la longitud. Se aplican las ponderaciones correspondientes, y algunos finessing de la orientación (debido a 180 "envuelve" a 0), entonces podría aplicar a casi cualquier estadística algoritmo de clustering para 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ía funcionar bien. Tales análisis de agrupamiento tienden a ser fáciles y rápidos de aplicar.) Idealmente, los segmentos se producen en pares (o únicos para una incomparable segmentos) y el resto es fácil.

Una manera de lidiar con la orientación problema es hacer una copia de la etiqueta de los segmentos. Añadir 180 grados a la orientación de la primera copia, si es de menos de 90, y de lo contrario, resta 180 grados a partir de la orientación. Con esto se amplía el conjunto de datos (obviamente), pero de lo contrario, no cambia el algoritmo de alguna manera.

Pesos son necesarios debido a las diferencias de coordenadas, longitudes, y a las orientaciones que puede significar cosas muy diferentes sobre las similitudes de sus segmentos correspondientes. En muchas aplicaciones, las diferencias entre los segmentos surgen de las diferencias en las ubicaciones de sus extremos. Como una aproximación, podemos esperar típica de la variación en la longitud de los segmentos a ser aproximadamente el mismo que el de la variación típica entre sus extremos. Por lo tanto, los pesos asociados con x, y, y la longitud debe ser aproximadamente la misma. La parte difícil es la ponderación de orientación, debido a que la orientación no puede ser equiparada con la distancia y, peor aún, segmentos cortos serían más propensos a estar mal orientados a que los segmentos de largo. Considerar una prueba-y-error de método que equivale a un par de grados de desorientación para el tamaño de un típico brecha entre los segmentos y, a continuación, que se ajusta hasta que el procedimiento parece funcionar bien. Para orientación, vamos a L ser una típica la longitud del segmento. Un cambio de orientación de un pequeño ángulo de t grados se llevará a cabo una distancia de aproximadamente L/2 * t / 60 (el 60 aproxima el número de grados en un radián), que es L/120 veces t. Que sugiere comenzar con la unidad de pesos para x, y, y longitud y un peso de L/120 para la orientación.

En resumen, esta sugerencia es:

1. Hacer copias de la etiqueta de los segmentos (como se describe en el apartado sobre finessing la orientación).

2. Convertir cada segmento en el cuádruple (x, y, la longitud, L/120 * orientación) donde L es un típico de la longitud del segmento.

3. Realizar un análisis de conglomerados de la cuádruples. El uso de un buen paquete estadístico (R es gratis).

4. Utilizar el análisis de cluster de salida como una tabla de búsqueda para asociar la etiqueta segmentos con cerca de etiqueta segmentos.

Answer 3

Aquí viene una idea

Si usted destrozar uno de los linestrings para comparar y comprobar si el vertexpoints está dentro de cierta distancia de los otros linestring a comparar usted puede controlar la prueba de muchas maneras.

los ejemplos de trabajo en PostGIS (que podría adivinar :-) )

En primer lugar, si nos dicen que no es una coincidencia si todos los vértices los puntos en una cadena de línea en table_1 es de 0,5 metros (unidades de mapa) o más cerca de una linestring 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(*)=num_of_points;

Entonces, podemos decir que hay un partido en caso de que más de 60% de la vertex_points en un linestring en table_1 es dentro de la distancia de un linestring 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á en el 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;

Usted también tendrá que ejecutar la consulta con table_1 y table_2 en invertido los papeles.

No sé lo rápido que va a ser. ST_Dumppoints es actualmente una de sql-función en PostGIS y no un C-función que hace que sea más lento de lo que debería ser. Pero creo que va a ser bastante rápida de todos modos.

Los índices espaciales va a ayudar mucho para ST_Dwithin efectiva.

HTH Nicklas

Answer 4

He trabajado en un proyecto con un requisito similar hace aproximadamente 5 años. Se trataba de la combinación de las coordenadas de las líneas centrales de la calle (con relativamente alta precisión de las coordenadas) con la Autopista Sistema de Monitoreo del Desempeño (APH) el tráfico de los enlaces de la red.

En el momento de la FHWA no proporcionar las herramientas para hacer este tipo de cosas. Que puede haber cambiado, es posible que desee comprobar. Incluso si usted no está trabajando con la carretera de datos, las herramientas, todavía podría ser relevante.

La escribí con ArcGIS, pero el algoritmo debe trabajar en opensource, mientras que proporciona capacidades de seguimiento similar 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

Answer 5

He escrito el código para controlar descuidado segmento de línea coincidente (y la superposición de ellos) en el Límite del Generador. Escribí hasta la (bastante elemental) matemáticas detrás de él aquí: http://blog.shoutis.org/2008/10/inside-boundary-generator-computational.html. El código es de código abierto y vinculado a partir de la entrada en el blog.

El código de la siguiente manera realmente un enfoque simple:

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

La principal ventaja de este enfoque es que te dan muy bien precisa las perillas de ángulo válido, distancias, y la longitud de superposición; en el lado negativo, no es una manera de medir la similitud de dos segmentos de línea por lo que es mucho más difícil, por ejemplo, hacer agrupamiento estadístico para determinar probables -- usted está atascado con la precisión de los mandos.

Nota: supongo que con suficiente SQL chuletas podría meter el segmento del segmento de prueba en una cláusula where... :)

Saludos!