¿Cómo comparar dos formas?

¿Hay alguna manera de comparar dos formas geométricas (o dos estructuras de datos más genéricas), sin usar la fuerza bruta cuando se trata de una tolerancia?

La fuerza bruta (es decir, la comparación de cada valor de cada objeto con cada valor del otro objeto) funciona pero es lenta y no puedo usarla.

Traté de ordenar los datos y comparar dos colecciones ordenadas. Es rápido, pero solo funciona con tolerancia cero. Tan pronto como agregue la tolerancia, me pierdo. El problema es que dos valores pueden ser idénticos cuando los comparo y diferentes cuando los ordeno.

Aquí hay algunos detalles de mi problema.

En mi complemento VBA de Excel, tengo una colección de objetos Shape creados por una colección de objetos Line , hechos por dos objetos Point cada uno. El complemento escanea un dibujo CAD a través de COM y crea la colección de objetos Shape .

Una versión simplificada podría generar esto:

  Shape 1 Shape 2 Point 1 0.0 5.0 0.0 4.9 Point 2 4.9 0.0 5.1 0.0 Point 3 5.0 5.0 5.0 5.0 

Necesito encontrar qué formas son idénticas a qué formas, donde los medios idénticos tienen la misma forma, tamaño y orientación, pero no la misma posición (hasta ahora es trivial) más o menos tolerancia (¡no tan trivial ahora!)

El Point.IsIdenticalTo(OtherPoint) se define como:

 Function IsIdenticalTo(OtherPoint As Point) As Boolean IsIdenticalTo = Abs(X - OtherPoint.X) < Tolerance And Abs(Y - OtherPoint.Y) < Tolerance End Function 

La implementación de fuerza bruta de Shape.IsIdenticalTo(OtherShape) funciona pero es demasiado lenta: si cada Line(I) tiene una OtherShape.Line(J) idéntica y viceversa, entonces las dos formas son idénticas. A veces tengo cientos de formas con cientos de líneas cada una, por lo que la solución de fuerza bruta no funciona para mí.

Probé dos enfoques que involucraban colecciones ordenadas. Ambos son rápidos porque la comparación de dos colecciones ordenadas es más rápida que la fuerza bruta, pero ambas fallan en algunas condiciones:

  1. Una colección SortedValues contiene todos los valores X e Y de todas las líneas. Los valores se ordenan, por lo que la información sobre si un valor es una X o una Y se pierde. He usado este enfoque durante meses sin problemas, pero falla, por ejemplo, cuando la única diferencia entre dos formas es entre los puntos (10, 20) y (20, 10) . Agregué el ángulo de línea a la lista de valores, las cosas han mejorado, pero todavía hay casos en que este enfoque falla, porque se pierde cierta información cuando los valores se ordenan juntos. En el ejemplo anterior, este enfoque funcionaría con las siguientes colecciones:

     Shape 1 Shape 2 0.0 0.0 0.0 0.0 4.9 4.9 5.0 5.0 5.0 5.0 5.0 5.1 
  2. Una colección SortedLines contiene todas las líneas ordenadas en sentido contrario a las agujas del reloj y comenzando desde el punto más cercano al origen. Este enfoque no pierde ninguna información, pero falla en el ejemplo anterior porque el algoritmo de clasificación no concuerda con la comparación de igualdad. Si la tolerancia es 0.5, deberían ser idénticos, pero el algoritmo de clasificación produce las colecciones que se muestran a continuación. Las cosas se vuelven más difíciles porque mis formas contienen subfiguras, por lo que hay muchos puntos de partida en cada forma.

      Shape 1 Shape 2 Point 1 4.9 0.0 0.0 4.9 Point 2 5.0 5.0 5.1 0.0 Point 3 0.0 5.0 5.0 5.0 

EDITAR:

