¿Cuál es la manera más eficiente de determinar si dos segmentos de línea son parte del mismo segmento, dentro de una tolerancia?

Question

Editar: Cambió el título. Estoy menos interesado en que los dos segmentos sean iguales, sino más bien, si son colineales entre sí, dentro de cierta tolerancia. Si es así, entonces las líneas deben agruparse juntas como un solo segmento.

Edit: Supongo que una forma breve de decir esto: Estoy tratando de agrupar segmentos de líneas similares juntos de una manera eficiente.

Decir que tengo segmentos de línea f(fx0, fy0) y (fx1, fy1) y g(gx0, gy0) y (gx1, gy1)

Estos provienen de algo así como un detector de bordes algoritmo de visión por ordenador, y en algunos casos, las dos líneas son básicamente los mismos, pero se contados como dos líneas distintas debido a las tolerancias de píxeles.

Hay varios escenarios

• f y g comparten exactamente los mismos puntos finales, por ejemplo: f = (0,0), (10,10) g = (0,0), (10,10)
• f y g comparten aproximadamente los mismos puntos finales, y aproximadamente la misma longitud, por ejemplo: f = (0,0.01), (9.95,10) g = (0,0), (10,10)
• f es un subconjunto de g, lo que significa que sus puntos finales se encuentran dentro del segmento g y comparten el sam e slope como el segmento g. Piense en una línea más o menos dibujada en la que el bolígrafo ha ido y venido para hacerla más gruesa. por ejemplo: f = (4.00, 4.02), (9.01, 9.02) g = (0,0), (10,10)

lo siguiente sería no ser considerado el mismo:

• f y g tienen una diferencia de pendiente más allá de cierto tolerance
• f y g pueden tener la misma pendiente pero son separados por una distancia más allá de tolerance, es decir, líneas paralelas
• f y g están en el mismo plano y en la misma pendiente, pero no se superponen en absoluto ... es decir. un conjunto de segmentos dentro de una línea punteada.

La forma más sencilla de saber si son lo mismo es si gx1 - fx1 <= tolerance (repetir para los otros tres puntos), pero en algunos casos, la línea f puede ser más corta que la línea g (de nuevo, debido a las diferencias de píxeles y/o escaneo de fotos pobre).

Entonces, ¿es mejor convertir los dos segmentos en coordenadas polares y comparar los ángulos? En ese caso, las dos rho estarían dentro de una tolerancia. Pero luego debes asegurarte de que los dos segmentos de línea tengan la misma "dirección", lo cual es trivial para calcular en coordenadas cartesianas o polares.

Así que esto es fácil de encontrar una manera, pero me pregunto si hay una manera mucho más limpia, basada en el álgebra lineal que he olvidado hace tiempo.

Answer 1

Su problema es doble: se quiere comparar tanto la diferencia en la longitud y la diferencia en los ángulos. Para calcular la diferencia en longitud, tomaría la longitud de la primera línea y la dividiría por la longitud de la segunda línea.

para tomar la diferencia en el ángulo, puede utilizar atan o, mi favorito:

angle = acos(abs((u dot v)/(u.length * v.length)))

Esperemos que esto ayuda. Perdón por la respuesta equivocada anterior.

vieja respuesta:

He aquí una idea para usted: ¿por qué no comparar la diferencia en los puntos de inicio y final de los dos segmentos de línea a la longitud total de una de las líneas? Entonces su función de diferencia sería algo como:

def difference(Line l1, Line l2): 
    # Distance between first point on first line and first point on second line 
    first_point_diff = (Line(l1.x1, l2.x1, l1.y1, l2.y1).length()) 

    # Distance between first point on first line and first point on second line 
    second_point_diff = (Line(l1.x2, l2.x2, l1.y2, l2.y2).length()) 

    return (first_point_diff + second_point_diff)/l1.length() 

Esta función devolverá la "diferencia" entre dos líneas como una fracción de la longitud total de la primera línea.

Answer 2

Se puede utilizar las coordenadas para definir ecuaciones de las líneas? Si es así, entonces podrías usar las dos ecuaciones en un sistema de ecuaciones, resolver el sistema y averiguar si las líneas se cruzan y dónde. Si las líneas no se cruzan en absoluto, pero la distancia entre ellas es muy pequeña, o con la tolerancia, puede considerarlas como una sola línea.

Answer 3

Si lo que quieres es ver si están en la misma dirección, ¿no podría simplemente considerar el producto de punto dividido por las magnitudes? Más cerca está de 1, cuanto más cerca esté la alineación entre las dos líneas.