Ver el código de «Localización de un punto»

{{referencias}}
==Localización de un punto – Método Rosa de los Vientos==

Dado un punto P y un polígono [[:m:w:en:Irregular_polygons|simple]] A, si al trazar un segmento entre P y alguno de los vértices del polígono A dicho segmento solamente toca al polí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 polígono → el punto es interior

* Si el segmento accede al vértice por el ángulo externo del polí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 polí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 [[:m:w:en:Irregular_polygons|producto vectorial]], utilizando los vértices del polígono, tenemos que:

* Si el resultado es positivo → entonces los vértices están ordenados en forma antihoraria 

* Si el resultado es negativo → entonces los vértices están ordenados en forma horaria

Esta particularidad también nos indica que los ángulos internos del polígono, medidos sobre cada vértice desde el segmento posterior hasta el anterior tienen en el mismo sentido que el ordenamiento de los vértices.

[[Archivo:rosa de los vientos 2.jpg|center]]

Luego de conocido el ordenamiento de los vértices, tomamos un vértice del polígono al azar y chequeamos que ningún de los segmentos del polí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 polí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 polí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.

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 polí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 polí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).

Otra forma sería asimilar los cuadrantes a la '''Rosa de los Vientos''', por lo tanto quedaría:

'''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 polí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 polí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 polí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.

Tomemos por lo tanto el vértice 2.

Las coordenadas de los vértices son: 1=(5,6), 2=(5,2), 3=(3,1), mientras que P=(3,0).

El segmento 1-2 es anterior al vértice 2 y el 2-3 es posterior al vértice 2, mientras que el segmento P-2 es el segmento incógnita:
     
:{| class="wikitable"
|-
! Segmentos
! Pendiente
! Orientación respecto del vértice 2
|-
| 1-2
| <math>\frac{2-6}{5-5} \longrightarrow \mathbf{V}</math>
| N
|-
| 2-3
| <math>\frac{1-2}{3-5} \longrightarrow \mathbf{+0,5}</math>
| SO
|-
| P-2
| <math>\frac{2-0}{5-3} \longrightarrow \mathbf{+1}</math>
| SO
|}

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 polígono son: SO(parcial-pendientes <= |0,5|), O, NO, N'''

*''' Los cuadrantes excluidos del polígono son: SO(parcial-pendientes >|0,5|), S, SE, E, NE'''
:{| class="wikitable" style="text-align:center;"
|-
! style="width:50px;" | N
! style="width:50px;" | NE
! style="width:50px;" | E
! style="width:50px;" | SE
! style="width:50px;" | S
! style="width:50px;" | SO
! style="width:50px;" | O
! style="width:50px;" | NO
|-
| I || E || E || E || E || <math>\le\vert0,5\vert</math> || I || I
|}

Donde:
* '''I''' → Cuadrante Incluido totalmente en el polígono
* '''E''' → Cuadrante Excluido totalmente del polígono
* '''<= |0,5|''' → En este cuadrante, el polí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 polí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 polígono A.'''

== Véase también ==
* [[Recta]]
* [[:m:w:en:Point_in_polygon|Point in Polygon]]
* [[:m:w:en:Irregular_polygons|Polygon]]
* [[:m:w:en:JTS_Topology_Suite|JTS Topology Suite]]
* [[Valor absoluto]]

== Enlaces externos ==
* [http://wmatem.eis.uva.es/~matpag/CONTENIDOS/Geometria/marco_geometria.htm Geometría]

[[Categoría:Algoritmia]]
[[Categoría:Geometría elemental]]