¿Cómo encontrar el rectángulo de área máxima dentro de un polígono convexo?

21

En esta publicación, buscamos algoritmos / ideas sobre cómo encontrar el rectángulo de área máxima dentro de un polígono convexo .

En la siguiente figura, los números son las áreas de los rectángulos ajustados. Como se muestra, un rectángulo deseado puede variar en cada dimensión y puede estar en cualquier ángulo.

Editar:

No tenemos una idea clara de cómo lidiar con el problema mencionado, así que preguntamos aquí. Sin embargo, suponemos que el rectángulo de área máxima puede ser uno de los que tiene un borde alineado (por supuesto, no necesariamente el mismo borde de longitud) con un borde del polígono.

ingrese la descripción de la imagen aquí

Desarrollador
fuente
1
¿Podría especificar qué software está utilizando? Además, publique su trabajo hasta aquí, o el enfoque general que ha elaborado para resolver esto. Quizás alguien pueda mejorar lo que ya has hecho. En mi experiencia, eso dará como resultado respuestas mucho más útiles que simplemente publicar una pregunta "de la nada".
Martin
1
Muy relacionado: gis.stackexchange.com/questions/22895/… .
whuber
@Martin Software: la programación Pythonse realizará Fortransi es necesario. Suponemos que, según nuestra publicación anterior aquí también mencionada anteriormente, whuberque podría ser un rectángulo con un borde en común con el polígono sería una respuesta.
Desarrollador
1
Su problema es realmente interesante, y creo que logré encontrar un algoritmo de resolución aquí y aquí .
nickves
1
@nickves Gracias por los enlaces. ¿Podría poner esta información como respuesta con una pequeña explicación de los algoritmos? Será potencialmente una buena respuesta para ser aceptado.
Desarrollador

Respuestas:

4

Algunas notas demasiado grandes para poner en un comentario (aunque esto no sugiere un algoritmo obvio):

La línea de perforación (EDITADA) : al menos dos vértices del rectángulo de área máxima deben estar en el límite del polígono (es decir, a lo largo de un borde o en un vértice). Y si el rectángulo de área máxima no es un cuadrado, entonces al menos tres vértices deben estar en el límite del polígono.

Me lo probé en cuatro pasos:

Nota # 1 : Al menos un vértice del rectángulo de área máxima siempre estará en el límite del polígono. Esto es bastante obvio, pero una prueba podría ser así (por contradicción): suponga que tiene un rectángulo "máximo" sin vértice en el límite del polígono. Eso significa que habría al menos un pequeño espacio alrededor de cada uno de sus vértices. Así que podrías expandir un poco tu rectángulo, contradiciendo su máxima.

Nota # 2 : Al menos dos vértices del rectángulo de área máxima siempre estarán en el límite del polígono. Una prueba podría ser así (nuevamente por contradicción): suponga que tiene un rectángulo "máximo" con solo un vértice en el límite (garantizado por la Nota # 1). Considere los dos bordes no adyacentes a ese vértice. Como sus puntos finales NO están en el límite, hay un pequeño espacio alrededor de cada uno. Por lo tanto, cualquiera de esos bordes podría "extruirse" un poco, expandiendo el área del polígono y contradiciendo su máxima.

Nota # 3 : Hay dos vértices diagonalmente opuestos del rectángulo de área máxima que se encuentran en el límite del polígono. (Sabemos por la Nota # 2 que hay al menos dos, pero no necesariamente que están uno frente al otro.) Pero nuevamente por contradicción, si los únicos dos vértices de límite eran adyacentes, entonces el borde opuesto (ninguno de cuyos vértices están en el límite) podrían extruirse un poco, aumentando el área del rectángulo y contradiciendo su máxima.

Nota # 4 : (EDITADO) Si el rectángulo de área máxima no es un cuadrado, entonces tres de sus vértices se ubicarán en el límite del polígono.

Para probar, suponga que ese no es el caso, es decir, que el rectángulo de área máxima no es un cuadrado, sino que solo dos de sus vértices están en el límite del polígono. Mostraré cómo construir un rectángulo más grande, contradiciendo la maximidad.

Llama a los vértices del rectángulo A, B, C, y D. Sin pérdida de generalidad, suponga que By Dson los dos que están en el límite del polígono. Dado Ay Cse encuentran en el interior del polígono, hay un margen de maniobra que les rodea (representada con círculos alrededor Ay Cen la siguiente imagen). Ahora dibuje un círculo alrededor del rectángulo y deslice los puntos Ay Cun poco alrededor del círculo en la misma cantidad (para hacer A'y C', como se muestra a continuación) para que el nuevo rectánguloA'BC'DEs más cuadrado que el rectángulo original. Este proceso crea un nuevo rectángulo que también está dentro del polígono original y tiene un área más grande. Esto es una contradicción, entonces la prueba está hecha.

