Algoritmo de Bentley-Ottmann

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 13 de marzo de 2020; la verificación requiere 1 edición .

El algoritmo de Bentley-Ottmann (1979) permite encontrar todos los puntos de intersección de los segmentos de línea recta en el plano . Utiliza el método de barrido de línea [1] (barrido de línea recta [2] , movimiento de línea recta [3] , exploración de línea [4] , barrido de línea ) . El método utiliza una línea recta de barrido vertical que se mueve de izquierda a derecha, mientras que los segmentos que intersecta en una coordenada dada , se pueden ordenar por la coordenada , por lo que se pueden comparar entre sí (cuál es más alto, cuál es más bajo). Esta comparación se puede realizar, por ejemplo, mediante la ecuación de una recta que pasa por dos puntos (los segmentos vienen dados por sus dos extremos): , donde , y , son las coordenadas del primer y segundo punto del segmento, respectivamente. La línea recta de barrido se mueve a lo largo de los llamados puntos de evento (extremos izquierdo y derecho de los segmentos, así como los puntos de intersección de los segmentos). Después del punto de intersección, los segmentos deben intercambiarse, ya que, por ejemplo, el más alto de los segmentos que se cruzan después del punto de intersección se convierte en el más bajo. El siguiente algoritmo no está diseñado para el caso en que dos segmentos se cruzan en más de un punto. $X$ $y$ $\left(x - x_1 \right)/ \left(x_2 - x_1 \right) = \left(y - y_1 \right)/ \left(y_2 - y_1 \right)$ $x_{1}$ $y_1$ $x_{2}$ $y_2$

NB Una línea de barrido también se puede representar como una línea horizontal que se mueve de arriba hacia abajo a lo largo de la coordenada , y los segmentos que la cruzan se pueden comparar a lo largo de la coordenada . $y$ $X$

Procesamiento de segmentos verticales

Hay un problema con el segmento vertical en el sentido de cómo compararlo arriba/abajo con los segmentos que se cruzan. Para hacer esto, podemos, por ejemplo, suponer que si el punto de intersección de los segmentos vertical y no vertical está por debajo de la coordenada actual del punto del evento, entonces el segmento vertical es más alto, si el punto de intersección es más alto que el actual. coordenada del punto del evento, entonces el segmento vertical se considera debajo del que lo cruza. Si la coordenada actual es igual a la coordenada del punto del evento, entonces al eliminar un segmento, considere que el segmento vertical es más bajo, mientras lo inserta, suponga que es más alto. $y$ $y$ $y$ $y$

Plaza de la memoria

En el peor de los casos, cuando, por ejemplo, todos los segmentos que se cruzan entre sí forman una cuadrícula rectangular, habrá puntos de intersección que será necesario almacenar. Para evitar el uso del cuadrado de memoria en el algoritmo, es posible eliminar el punto de intersección de los segmentos que dejan de ser adyacentes temporalmente en una posición determinada de la línea de barrido. Estos puntos aún se encontrarán nuevamente en los pasos posteriores del algoritmo, cuando los segmentos dados vuelvan a ser adyacentes (Pec, Sherir 1991). $O \izquierda(n^2 \derecha)$

Algoritmo

El pseudocódigo a continuación utiliza:

Q es una estructura de datos dinámica sin repeticiones con un tiempo logarítmico para buscar, insertar, eliminar puntos de eventos y encontrar el elemento mínimo (por ejemplo, árbol rojo-negro , árbol 2-3 ).
T es una estructura de datos dinámica sin repeticiones con un tiempo logarítmico para buscar, insertar, eliminar segmentos. Almacena todos los segmentos que se cruzan con la línea de barrido (por ejemplo, árbol rojo-negro, árbol 2-3).
q - punto de evento.
newq - acaba de encontrar el punto de intersección de los segmentos, el punto del evento.
L(q) es el conjunto de segmentos cuyo extremo izquierdo es q (para segmentos verticales, el extremo inferior se considera el extremo izquierdo).
R(q) es el conjunto de segmentos cuyo extremo derecho es q.
I(q) es el conjunto de segmentos que se cortan en q.

