algorithm - Algoritmo cuadrilátero de área mínima

language-agnostic math (6)

Existen algunos algoritmos para encontrar el rectángulo de límite mínimo que contiene un polígono dado (convexo).

¿Alguien sabe acerca de un algoritmo para encontrar el cuadrilátero delimitador de área mínima (cualquier cuadrilátero, no solo rectángulos)?

He buscado en Internet durante varias horas, pero aunque encontré algunos artículos teóricos sobre el tema, no encontré una sola implementación ...

EDITAR: La gente en Mathoverflow me señaló un artículo con una solución matemática ( mi publicación allí ), pero para el cual no encontré una implementación real. Decidí seguir el método de Monte Carlo de Carl, pero me sumergiré en el documento e informaré aquí, cuando tenga tiempo ...

¡Gracias a todos!

El enfoque de Monte Carlo

Gracias por los comentarios aclaratorios sobre el problema. He quitado que lo que se requiere no es un resultado matemáticamente correcto sino un "ajuste" que es mejor que cualquier otro ajuste comparable para otras formas.

En lugar de verter mucho poder cerebral algorítmico en el problema, dejaría que la computadora se preocupara por eso. Generar grupos de 4 puntos aleatorios; compruebe que el cuadrángulo formado por la unión convexa de esos 4 puntos no se interseca con el polígono y calcule el área del cuadrante. Repita 1 millón de veces, recupere el patio con el área más pequeña.

Puedes aplicar algunas restricciones para que tus puntos no sean completamente aleatorios; Esto puede mejorar dramáticamente la convergencia.

Monte Carlo, mejorado

He estado convencido de que lanzar 4 puntos al azar en el avión es un comienzo altamente ineficiente incluso para una solución de fuerza bruta. Así, el siguiente refinamiento:

Para cada prueba, seleccione al azar p vértices distintos y q lados distintos del polígono de modo que p + q = 4.
Para cada uno de los lados q , construya una línea que pase por los puntos finales de ese lado.
Para cada uno de los vértices p , construya una línea que pase a través de ese vértice y con una pendiente asignada al azar.
Verifique que las 4 líneas formen un cuadrilátero, y que este cuadrilátero contiene (¡y no se intersecta!) El polígono. Si estas pruebas fallan, no continúes con esta iteración.
Si el área de este cuadrilátero es el mínimo de todas las áreas vistas hasta ahora, recuerde el área y las coordenadas de los vértices del cuadrilátero.
Repita un número arbitrario de veces y devuelva el cuadrilátero "mejor" encontrado.

A diferencia de requerir siempre 8 números aleatorios (coordenadas x e y para cada uno de los 4 puntos), esta solución solo requiere (4 + p ) números aleatorios. Además, las líneas producidas no se confunden ciegamente en el plano sino que están tocando el polígono. Esto asegura que los cuadriláteros sean desde el principio al menos muy cerca del polígono.

Aquí hay una observación que conduce a una mejora del algoritmo de Monte Carlo, y también puede llevar a una respuesta directa.

Lema: si un borde de un cuadrilátero óptimo toca el polígono en un solo punto, toca el punto medio de ese borde.

Prueba: defina X e Y como la longitud de los dos segmentos a cada lado del punto de contacto. Imagine rotar el borde alrededor del punto de contacto único con un ángulo infinitesimal A. La rotación afecta el tamaño del cuadrilátero incrementándolo en XA / 2 y disminuyéndolo en YA / 2, o viceversa. Si X! = Y, entonces una de las dos direcciones de rotación lleva a un cuadrilátero más pequeño. Como el cuadrilátero es mínimo, debemos tener X = Y.

Para usar este hecho, tenga en cuenta que si seleccionamos algunos bordes y puntos donde el polígono toca el cuadrilátero, y no seleccionamos dos puntos en una fila, podemos determinar el cuadrilátero de manera única al seleccionar el borde a través de cada punto que hace ese punto. el punto medio del borde (y si eso no es posible, rechace la configuración elegida). En el algoritmo de Monte Carlo, esto se reduce a decir que no tenemos que elegir la pendiente para este borde, se puede determinar explícitamente.

Todavía tenemos el caso en el que se seleccionaron dos puntos adyacentes; espero que haya inspirado a alguien más para que retire aquí ...

