Encontrar un rectángulo alineado con el eje dentro de un polígono

Question

Estoy buscando un buen algoritmo para encontrar un rectángulo alineado con el eje dentro de un polígono (no necesariamente convexo). Un rectángulo máximo sería agradable, pero no es necesario; cualquier algoritmo que pueda encontrar un rectángulo "bastante bueno" estaría bien.

El polígono también puede tener agujeros, pero cualquier sugerencia a algoritmos que solo funcionen para polígonos convexos o simples también sería útil.

En mi implementación, las pruebas de intersección para los lados son bastante baratas, pero las pruebas de "punto en polígono" son caras, por lo que idealmente deberían minimizarse.

Answer 1

Solo como referencia, hasta ahora todo lo que tengo es fuerza bruta: haga una cuadrícula, y para puntos en la cuadrícula, si están dentro del polígono, haga una serie de rectángulos expandiendo cada esquina o lado sucesivamente hasta que golpea un lado. Entonces solo elige el más grande.

La optimización más simple (y muy efectiva) es comprobar si un punto de la cuadrícula está en el polígono una vez que ha comprobado que no está contenido en uno de los rectángulos ya construidos, ya que la verificación 'punto en rectángulo' está ardiendo rápido.

Por razones obvias, esto es bastante lento e inexacto, por no hablar poco elegante :)

Answer 2

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
tiene un algoritmo para convexa, las referencias podrían ser digno de una mirada.
no estoy seguro de si podría extenderse a no convexo sin embargo.

Answer 3

Una solución es dividir el polígono cóncavo en segmentos convexos y luego usar el enlace de cobbal.

Como realmente tiene dos problemas fundamentales diferentes, ¿ha considerado otras alternativas al problema de la prueba de aciertos, como usar un árbol BSP? Puede acelerar aún más colocando una grilla sobre el poli y construyendo un árbol BSP para cada cuadrícula. ¿O un árbol kd con un borde como máximo en cada hoja?

Editar: Voy a ellaborate en el kd-árbol (por aburrimiento, aunque podría ser de alguna utilidad a nadie):

KD-árboles tienen las siguientes propiedades:

1. Son binarios
2. Cada nodo no hoja divide el espacio a lo largo de un plano perpendicular a un eje, un lado por niño. P.ej. la raíz divide el espacio en x < x0 yx> = x0
3. Los niveles de los árboles se dividen en diferentes ejes, p. ej. nivel 0 (root) divide perpendicular a X, nivel 1 -> Y, etc.

Para utilizar esta para el polígono golpeó detección, construir el árbol como sigue:

1. Escoja un vértice para dividir a lo largo. (Preferiblemente en algún lugar cerca del medio para un árbol equilibrado).
2. Dividir otros vértices en dos conjuntos, uno para cada lado de la división. El vértice anterior no entra en ninguno de los conjuntos.
3. Coloque los bordes en los juegos también. Cualquier borde que interseca la línea divisoria entra en ambos conjuntos.
4. Construya hijos recursivamente de los grupos anteriores.

Si el vértice dividido se elige de forma adecuada, el árbol debe tener una profundidad próxima al registro (N), donde N es el número de vértices. Cada nodo de hoja tendrá como máximo un borde que lo atraviesa. Para hacer la detección de aciertos:

1. Encuentra la hoja en la que cae el punto.
2. Si hay un borde en la hoja, compárelo. De lo contrario, debería ser obvio si el punto está dentro o fuera (guarde esta información en dichas hojas al construir el árbol).

Answer 4

¿Qué tal el uso del recorte de orejas? Puede encontrar el rectángulo alineado al eje máximo en cada triángulo. Entonces podrías intentar unir triángulos y volver a calcular tus rectángulos.