math - what - Un algoritmo simple para la intersección de polígonos

what shape has 6 sides (9)

Estoy buscando un algoritmo muy simple para calcular la intersección / recorte de polígono. Es decir, dados los polígonos P , Q , deseo encontrar el polígono T que está contenido en P y en Q , y deseo que T sea máximo entre todos los polígonos posibles.

No me importa el tiempo de ejecución (tengo algunos polígonos muy pequeños), también puedo permitirme obtener una aproximación de la intersección de los polígonos (es decir, un polígono con menos puntos, pero que aún está contenido en la intersección de los polígonos) )

Pero es realmente importante para mí que el algoritmo sea simple (pruebas más baratas) y preferiblemente corto (menos código).

editar: tenga en cuenta que deseo obtener un polígono que represente la intersección. No necesito solo una respuesta booleana a la pregunta de si los dos polígonos se cruzan.

Aquí hay un enfoque basado en la triangulación que es bastante sencillo de implementar y se puede ejecutar en O (N ² ).

Por cierto, O (N ² ) es óptimo para este problema. Imagine dos polígonos en forma de cuchillas de horquilla que se cruzan en ángulo recto. Cada uno tiene una cantidad de segmentos proporcionales al número de dientes; el número de polígonos en la intersección es proporcional al cuadrado del número de dientes.

Primero, triangula cada polígono.
Compara todos los triángulos de P a pares con todos los triángulos de Q para detectar intersecciones. Cualquier par de triángulos que se cruzan se puede dividir en triángulos más pequeños, cada uno de los cuales se encuentra en P, en Q o en la intersección. (Lo que usaste en el paso 1 puede reutilizarse para ayudar con esto). Solo conserva los triángulos que están en la intersección.
Calcule los vecinos de cada triángulo, comparándolos por pares y construya un gráfico de adyacencia. Este gráfico contendrá un subgrafo conectado para cada polígono en la intersección de P y Q.
Para cada subgráfico, elija un triángulo, camine hasta el borde y luego camine alrededor del borde, produciendo los segmentos que delimitan el polígono de salida correspondiente.

Aquí hay un enfoque simple y estúpido: al ingresar, discretice sus polígonos en un mapa de bits. Para cruzarse, Y los mapas de bits juntos. Para producir polígonos de salida, trace los bordes irregulares del mapa de bits y alise los jaggies utilizando un algoritmo de aproximación de polígono . (No recuerdo si ese enlace proporciona los algoritmos más adecuados, es solo el primer hit de Google. Puede consultar una de las herramientas para convertir imágenes de mapa de bits en representaciones de vectores. Tal vez podría invocarlas sin volver a implementar el algoritmo ?)

La parte más compleja sería trazar las fronteras , creo.

De regreso a principios de los años 90 me enfrenté a algo así como este problema en el trabajo, por cierto. Me equivoqué: se me ocurrió un algoritmo (completamente diferente) que funcionaría en coordenadas de números reales, pero parecía toparse con una plétora de casos degenerados completamente incoherentes frente a las realidades de la coma flotante (y la entrada ruidosa) . Tal vez con la ayuda de Internet hubiera hecho mejor!

Entiendo que el póster original estaba buscando una solución simple, pero desafortunadamente no existe una solución simple.

Sin embargo, recientemente he creado una biblioteca de recorte freeware de código abierto (escrita en Delphi, C ++ y C #) que recorta todo tipo de polígonos (incluidos los que se intersecan a sí mismos). Esta biblioteca es bastante simple de usar: http://sourceforge.net/projects/polyclipping/ .

Esto puede ser una gran aproximación dependiendo de sus polígonos, pero aquí hay uno:

Calcule el centro de masa para cada polígono.
Calcule la distancia mínima o máxima o promedio de cada punto del polígono al centro de masa.
Si C1C2 (donde C1 / 2 es el centro del primer / segundo polígono)> = D1 + D2 (donde D1 / 2 es la distancia que calculó para el primer / segundo polígono), entonces los dos polígonos "se cruzan".

Sin embargo, esto debería ser muy eficiente ya que cualquier transformación al polígono se aplica de la misma manera al centro de masa y las distancias del nodo central se pueden calcular solo una vez.

La forma en que trabajé sobre el mismo problema

rompiendo el polígono en segmentos de línea
encontrar línea de intersección usando IntervalTrees o LineSweepAlgo
encontrar un camino cerrado usando GrahamScanAlgo para encontrar un camino cerrado con vértices adyacentes
Referencia cruzada 3. con DinicAlgo para disolverlos

nota: mi escenario era diferente dado que los polígonos tenían un vértice común. Pero Hope esto puede ayudar

No nos has dado tu representación de un polígono. Así que estoy eligiendo (más como sugiriendo) uno para ti :)

