Encontrar un rectángulo delimitado dentro de un polígono cóncavo/convexo

Question

Estoy buscando un método para encontrar un rectángulo alineado con el eje dentro de un polígono cóncavo o convexo.

He estado buscando en la web, las soluciones más cercanas que pude encontrar solo caben en un polígono convexo, y no uno cóncavo. Por ejemplo -

Finding an axis-aligned rectangle inside a polygon

Para ser honesto, no soy un gran genio de las matemáticas, por lo que preferiría encontrar ejemplos de código o una biblioteca de código, pero supongo que podría manejar un poco de matemática por mí mismo, o encontrar a alguien para ayudarme con eso

Sería muy bueno si la solución podría ser en Java también, pero tal vez soy demasiado codicioso: P

Editar: En respuesta al comentario de Russell, que estoy añadiendo un poco más de información.

El rectángulo delimitado debe ser lo más grande posible. El rectángulo está destinado a contener texto dentro de él. 1 a 4 palabras como máximo, con soporte para el ajuste de texto. Entonces, si, por ejemplo, fuera demasiado delgado, colocaría el texto verticalmente en lugar de horizontalmente. Por lo tanto, para la relación de aspecto, supongo que debe ser suficiente para contener de 1 a 4 palabras, ya sea vertical u horizontalmente con el ajuste de palabras. Puedo cambiar el tamaño del texto si el rectángulo es pequeño, pero preferiblemente el texto debe ser lo más grande posible.

Otro requisito que sería bueno tener sería que si la orientación general del polígono es diagonal y el texto se ajustaría mucho mejor cuando está orientado diagonalmente, entonces el rectángulo no necesariamente se alinearía con el eje 'pero en su lugar, estar alineado con las líneas diagonales del polígono. Supongo que esta demanda está haciendo que esto sea realmente complicado, pero si ustedes piensan que es posible, ¡sería genial!

Creo que he cubierto todos los requisitos ahora. : P

Gracias!

Answer 1

Como quiera hacer esto para el texto, asumiré que la velocidad es importante, la precisión es menos importante. Sugiero esto, entonces:

1. Lugar del polígono en una cuadrícula con células proporcionales a las dimensiones de texto.
2. Eliminar celdas en el límite usando Bresenham's line algorithm..
3. eliminar las células fuera de las células de contorno (por trabajar desde los bordes de la rejilla hacia adentro.
4. Encontrar el rectángulo máxima en las células restantes, por ejemplo el método mostrado here.

Ver también Puzzle: Find largest rectangle (maximal rectangle problem).

EDITAR: Acabo de notar la solicitud de que este algoritmo se ajuste si el polígono está orientado en ángulo. Mi sugerencia es encontrar el principle axes del polígono para verificar la orientación, rotarlo para alinear el eje dominante con el eje x, y aplicar el algoritmo anterior.

Además, quiero señalar que "eliminar una celda" realmente solo significa configurar un bit en una matriz 2D que representa las celdas de la grilla.

Answer 2

Una vez implementado un sistema similar de una manera realmente kludgey simplemente haciendo una búsqueda a través de posibles rectángulos y usando Shape.contains() en ellos. Fue algo lento, tal vez 1 para el diseño de la dirección de Gettsburg en un óvalo, pero útil para texto estático y para texto pequeño en formas simples.

Si le interesa, puede descomprimir el archivo jar here y mirar TextWrappingLayout. Probablemente sea mucho más complicado de lo que necesitaría, porque en lugar de colocarlo en un solo rectángulo, intenta colocar cada línea lo más cerca posible, pero puede ver la idea básica.