Ingreso

Algoritmo para encontrar las intersecciones entre segmentos Verticales y Horizontales


Para comenzar, se supondrá que todos los segmentos son horizontales o verticales, por lo tanto, los dos puntos que definen cada segmento tienen igual coordenada 'x' o igual coordenada 'y'. El plan general para encontrar una intersección en un conjunto de segmentos, consiste en imaginar el recorrido de unalinea exploratoria horizontal, que barre desde abajo hacía arriba. Las proyecciones sobre esta linea, se dan de manera que los segmentos verticales son puntos y los segmentos horizontales son intervalos; a medida que la linea exploratoria avanza de abajo hacía arriba, los puntos (que representan a los segmentos verticales) aparecen y desaparecen, y los segmentos horizontales se encuentranperiódicamente. Una intersección se encuentra, cuando se encuentra un segmento horizontal que representa un intervalo en la linea de exploración, la cual contiene un punto que representa un segmento vertical. Reunido el punto significa que el segmento vertical cruza a la linea exploratoria, y el segmento horizontal se encuentra en la linea de exploración, por lo que los segmentos horizontales y verticalesdeben cruzarse.
Por supuesto, no es necesario en realidad “barrer”con la linea exploratoria horizontal hasta el final a través del conjunto de segmentos, ya que tenemos que tomar medidas sólo cuando se encuentran los extremos de los segmentos, podemos comenzar por clasificar los segmentos en función de su coordenada 'y', a continuación, procesar los segmentos en ese orden. Si se encuentra elpunto del extremo inferior de un segmento vertical, añadimos la coordenada 'x' a un árbol de búsqueda binaria, y si se encuentra el extremo superior, borramos la coordenada en 'x' del árbol, y al encontrarse un segmento horizontal, realizamos la Búsqueda por Rango con las coordenadas en 'x' de los extremos del segmento. El algoritmo de Búsqueda por Rango se explicara a continuación.

Algoritmo deBúsqueda por Rango (Range Searching)

Se utiliza para saber cuales puntos de un conjunto de puntos, se encuentran dentro de un intervalo dado. Consiste en construir un árbol binario de búsqueda, que contiene el conjunto de puntos, y después hacer un simple recorrido recursivo del mismo, devolviendo los puntos dentro del intervalo e ignorando las partes del árbol situadas fuera de él. Si el puntodel extremo izquierdo del intervalo está a la izquierda del punto de la raíz, se busca (recursivamente) en el subárbol izquierda y de forma similar para el derecho, verificando en cada nodo que se encuentre, si los puntos asociados a cada uno de ellos están o no dentro del intervalo.

Pseudocódigo del algoritmo de Búsqueda por Rango:

//Devuelve el número de puntos que se encuentran dentro delintervalo formado por [v1, v2]

int BusquedaPorRango(arbol*a,int v1,int v2){

bool x=false;bool y=false;
int contador=0;

Si el arbol es vacio
return 0;
Si no es vacio {
Si el valor del nodo del arbol es mayor o igual que v1
if (a->Valor()>=v2){x=true;}
Si el valor del nodo del arbol es menor o igual que v2
if (a->Valor()subArb_i(),v1,v2);}Si x e y son verdaderos, el punto se encuentra dentro del intervalo.
if (x&&y){contador++;}
Si y es verdadero, busco por el subárbol derecho
if (y){contador+=BusquedaPorRango(a->subArb_d(),v1,v2);}
}
return contador;
}

Costo: 0(logN). Siendo N el número de elementos en el árbol.

A continuación se tratará de explicar de manera gráfica, de forma tal que seentienda de mejor manera su funcionamiento:
Figura 1.1 - Explorando las Intersecciones.


La figura 1.1 muestra el barrido de la linea de exploración para encontrar las intersecciones, la exploración se inicia en el punto con la menor coordenada y, siendo el extremo inferior del segmento C (Paso 1), por lo tanto la coordenada x de este segmento es cargado en un...