algorithm - poligonos - polígono convexo de 5 lados
El círculo más grande dentro de un polígono no convexo (5)
¿Cómo puedo encontrar el círculo más grande que pueda caber dentro de un polígono cóncavo?
Un algoritmo de fuerza bruta está bien siempre que pueda manejar polígonos con ~ 50 vértices en tiempo real.
La clave para resolver este problema es hacer primero una observación: el centro del círculo más grande que cabrá dentro de un polígono arbitrario es el punto que es:
- Dentro del polígono y
- Lo más lejos posible de cualquier punto en los bordes del polígono.
¿Por qué? Porque cada punto en el borde de un círculo es equidistante de ese centro. Por definición, el círculo más grande tendrá el radio más grande y tocará el polígono en al menos dos puntos, por lo que si encuentras el punto más alejado del polígono, has encontrado el centro del círculo.
Este problema aparece en la geografía y se resuelve iterativamente a cualquier precisión arbitraria. Se llama el problema de los polos de inaccesibilidad. Ver Polos de inaccesibilidad: un algoritmo de cálculo para los lugares más remotos de la Tierra .
El algoritmo básico funciona así:
- Defina R como una región rectilínea de (x min , y min ) a ( xmax , ymax );
- Divida R en una cantidad arbitraria de puntos. El documento usa 21 como una heurística (es decir, divide la altura y el ancho por 20);
- Clip cualquier punto que esté fuera del polígono;
- Para el resto, encuentre el punto que esté más alejado de cualquier punto del borde;
- A partir de ese punto, defina una nueva R con intervalos e intervalos más pequeños y repita desde el paso 2 para obtener cualquier respuesta de precisión arbitraria. El papel reduce R por un factor de la raíz cuadrada de 2.
Una nota, Cómo probar si un punto está dentro del polígono o no: la solución más simple para esta parte del problema es lanzar un rayo a la derecha del punto. Si cruza un número impar de bordes, está dentro del polígono. Si es un número par, está afuera.
Además, en cuanto a la prueba de la distancia a cualquier borde, hay dos casos que debe tener en cuenta:
- El punto es perpendicular a un punto en ese borde (dentro de los límites de los dos vértices); o
- No lo es
(2) es fácil. La distancia al borde es el mínimo de las distancias a los dos vértices. Para (1), el punto más cercano en ese borde será el punto que interseca el borde en un ángulo de 90 grados comenzando desde el punto que está probando. Vea la distancia de un punto a un rayo o segmento .
Resumen: En teoría, esto se puede hacer en el tiempo O (n). En la práctica, puedes hacerlo en el tiempo O (n log n).
Diagramas de Voronoi generalizados.
Si considera los vértices y los bordes del polígono como un conjunto de sitios y tesela el interior en las "celdas vecinas más cercanas", obtendrá el diagrama de Voronoi (generalizado). El diagrama de Voronoi consiste en nodos y bordes que los conectan. El espacio libre de un nodo es la distancia a sus caras de polígono definitorias.
(Aquí el polígono incluso tiene agujeros, el principio todavía funciona).
La observación clave ahora es que el centro del círculo máximo inscrito toca tres caras (vértices o bordes) del polígono, y ninguna otra cara puede estar más cerca. Entonces el centro tiene que estar en un nodo Voronoi, es decir, el nodo con la mayor separación.
En el ejemplo anterior, el nodo que marca el centro del círculo máximo inscrito toca dos bordes y un vértice del polígono.
El eje medial, por cierto, es el diagrama de Voronoi con aquellos bordes de Voronoi eliminados que emanan de los vértices reflejos. Por lo tanto, el centro del círculo inscrito máximo también se encuentra en el eje medial.
Fuente: Un artículo de blog mío que trata sobre las generalizaciones de los círculos inscritos máximos en algún momento. Allí puedes encontrar más sobre los diagramas de Voronoi y su relación con los círculos inscritos máximos.
Algoritmos e implementaciones.
Podrías calcular el diagrama de Voronoi. El algoritmo O (n log n) del caso más desfavorable para puntos y segmentos está dado por Fortune, un algoritmo de línea de barrido para diagramas de Voronoi , SoCG''86. Held publicó el paquete de software Vroni con una complejidad de tiempo O (n log n) esperada, que realmente calcula el círculo inscrito máximo también. Y parece haber una implementación en boost , también.
Para polígonos simples (es decir, sin agujeros), un algoritmo de tiempo óptimo que se ejecuta en O (n) tiempo se debe a Chin et al., Hallar el eje medio de un polígono simple en tiempo lineal , 1999.
Fuerza bruta.
Sin embargo, como dijiste que estás bien con un algoritmo de fuerza bruta: ¿qué tal si simplemente probamos todos los trillizos de sitios (vértices y bordes)? Para cada tripleta se encuentran nodos Voronoi candidatos, es decir, loci equidistantes a los tres sitios y comprobar si cualquier otro sitio se cruza con el círculo inscrito máximo candidato. Si hay una intersección, descarta al candidato. Tome lo mejor que pueda encontrar sobre todos los trillizos.
Ver el capítulo 3 en mi tesis de maestría sobre más detalles sobre cómo calcular loci equidistantes para tres sitios.
Un algoritmo O (n log (n)):
- Construya el diagrama de Voronoi de los bordes en P. Esto se puede hacer con, por ejemplo, el algoritmo Fortunes .
- Para nodos Voronoi (puntos equidistantes a tres o más bordes) dentro de P;
- Encuentra el nodo con la distancia máxima a los bordes en P. Este nodo es el centro del círculo máximo inscrito.
Un algoritmo O (n log X), donde X depende de la precisión que desee.
Búsqueda binaria para el radio R más grande para un círculo:
En cada iteración, para un radio dado r, presione cada borde E, "hacia adentro" por R, para obtener E ''. Para cada borde E '', defina el medio plano H como el conjunto de todos los puntos "dentro" del polígono (usando E'' como el límite). Ahora, calcule la intersección de todos estos semiplanos E '', lo que podría hacerse en el tiempo O (n). Si la intersección no está vacía, si dibuja un círculo con radio r usando cualquier punto en la intersección como el centro, estará dentro del polígono dado.
En caso de que alguien esté buscando una implementación práctica, diseñé un algoritmo más rápido que resuelve este problema para una precisión dada y lo convertí en una biblioteca de JavaScript. Es similar al algoritmo de cuadrícula iterativo descrito por @cletus, pero está garantizado para obtener el óptimo global, y también es 20-40 veces más rápido en la práctica.
Compruébelo: https://github.com/mapbox/polylabel