Represente cada polígono como un gran polígono convexo y una lista de polígonos convexos más pequeños que deben ''restarse'' de ese gran polígono convexo.

Ahora, dados dos polígonos en esa representación, puede calcular la intersección como:

Calcule la intersección de los grandes polígonos convexos para formar el gran polígono de la intersección. Luego ''resta'' las intersecciones de todas las más pequeñas de ambas para obtener una lista de polígonos subtratados.

Obtienes un nuevo polígono siguiendo la misma representación.

Como la intersección poligonal convexa es fácil, este hallazgo de intersección también debería ser fácil.

Parece que debería funcionar, pero no le he dado un pensamiento más profundo con respecto a la complejidad de corrección / tiempo / espacio.

No tengo una solución muy simple, pero aquí están los pasos principales para el algoritmo real :

Haga una lista personalizada de doble enlace para los vértices y bordes del polígono. Usar std::list no funcionará porque debe intercambiar los punteros / desplazamientos siguientes y anteriores por una operación especial en los nodos. Esta es la única forma de tener código simple, y esto dará un buen rendimiento.
Encuentra los puntos de intersección al comparar cada par de bordes. Tenga en cuenta que comparar cada par de aristas dará O (N²) tiempo, pero mejorar el algoritmo a O (N · logN) será fácil después. Para algunos pares de aristas (digamos a → b y c → d), el punto de intersección se encuentra usando el parámetro (de 0 a 1) en el borde a → b, que viene dado por tₐ = d₀ / (d₀-d₁) , donde d₀ es (ca) × (ba) y d₁ es (da) × (ba). × es el producto en 2D transversal como p × q = pₓ · qᵧ-pᵧ · qₓ. Después de haber encontrado tₐ, encontrar el punto de intersección es usarlo como un parámetro de interpolación lineal en el segmento a → b: P = a + tₐ (ba)
Divida cada borde agregando vértices (y nodos en su lista enlazada) donde se cruzan los segmentos.
Luego debes cruzar los nodos en los puntos de intersección. Esta es la operación para la que necesitó hacer una lista personalizada de doble enlace. Debe intercambiar algunos pares de punteros siguientes (y actualizar los punteros anteriores en consecuencia).

Luego tiene el resultado bruto del algoritmo de resolución de intersección de polígono. Normalmente, deseará seleccionar alguna región de acuerdo con el número de cuerda de cada región. Busque el número de cuerda del polígono para obtener una explicación al respecto.

Si quiere hacer un algoritmo O (N · logN) de este O (N²) uno, debe hacer exactamente lo mismo, excepto que lo hace dentro de un algoritmo de barrido de línea. Busque el algoritmo de Bentley Ottman . El algoritmo interno será el mismo, con la única diferencia de que tendrá un número reducido de aristas para comparar, dentro del bucle.

Puede usar un algoritmo de recorte de polígono para encontrar la intersección entre dos polígonos. Sin embargo, estos tienden a ser algoritmos complicados cuando se tienen en cuenta todos los casos extremos.

Una aplicación de recorte de polígono en la que puede utilizar su motor de búsqueda favorito para buscar es Weiler-Atherton . Artículo de wikipedia sobre Weiler-Atherton

Alan Murta tiene una implementación completa de un cortador de polígonos GPC .

Editar:

Otro enfoque es primero dividir cada polígono en un conjunto de triángulos, que son más fáciles de tratar. El Teorema de dos orejas de Gary H. Meisters es el truco. Esta página en McGill hace un buen trabajo explicando la subdivisión triangular.

Si usa C ++, y no desea crear el algoritmo usted mismo, puede usar Boost.Geometry . Utiliza una versión adaptada del algoritmo de Weiler-Atherton mencionado anteriormente.