Construyendo un nuevo rectángulo

Para creer esa prueba, debes convencerte de que el área de un rectángulo inscrito en un círculo aumenta a medida que se vuelve "más cuadrada" (es decir, la diferencia entre las longitudes de los bordes se hace más pequeña). También necesita que el polígono sea convexo para que las nuevas líneas estén todas dentro de él. Y probablemente hay otros pequeños detalles que se esconden debajo de la alfombra, pero estoy bastante seguro de que todos funcionan.

csd
fuente
Nota # 4 es sospechoso, porque "meneando" los otros dos vértices crearán no rectángulos.
whuber
Cierto. Sin embargo, su visualización del cuarto ejemplo no es del todo correcta (si 2 vértices están en el límite del polígono, no puede estirarlo más). Sin embargo, no puedo encontrar exactamente cómo explicarlo (intenté escribir un comentario pero me puse demasiado desordenado), pero confío en que tienes razón.
Saryk
Creo que hay contraejemplos para tener en cuenta # 4. Sin embargo, los que he encontrado toman algunos cálculos involucrados para mostrar; la más simple es la perturbación de un hexágono irregular (un cuadrado con dos esquinas opuestas ligeramente cortadas).
whuber
Acordó que la Nota # 4 es sospechosa. Echaré un vistazo más de cerca esta noche y lo arreglaré o lo eliminaré.
csd
+1 Esa es una buena resolución de la dificultad. Gracias por la edición!
whuber
3

He hecho un bosquejo muy rápido y horrible sobre su nota verde en la pregunta. No pude publicarlo como comentario, así que tuve que escribir una respuesta, incluso si no es una.
Creo que en la imagen a continuación tenemos un rectángulo de área máxima (no perfecto, es solo un boceto hecho en Paint para dar una idea), y no creo que pueda encontrar uno más grande que tenga un lado común con el bordes del polígono negro ...
Sin embargo, puedo estar equivocado, en ese caso tienes todas mis disculpas.
Bosquejo rápido que hice en Paint

Saryk
fuente
3
Buen punto (+1). Sin embargo, hay un contraejemplo mucho más simple: considere el problema de inscribir un rectángulo de área máxima dentro de un octágono regular. Es fácil de ver (y fácil de probar al encontrar primero un cuadrado máximo dentro del círculo del octágono) que las esquinas de la solución coinciden con vértices alternos del octágono y que esta solución es sustancialmente más grande que cualquier rectángulo inscrito con borde alineado.
whuber
En realidad (solo tengo una gran duda en este momento), el rectángulo más pequeño externo (los de esta publicación ) de este polígono no tiene la misma orientación que uno de los lados, ¿verdad? (Lo vería con la misma orientación que mi rectángulo rojo)
Saryk
3
Ese polígono no es convexo, por cierto. La pregunta original se restringe a los polígonos convexos.
csd
2
@csd Ese es un gran punto, pero Saryk sigue siendo correcto, como lo muestra mi contraejemplo. Saryk, no hay problema con el rectángulo delimitador de área mínima: es fácil demostrar (rigurosamente) que debe incluir un lado del casco convexo. Creo que el rectángulo con el área máxima inscrita (de un polígono convexo) solo necesita tener dos vértices tocando el límite, no más.
whuber
2

La mayoría de los otros algoritmos encuentran el rectángulo rectilíneo de área máxima inscrito en un polígono convexo, y tienen una complejidad de O(log n). No creo que adivine que el polígono de área máxima está alineado con uno de los lados es correcto, porque todo lo que necesitaría hacer es rotar los ntiempos del polígono , lo que resulta en una complejidad de O(n log n), y en mi breve investigación no pude encontrar algo que diga que fue tan fácil.

Sin embargo, el artículo Rectángulos inscritos más grandes en polígonos convexos de Knauer, et. al., describe un algoritmo de aproximación que lo acercará a la respuesta correcta.

Según tengo entendido, el algoritmo se basa en uno de los polígonos de área máxima alineados a los ejes conocidos, y luego toma muestras aleatoriamente de puntos dentro del espacio de polones, genera múltiples ejes a partir de esas muestras aleatorias, itera sobre esos ejes y aplica el eje algoritmo alineado a cada uno, y luego devuelve el rectángulo más grande en ese conjunto.

lreeder
fuente
¿Hay quizás un error tipográfico en la primera oración? ¡No puede haber un algoritmo O (log (n)) porque simplemente leer en las coordenadas es una operación O (n)!
whuber
El enlace está muerto
peligroso el
1
@dangerousdave - Encontré un enlace alternativo por el tiempo que dure ...
lreeder