Algoritmo de cuadrilátero de contorno mínimo

Question

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

¿Alguien conoce un algoritmo para encontrar un cuadrilátero de área mínima (cualquier cuadrilátero, no sólo rectángulos)?

Me han remitido a este sitio desde stackoverflow.com ( puesto original ), ya que los chicos de allí no sabían la respuesta a esto...

(PD: Soy programador y no matemático, por lo que agradecería especialmente que me indicaran las implementaciones existentes si las hubiera... Muchas gracias)

Answer 1

Creo que lo que quieres es "Geometric applications of a matrix searching algorithm", Aggarwal et al, Algorithmic 1987, doi:10.1007/BF01840359 . Se basa en un trabajo previo de Aggarwal, Chang y Yap (su referencia [2]) para demostrar que el área mínima que encierra el k-gon de una figura geométrica puede encontrarse en tiempo O(n^2) siempre que k sea constante - lo explican muy brevemente hacia el final de la página 11 de su trabajo (página 205 de la revista).

Answer 2

Me gusta el algoritmo de Monte Carlo sugerido por Carl Smotricz en Stack Overflow, que citaré aquí:

• Para cada ensayo, seleccione al azar p vértices distintos y q lados distintos lados del polígono de forma que p + q = 4.

• Para cada uno de los q lados, construye una línea que pase por los puntos extremos de ese lado de ese lado.

• Para cada uno de los p vértices, construye una línea que pase por ese vértice y con una pendiente asignada al azar.

• Comprueba que las 4 líneas forman efectivamente un cuadrilátero, y que este cuadrilátero contiene (y no intersección) al polígono. Si estas pruebas fallan, no sigas con esta iteración.

• Si el área de este cuadrilátero es el mínimo de todas las áreas vistas hasta ahora, recuerda el área y las coordenadas de los vértices del cuadrilátero.

• Repite un número arbitrario de veces y devuelve el "mejor" cuadrilátero encontrado.

Pero seguro que esto se puede mejorar. En particular, el "mejor" cuadrilátero aquí no está garantizado toque el polígono que intentamos delimitar, y así se puede hacer más pequeño. En particular, parece que hacer conjeturas al azar y luego tratar de "mejorarlas" de alguna manera sería mejor que simplemente hacer conjeturas al azar y desecharlas si no son lo suficientemente buenas.