Buscando para encontrar el rectángulo más grande, por área, en el interior de un polígono

Question

Yo estoy buscando para la impresión de texto en el interior de un polígono, mediante programación. Me gustaría encontrar el rectángulo más grande para colocar el texto dentro del polígono de un sub conjunto de rectángulos, es decir, aquellas orientadas con su eje mayor a lo largo de incrementos de 45°, por ejemplo, de 0°, 45°, 90°, etc.

No estoy 100% seguro de si me he hecho esta pregunta correctamente, pero el punto de esto es conseguir un default de la posición y orientación de un texto dentro de un polígono. Estoy abierto a cualquier atisbo de sugerencias alternativas, pero supongo que sería ideal como un algoritmo para trabajar fuera de este rectángulo.

También estoy consciente de que es posible que a la hora de idear un polígono que haría la mayoría de los algoritmos inútil que se incluya como parte del polígono una extremadamente larga y delgada sección rectangular, lo que resulta en ilegible el texto, si no es posible dar cuenta de esto de alguna manera, estoy bien con asumiendo que esto no va a ocurrir en mi situación, ya que habrá un manual para la posición y la orientación en mi escenario.

EDITAR: Pensando en lo complicado que es esto, podría ser más fácil para eliminar la restricción angular, a continuación, gire y reducir el tamaño del rectángulo a una de esas orientaciones después de calcular como una simplificación. También supongo que la longitud del texto es muy importante, por lo que el algoritmo tiene que ser adaptable a un rectángulo de una relación específica...

Siéntase libre de tirar ideas, estoy feliz de rebote de ida y vuelta con la gente acerca de la mejor manera de hacer esto.

EDIT2: Sugerido por un amigo: Calcular la línea más larga en el interior del polígono, a continuación, utilizarlo como un eje para un rectángulo. Así que voy a enumerar todas las líneas que van a través de 2 vértices hasta que encuentre el más largo, entonces rectangularise cada línea de partida en el más largo, en el rectángulo más grande con las proporciones correctas. A continuación, el más grande de estos debe ser bastante parecido a lo que quiero. Cualquier comentario en este enfoque?

EDIT3: Terminé el dibujo de la "más grande" rectángulo por la subdivisión de mi problema en el área de seguridad en una red de n por n cuadrados (donde n es relativamente grande, aunque es razonable que mi dominio del problema, tamaño), comprobando si las cuatro esquinas estaban todos dentro de la poli. Si se quisiera aumentar el tamaño de la plaza por n, interating esto hasta que estaba a las afueras de la poli, luego de aumentar n longitud sabio y repita el aumento de anchura (el mantenimiento de un registro de la mayor área del rectángulo como me fue) hasta que había encontrado la mayor rectángulo para que el tamaño de la subdivisión. Me gustaría entonces la mitad n y a partir de mi actual rectángulo más grande, repita el proceso. Repetir todo hasta que llegué a un pequeño adecuado valor de n.

Answer 1

Esta es probablemente una exageración, pero si el polígono es convexo y de fijar el eje sobre el que el rectángulo es estar alineado, el problema es de segundo orden de cono programa. Si $x$ es un 2-d vector, cualquier polígono convexo se puede expresar como el conjunto de puntos de satisfacciones $Ax \le b$, donde a es Una matriz y b es un vector. (¿Por qué? cada delimitador de línea es una desigualdad $a_i^T x \le b_i$, por lo que a continuación vamos a $a_i^T$ ser la i-ésima fila de a $A$, e $b_i$ la i-ésima componente de b.)

Así que si $x$ es una de las esquinas del rectángulo, y $\ell,w$ son la longitud y el ancho del rectángulo, el problema es: $$ \begin{eqnarray} \max_{x,\ell, w} \ \ell w \\ Ax \le b, \quad A\left(x + \left[\begin{matrix} 0 \\ w\end{de la matriz}\right] \right) \le b, \quad Un\left(x + \left[\begin{matrix} \ell \\ 0\end{de la matriz}\right] \right)& \le b, \quad Un\left(x + \left[\begin{matrix} \ell \\ w\end{de la matriz}\right] \right)& \le b, \quad \ell,w \ge 0 \end{eqnarray} $$ Luego hay un estándar truco para activar un hiperbólico restricción en un SOCP: $$\left \| \left[\begin{matrix} 2z \\ \ell - w\end{de la matriz}\right] \right\|_2 \le \ell + w \Leftrightarrow z^2 \le \ell w $$ Así que en lugar de la maximización de la $\ell w$ puede incluir la restricción, y maximizar $z$. Si usted no tiene acceso a un SOCP solver es probablemente el más complicado de lo que usted necesita, pero sí se muestra cómo se puede resolver el problema exactamente.