segmentosIntersecciones(puntos[]) 1) Se inicializan Q y T. En Q se introducen todos los extremos de los segmentos ordenados por la coordenada x, y si los dos puntos coinciden, luego, el punto final izquierdo del segmento se coloca delante del punto final derecho. Si solo coincide x, entonces el punto con la y más pequeña es el más pequeño. V ← ∅ 2) mientras Q != ∅ q ←mín(Q); procesoPunto(q); procesoPunto(q) 1) Encuentra en Q todos los segmentos que contengan q; // serán adyacentes en Q, ya que los puntos de evento que están contenidos en estos los segmentos tienen las mismas coordenadas; 2) si (|L(q)| + |R(q)| + |I(q)| > 1) O (|I(q)| > 0) luego Punto de retorno q; 3) if (|I(q)| = 0) AND (|L(q)|+|R(q)| > 0) // en el punto considerado, todos los segmentos solo comienzan o terminan; entonces I(q) ← I(q) ∪ L(q) ∪ R(q); // suma a I(q) L(q) y R(q) 4) Eliminar de TR(q) e I(q); 5) Insertar en TI(q) y L(q); // todos los segmentos del conjunto I(q) han sido eliminados de T, pero ahora se insertan nuevamente en el orden cambiado después del punto de intersección; 6) si (L(q)∪I(q) = ∅) O (|I(q)| = |R(q)| - 1) luego encuentre en T los vecinos superior e inferior de q su y sl; newq = findIntersect(su, sl); si nuevaq != NULL luego agregue (Q, nuevoq); 7) más Sea s′ el segmento superior de L(q)∪I(q); Sea su el vecino superior de s′ en T; Sea s′′ el segmento más bajo de L(q) ∪ I(q); Sea sl el vecino inferior de s′′ en T; newq = findIntersect(su, s′); si nuevaq != NULL luego agregue (Q, nuevoq); nuevoq = buscarIntersección(sl, s′′); si nuevaq != NULL luego agregue (Q, nuevoq); // luego elimina el cuadrado de memoria; newq = findIntersect(sl, su); si nuevaq != NULL luego eliminar (Q, newq); nuevoq = encontrarIntersección(s′′, su); si nuevaq != NULL luego eliminar (Q, newq); nuevoq = buscarIntersección(sl, s′); si nuevaq != NULL luego eliminar (Q, newq); encontrarIntersección(sl, su) si sl y su se cruzan a la derecha de la línea de barrido (o en la línea de barrido por encima del punto de evento actual) luego devuelve newq; de lo contrario, devuelve NULL;

Análisis

Sea el número de segmentos, sea el número de segmentos que cortan el punto . Entonces el tiempo para inicializar Q es , y para inicializar T es . Lleva tiempo encontrar todos los segmentos que pasan por el punto y actualizar Q. Actualizar T también es tiempo. Total: , donde es el número de puntos de intersección . . $norte$ $m\izquierda(q\derecha)$ $q$ $O \left(n \log n \right)$ $O\izquierda(1\derecha)$ $q$ $O \left(m \left(q \right) \log n \right)$ $O \left(m \left(q \right) \log n \right)$ $O \left(n \log n + \sum m \left(q \right) \log n \right) = O \left(n \log n + \log n \sum m \left(q \right) \right ) = O \left( \left(n+k \right) \log n \right)$ $k$ $\left( \sum m \left(q \right) = O \left(n+k \right) \right)$ $k = O \izquierda(n^2 \derecha)$

Memoria , debido a que se eliminan los puntos de intersección de segmentos que ya no son adyacentes, de lo contrario sería , donde . $O\izquierda(n\derecha)$ $O \izquierda(n + k \derecha)$ $k = O \izquierda(n^2 \derecha)$

Notas

↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
↑ Praparata F., Sheimos M. Geometría computacional: una introducción = Geometría computacional Una introducción. — M .: Mir, 1989. — 478 p.
↑ Kormen, T. , Leizerson, C. , Rivest, R. Algorithms: construcción y análisis = Introducción a los algoritmos / Per. De inglés. edición A. Shen. — M. : MTsNMO, 2000. — 960 p. - ISBN 5-900916-37-5 .
↑ Laszlo M. Geometría computacional y gráficos por computadora en C++. - M. : BINOM, 1997. - 304 p.

Literatura

Berg M., Cheong O., Creveld M., Overmars M. Geometría computacional. Algoritmos y Aplicaciones = Geometría Computacional: Algoritmos y Aplicaciones. - M. : DMK-Press, 2016. - 438 p. - ISBN 978-5-97060-406-9 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Geometría Computacional: Algoritmos y Aplicaciones. - Springer, 2000. - 368 págs.
Praparatha F., Sheimos M. Geometría computacional Una introducción. — M .: Mir, 1989. — 478 p.
Laszlo M. Geometría computacional y gráficos por computadora en C++. - M. : BINOM, 1997. - 304 p.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmos. Construcción y Análisis = Introducción a los Algoritmos. - 2ª ed. - "Williams", 2005. - 1296 p.

Enlaces

El visualizador es un caso especial (el algoritmo Sheimos-Goy, 1976 (determinación de la presencia de segmentos que se cruzan)).