Diferencia entre revisiones de «Localización de un punto»

Contenido eliminado Contenido añadido
imported>Ecrcasla
imported>Ecrcasla
Sin resumen de edición
Línea 1:
==Localización de un punto – Método Rosa de los Vientos==
 
Dado un punto P y un áreapolígono [http://en.wikipedia.org/wiki/Irregular_polygons simple] A, si al trazar un segmento entre P y alguno de los vértices del áreapolígono A dicho segmento solamente toca al áreapolígono en el vértice mencionado (es decir ni cruza ni toca ni solapa ningún otro segmento o vértice), resulta:
 
* Si el segmento accede al vértice por el ángulo interno del áreapolígono → el punto es interior
 
* Si el segmento accede al vértice por el ángulo externo del áreapolígono → el punto es exterior
 
[[Archivo:rosa de los vientos 1.jpg|center|300px]]
 
El método propone que si el segmento incógnita ni cruza ni toca ni solapa ningún segmento del áreapolígono (salvo en el vértice elegido) entonces el punto P no cambia su estado, ya sea interno o externo. Por este motivo alcanza con saber si el segmento incógnita llega al vértice por dentro o por fuera del polígono.
 
== Descripción del método ==
 
La primera medida es conocer si los vértices que conforman el polígono están ordenados en forma horaria o antihoraria.
Si calculamos el producto, vectorial, utilizando los vértices del áreapolígono, tenemos que:
 
* Si el resultado es positivo → entonces los vértices están ordenados en forma antihoraria
Línea 24:
[[Archivo:rosa de los vientos 2.jpg|center]]
 
Luego de conocido el ordenamiento de los vértices, tomamos un vértice del áreapolígono al azar y chequeamos que ningún de los segmentos del áreapolígono se cruzan, tocan o se solapan con el segmento que se forma entre el punto P y el vértice seleccionado (con excepción obviamente de este vértice). Este procedimiento lo repetimos hasta encontrar un vértice del áreapolígono que cumpla con esta condición.
 
Nota: El contacto entre dos segmentos cualesquiera se halla utilizando la ecuación de la [[recta]] (y= a*x+b), donde a es la pendiente de la recta y b es la ordenada al origen o bien (x=c) para rectas verticales, donde c representa el valor constante de x. Con estas ecuaciones se ubica el punto de cruce de ambas rectas (si no son paralelas), verificando si ese punto es interior a los dos segmentos. El único punto que debe ser interno a los dos segmentos es el vértice elegido del áreapolígono a evaluar. Si existe otro punto de contacto, entonces ese vértice no sirve para evaluar si el punto P es interior o exterior.
 
Se deberá tener en cuenta, además, situaciones especiales tales como segmentos de una misma recta (a1= a2 y b1=b2 o bien c1=c2) donde se deberá evaluar solapamiento de segmentos, que tampoco sirven para este análisis.
Línea 32:
Una vez hallado un vértice de las características mencionadas podemos calcular el ángulo interno y externo y compararlo con el ángulo del segmento incógnita.
 
Otra forma, evitando fórmulas trigonométricas, es calcular sobre los dos segmentos concurrentes (pertenecientes al áreapolígono) y el segmento incógnita, las pendientes de la recta y la orientación.
 
La '''pendiente''' a se calcula como (y2-y1)/(x2-x1). El cálculo arroja un valor numérico positivo para el primer y tercer cuadrante y negativo para el segundo y cuarto cuadrante. Cuando y2=y1 → la recta es horizontal → a=0 y cuando x2=x1 la recta es vertical → hacemos a=“V”.
 
Por su parte la '''orientación''' surge al colocar imaginariamente el vértice del áreapolígono en el centro de coordenadas (x=0, y=0) y evaluar como acceden a dicho vértice tanto el segmento anterior como el posterior y el segmento incógnita, teniendo en cuenta los distintos cuadrantes. En este caso tendremos que los segmentos pueden acceder desde:
+Y, +X+Y, +X, +X-Y, -Y, -X-Y, -X, -X+Y (enumerado en forma horaria).
 
Línea 43:
'''N, NE, E, SE, S, SO, O, NO''' (Particularmente esta notación parece ser más amistosa desde lo visual)
 
Conociendo el hecho de que los ángulos internos del áreapolígono (medidos desde el segmento posterior hacia el segmento anterior de cada vértice) coincide con el sentido de enumeración de los vértices del áreapolígono (horario o antihorario), estamos en condiciones de calcular cuales son los cuadrantes cubiertos en forma parcial o total por el ángulo interno y por lo tanto cuales son los cubiertos por el ángulo externo.
 
[[Archivo:rosa de los vientos 3.jpg|center]]
 
En nuestro ejemplo del áreapolígono 1,2,3,4,5 el producto vectorial de los vértivces es: (5*2-5*6)+(5*1-3*2)+(3*2-1*1)+(1*6-1*2)+(1*6-5*6) = '''-36 < 0 → sentido horario.'''
 
Se puede apreciar que los vértices 2, 3 y 4 cumplen con las condiciones de no intersección, mientras que los vértices 1 y 5 no la cumplen.
Línea 61:
Teniendo en cuenta que para recorrer el angulo interno del vértice 2 partiendo desde el segmento 2-3 (el posterior) hasta el 1-2 (el anterior) lo debemos hacer en el sentido horario, del cuadro podemos afirmar que :
 
*''' Los cuadrantes incluidos en el áreapolígono son: SO(parcial-pendientes <= |0,5|), O, NO, N'''
 
*''' Los cuadrantes excluidos del áreapolígono son: SO(parcial-pendientes >|0,5|), S, SE, E, NE'''
 
 
Línea 70:
 
Donde:
* '''I''' → Cuadrante Incluido totalmente en el Áreapolígono
* '''E''' → Cuadrante Excluido totalmente del Áreapolígono
* '''<= |0,5|''' → En este cuadrante, el áreapolígono Incluye las pendientes menores e iguales en valor absoluto a 0,5 y Excluye a las de valor mayor
 
Si '''P''' hubiera accedido desde cualquiera de los cuadrantes incluidos totalmente '''(O,NO,N)''', entonces estaría incluido en el áreapolígono '''A'''. En cambio si hubiera accedido desde cuadrantes totalmente excluidos '''(S, SE, E, NE)''', estaría excluido.
 
En el caso que acceda desde un cuadrante incluido en forma parcial, se deben comparar los valores de las pendientes.
 
En nuestro caso la pendiente del segmento P-2 es mayor a la del segmento 2-3 en valor absoluto (|1|>|0,5|) y como el cuadrante SO está excluido para pendientes mayores de |0,5| → '''el punto P es externo al áreapolígono A.'''
 
== Véase también ==