Creo que cada lado del cuadrilátero delimitador de área mínima pasará a través de al menos 2 de los vértices de tu polígono. Si esta suposición es cierta, debería ser fácil realizar una búsqueda de fuerza bruta para la solución.

Genere el conjunto único de líneas que están definidas por 2 de sus vértices y no se intersecan con el polígono.
Examine cada conjunto de 4 líneas para determinar cuál produce el cuadrilátero delimitador de área mínima.

ACTUALIZADO: la suposición de que cada lado del cuadrante delimitador pasará a través de al menos 2 vértices es falsa, pero un conjunto de líneas relacionadas puede proporcionar una base para una solución. Como mínimo, cada lado del cuadrante delimitador pasará a través de uno de los vértices utilizados para definir el conjunto único de las líneas que están definidas por 2 vértices y no se intersecan con el polígono.

Creo que el cuadro delimitador orientado debería estar bastante cerca (aunque en realidad es un rectángulo). Aquí está el documento de referencia estándar sobre cajas delimitadas orientadas: el documento de Gottschalk (PDF)

Mire la sección 3 (Ajuste de un OBB).

Creo que un OBB 2D alrededor de los puntos es un buen punto de partida. Eso probablemente dará un ajuste "bueno" (pero no el mejor); Si encuentra que todavía necesita un límite más estrecho, puede extender el ajuste a cuadriláteros.

En primer lugar, debe calcular el casco convexo de sus puntos de entrada. Eso le da menos puntos para tratar y no cambia la respuesta en absoluto.

Me mantendría alejado del método basado en la covarianza al que se hace referencia en el artículo de Gottschalk en otra parte. Eso no siempre da el mejor ajuste, y puede ir muy mal para una entrada muy simple (por ejemplo, un cuadrado).

En 2D, el enfoque de "calipers rotativos" descrito en http://cgm.cs.mcgill.ca/~orm/maer.html debería dar el OBB que mejor se ajuste exactamente. El problema también es fácil de considerar como un problema de minimización 1D:

Para un ángulo dado, gire los ejes x e y en este ángulo. Esto te da dos vectores ortogonales.
Para cada punto, proyectar sobre ambos ejes. Lleve un registro de la proyección mínima y máxima en cada eje.
El área del OBB es (max1-min1) * (max2-min2), y puede calcular fácilmente los puntos del OBB desde el ángulo y las proyecciones mínimas y máximas.
Repita, muestre el intervalo [0, pi / 2] tan fino como desee y realice un seguimiento del mejor ángulo.

El blog de John Ratcliffe ( http://codesuppository.blogspot.com/2006/06/best-fit-oriented-bounding-box.html ) tiene algún código que hace este enfoque de muestreo en 3D; Deberías poder adaptarlo a tu estuche 2D si te quedas atascado. Advertencia : John a veces publica imágenes ligeramente NSFW en sus publicaciones de blog, pero ese enlace en particular está bien.

Si aún no está satisfecho con los resultados después de hacer que esto funcione, podría modificar el enfoque un poco; Hay dos mejoras que puedo pensar:

En lugar de seleccionar ejes ortogonales como se mencionó anteriormente, puede elegir dos ejes no ortogonales. Esto le daría el rombo mejor ajustado. Para hacer esto, básicamente harías una búsqueda 2D sobre [0, pi] x [0, pi].
Utilice el OBB de mejor ajuste como punto de partida para una búsqueda más detallada. Por ejemplo, podría tomar los 4 puntos del OBB, mover uno de ellos hasta que la línea toque un punto y luego repetir para los otros puntos.

Espero que ayude. Perdón por la sobrecarga de información :)

Un algoritmo tacaño

Comience con su polígono convexo. Si bien hay más de 4 puntos, encuentre el par de puntos vecinos que es más barato de consolidar, y consolídelos, reduciendo la cantidad de puntos en su polígono en 1.

Por "consolidar", me refiero a extender los dos bordes en cada lado hasta que se encuentren en un punto, y tomar ese punto para reemplazar los dos.

Por "más barato", me refiero al par para el cual la consolidación agrega la menor cantidad de área al polígono.

Before: After consolidating P and Q: P'' // P____Q / / / / / / / / / / / / / /

Se ejecuta en O (n log n). Pero esto solo produce una aproximación, y no estoy del todo contento con eso. Cuanto mejor sea el algoritmo para producir un agradable pentágono regular, más área deberá consumir la última consolidación.