Determinar si el círculo está cubierto por un conjunto de otros círculos

Question

Suponga que tiene un conjunto existente de los círculos $\mathcal{C} = {C_1, .., C_n}$ cada uno con un radio fijo $r$ pero variando el centro de coordenadas. A continuación, se le da un nuevo círculo de $C_{n+1}$ con el mismo radio $r$ como el anterior círculos, pero con un nuevo centro de coordenadas.

¿Cómo se puede determinar si el área cubierta por la $C_{n+1}$ está totalmente cubierto por $\mathcal{C}$?

Cómo hacerlo si los círculos se pueden tener diferentes radios?

Nota: no pude sin embargo, el trabajo fuera una buena solución matemática para esto. Viniendo de ciencias de la computación, la mejor que se me ocurrió es la solución de este en la fuerza bruta usando algún tipo de Monte Carlo de muestreo, es decir, dibujar un gran número de puntos al azar en el área de la $C_{n+1}$ y, a continuación, comprobar para cada punto si es cerrado por al menos un círculo en $\mathcal{C_{intersecting}}$ (subconjunto de $\mathcal{C}$ con los círculos que están dentro de$2r$$C_{n+1}$).

Answer 1

Es fácil comprobar si hay alguna parte en todas las del disco de destino que está cubierto -- que es sólo una cuestión de comparar las distancias con las sumas de los radios. Así que se supone que hay cierta superposición.

Ahora, si todavía hay también algunos no cubiertos dentro de la zona del disco de destino, entonces el límite de la cobertura total debe pasar a través del disco de destino. Que límites consiste, en casi todas partes, de los puntos que están en la periferia de uno de los discos originales y no cubiertos por ningún otro de los discos originales. (Estoy asumiendo que no hay duplicados entre los discos originales).

Por lo tanto, usted puede ir a través de la $C_i$'s uno por uno, y comprobar (a) rango de ángulos de su límite está cubierto por el disco de destino y, a continuación, para cada una de las $C_j$ $i\ne j$ restar el ángulo de intervalo en $C_i$'s de límite que no está cubierto por $C_j$. Si no hay nada a la izquierda cuando haya terminado, usted ha encontrado un punto en la frontera de la unión, que es dentro de $C_{n+1}$.

Esto le da un $O(n^2\log n)$ algoritmo. Cada ángulo de intervalo es fácil de encontrar desde distancias, radios y las posiciones relativas de uso de la trigonometría básica.