Círculo más grande dentro de un polígono no convexo

Question

¿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.

Answer 1

La clave para resolver este problema primero es hacer una observación: el centro del círculo más grande que quepa dentro de un polígono arbitrario es el punto que es:

1. dentro del polígono; y
2. Más alejado 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 Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth.

El algoritmo básico funciona así:

1. Definir R como una región rectilínea de (x _min, y _min) a (x _max, y _max);
2. Divida R en un número arbitrario de puntos. El documento usa 21 como una heurística (es decir, divide la altura y el ancho por 20);
3. Recorte cualquier punto que esté fuera del polígono;
4. Para el resto, encuentre el punto más alejado de cualquier punto del borde;
5. 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 a 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.

También, en lo que prueba la distancia a cualquier borde hay dos casos es necesario considerar:

1. El punto es perpendicular a un punto en que el borde (dentro de los límites de los dos vértices); o
2. 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. Ver Distance of a Point to a Ray or Segment.

Answer 2

Un O (n log (n)) algoritmo:

1. construir el Voronoi Diagram de los bordes en P. Esto se puede hacer con, por ejemplo, Fortunes algorithm.
2. Para nodos Voronoi (puntos equidistantes a tres o más bordes) dentro de P;
3. Encuentra el nodo con la distancia máxima a los bordes en P. Este nodo es el centro del círculo máximo inscrito.

Answer 3

Algoritmo O (n log X), donde X depende de la precisión que desee.

La búsqueda binaria para mayor radio R por un círculo:

En cada iteración, para un determinado radio r, empuje 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.

Answer 4

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 convierte 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

Answer 5

Resumen: En teoría, esto se puede hacer en 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. La autorización 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. Por lo tanto, el centro debe ubicarse 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 los 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: A blog article mía que se ocupa de las generalizaciones de 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 & implementaciones.

En realidad, se puede calcular el diagrama de Voronoi. El algoritmo O (n log n) del caso más desfavorable para puntos y segmentos está dado por Fortune, . Algoritmo de línea de barrido para los diagramas de Voronoi, SoCG'86. Held publicó el paquete de software Vroni con una complejidad de tiempo O (n log n) esperada, que en realidad calcula también el círculo máximo inscrito. 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) de tiempo se debe a Chin et al., Finding the Medial Axis of a Simple Polygon in Linear Time, 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 ganadores de Voronoi, es decir, loci equidistantes para los tres sitios y se comprueba 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.

Consulte el capítulo 3 en mi Master thesis para obtener más información sobre la computación de loci equidistantes para tres sitios.