Las formas se importan desde una aplicación gráfica externa a través de COM. Una forma puede ser tan simple como un rectángulo o tan compleja como cualquier esquema elegante con 10 círculos en el interior, 20 formas internas y 30 líneas. Representan paneles con orificios y decoraciones simples, y a veces tienen forma de dientes de sierra, lo que hace docenas de bordes.

  1. manejar forma como polígono

    convierte tus puntos (cada línea) a un conjunto de líneas (length,angle) como en esta imagen:

    representación de polígono

    esto asegura la invariancia en rotación / traducción. Si ve más líneas con angle=PI únalos para evitar comparaciones erróneas de las mismas formas con diferentes muestreos; intente también hacer coincidir la misma regla de bobinado de polígono CW / CCW para ambas formas.

  2. encontrar punto de inicio

    Puede ser el angle, length más grande o más pequeño angle, length … o el orden específico de angles+lengths . Así que reordene las líneas de un polígono (cyclic shift) para que sus formas se comparen desde el “mismo punto” si pueden.

  3. comparación – para una coincidencia exacta

    • el número de líneas tiene que ser el mismo
    • los perímetros deben ser iguales +/- algo de precisión

    así por ejemplo:

     fabs (sum of all lengths of poly1 - sum of all lengths of poly2) <= 1e-3 

    si no las formas son diferentes. Luego compara todas las longitudes y angularjs. Si cualquier valor difiere más que el valor de precisión, las formas son diferentes.

  4. comparación - el tamaño no importa

    calcular el perímetro de ambos polígonos l1,l2 y cambiar el tamaño de todas las longitudes del poly2 comparado para que coincida con el perímetro de poly1 modo que todas las longitudes de poly2 se multipliquen por el value = l1/l2; . Después de esta comparación de uso de la viñeta n . ° 3

  5. comparación: las desviaciones de forma aún pueden coincidir positivamente (el tamaño debe ser el mismo)

    Intente establecer el número de líneas con el mismo valor (una todas las líneas con un ángulo cercano a PI ). Entonces los perímetros deben "coincidir" ... fabs(l1-l2)<=1e-3*l1 . Puedes usar la viñeta # 4 comparación

  6. comparación: las desviaciones de tamaño y forma aún pueden coincidir

    simplemente poly2 tamaño de poly2 para que coincida con el perímetro de poly1 como en la viñeta n.º 4 y luego use la viñeta n.º 5

Si no puede encontrar el punto de inicio en los polígonos del stand (viñeta n.º 2 )

Luego debe verificar todos los cambios de punto de inicio, de modo que si sus polígonos tienen un stand de 5 líneas:

  poly1: l11,l12,l13,l14,l15 poly2: l21,l22,l23,l24,l25 

Luego, tiene que comparar las 5 combinaciones (a menos que encuentre el emparejamiento antes):

  cmp (l11,l12,l13,l14,l15),(l21,l22,l23,l24,l25) cmp (l11,l12,l13,l14,l15),(l22,l23,l24,l25,l21) cmp (l11,l12,l13,l14,l15),(l22,l23,l24,l25,l21) cmp (l11,l12,l13,l14,l15),(l23,l24,l25,l21,l22) cmp (l11,l12,l13,l14,l15),(l24,l25,l21,l22,l23) cmp (l11,l12,l13,l14,l15),(l25,l21,l22,l23,l24) 

[Notas]

  1. También hay formas más rápidas de comparar, pero pueden fallar en algunos casos

    • puedes comparar histogtwigs de líneas, angularjs
    • puedes usar la neural network (no me gustan pero son ideales para clasificaciones como esta)
  2. si tus formas deben orientarse de la misma manera (sin invariancia de rotación)

    a continuación, en lugar de ángulo de vértice utilice el ángulo de dirección de la línea

  3. si no puede garantizar la misma regla de devanado para ambos polígonos comparados

    entonces tienes que verificarlos en el stand:

     cmp (l11,l12,l13,l14,l15),(l21,l22,l23,l24,l25) cmp (l11,l12,l13,l14,l15),(l25,l24,l23,l22,l21) 

Sé que es una respuesta un poco vaga, pero aún espero que ayude al menos un poco ...

Tengo el mismo problema. Calculo la matriz adyacente del vértice ponderado con las distancias. Este calcula todos los lados de longitud y diagonales. Entonces, si el módulo de cada fila o columna de la matriz es el mismo con la otra matriz, entonces las dos formas son las mismas. Para la tolerancia simplemente use la función round () antes del inicio. La complejidad es O (n2 / 2), porque tienes que calcular solo la mitad de la matriz adyacente que es simétrica. El problema es que no puedo detectar si una forma está volteada.