Intersección circular con algoritmo de línea de barrido

Desafortunadamente, todavía no soy tan fuerte en entender el algoritmo de línea de barrido . Todos los documentos y libros de texto sobre el tema ya se leen, sin embargo, la comprensión aún está muy lejos. Solo para aclararlo, trato de resolver tantos ejercicios como pueda. Pero, las tareas realmente interesantes e importantes siguen siendo un desafío para mí.

El siguiente ejercicio lo encontré en las notas de clase de Intersección de segmento de línea del omnipotente Jeff Erickson.

Ejercicio 2. Describa y analice un algoritmo de línea de barrido para determinar, dados círculos en el plano, si dos se cruzan, en el tiempo . Cada círculo está especificado por su centro y su radio, por lo que la entrada consta de tres matrices y . Tenga cuidado de implementar correctamente las primitivas de bajo nivel. $n$ $O(n \log n)$ $X[1.. n], Y [1.. n]$ $R[1.. n]$

Intentemos hacer una cosa compleja más fácil. ¿Qué sabemos sobre la intersección de círculos? Qué análogo se puede encontrar con la intersección de líneas. Dos líneas podrían cruzarse si son adyacentes, ¿qué propiedad deberían tener dos círculos para cruzarse? Sea la distancia entre el centro de los círculos, y centros de los círculos. Considere algunos casos: $d$ $r_{0}$ $r_{1}$

Caso 1: si entonces no hay soluciones, los círculos están separados. $d > r_{0} + r_{1}$
Caso 2: Sientonces no hay soluciones porque un círculo está contenido dentro del otro. $d < |r_{0} - r_{1}|$
Caso 3: Si y entonces los círculos son coincidentes y hay un número infinito de soluciones. $d = 0$ $r_{0} = r_{1}$

Entonces, parece que las condiciones de intersección están listas, por supuesto, pueden ser condiciones incorrectas. Corrija si es así.

Algoritmo. Ahora necesitamos encontrar algo en común entre dos círculos que se cruzan. Con la intersección de análogo a línea, necesitamos tener una condición de inserción y una condición de eliminación en la cola de eventos. Digamos que el punto de evento es la coordenada x del primer y último punto que toca la línea de barrido vertical. En el primer punto, insertamos el círculo en el estado y verificamos la intersección (se mencionan 3 casos de verificación anteriormente) con los círculos más cercanos, en el último punto eliminamos el círculo del estado .

Parece que es suficiente para el algoritmo de línea de barrido. Si hay algo mal, o puede haber algo que debería hacerse de manera diferente, siéntase libre de compartir sus pensamientos con nosotros.

Anexo :

Inserto un círculo cuando la línea de barrido vertical toca el círculo por primera vez, y elimino un círculo del estado cuando la línea de barrido lo toca por última vez. La verificación de intersección debe hacerse para el círculo anterior más cercano. Si agregamos un círculo al estado y ya había otro círculo que agregamos antes y todavía estaba allí, por lo tanto, el círculo anterior no estaba "cerrado", por lo que podría haber una intersección.

algorithms computational-geometry com
fuente

omnipotente [cita requerida]

JeffE

@com ¿qué quieres decir con "círculo anterior más cercano"?

Joe

¿Supongo que statusmantiene los círculos que actualmente se cruzan con la línea de barrido? Suponga que actualmente tiene 100 círculos statusy procesa un evento de inserción e inserta el círculo 101. ¿Cuántos círculos compara para verificar la intersección? ¿Cómo eliges qué círculos comparar?

Joe

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

Respuestas:

Definitivamente estás en el camino correcto. La gran pregunta es: cuando inserta un círculo, ¿en qué otros círculos verifica la intersección? ¿Cómo se realiza esta verificación?

En el caso de intersección de segmento de línea, los segmentos de línea en cualquier coordenada x están totalmente ordenados. (Puede enumerarlos de la coordenada Y más baja a la más alta). Por lo tanto, puede mantener los segmentos de línea en un árbol de búsqueda binario, y cuando agrega un nuevo segmento, solo necesita averiguar dónde pertenece en el árbol de búsqueda binario y verificar si hay eventos de intersección en sus vecinos.

En el caso de los círculos, no está claro de inmediato qué círculos verificar. Si su respuesta es "todas", entonces su algoritmo necesita algo de trabajo.

¿Puedes encontrar una manera de representar los círculos para que estén totalmente ordenados, como lo son los segmentos de línea?

Intenta representar los círculos como dos semicírculos. Cada evento de inserción es en realidad dos eventos: inserte la mitad superior e inserte la mitad inferior.

Joe
fuente

Desafortunadamente no entiendo la idea de semicírculos, tal vez consideres semicírculo como una unidad mínima de círculo que se puede intersecar (3 casos de intersección: la intersección está en el semicírculo superior, o en la inferior, o en ambos). Al principio, todos los círculos están ordenados por la coordenada x de sus límites izquierdo y derecho. Por lo tanto, no debemos considerar x coordinado en estado , porque todos los círculos ya vienen en x orden de coordenadas. Por lo tanto, parece más lógico considerar la coordenada y del centro (del semicírculo), o cualquier combinación de y y radios. ¿Su opinión?

com

@com Necesita un punto central y un radio para determinar si dos círculos se cruzan, como lo hizo en sus propias verificaciones de intersección. Solo la coordenada y y el radio por sí solos no especifican completamente el límite del círculo. Parece que hay algo fundamental sobre los algoritmos de línea de barrido que no está entendiendo, pero es difícil para mí decir qué es.

Joe

Podría pensar en este enfoque análogo al barrido de Bentley Ottmann que se ejecuta en tiempo O ((n + k) logn).

Podría reducir el problema de la intersección circular a la intersección del segmento de línea. Consideraré el diámetro vertical paralelo al eje Y para cada uno de los círculos. El algoritmo utilizará una línea horizontal que barre el plano de abajo hacia arriba.

Ahora tenemos el punto final superior, el punto final inferior para cada uno de los círculos. Además, tenemos que modificar el predicado Intersección para decir que dos segmentos se cruzan si y solo si la línea de barrido atraviesa ambos círculos en un punto.

Dado que el problema de la intersección de la línea puede resolverse en el tiempo O ((n + k) logn), el mismo límite sigue también para la intersección circular.

Estoy bastante convencido de que esto funcionaría, pero si ustedes pudieran señalar cualquier caso que esto no manejará en general, háganmelo saber.

TheGT
fuente