Coordenada dada de un polígono y un punto. ¿Cómo calculo si el punto se encuentra dentro del polígono?

Answer 1

Un polígono es una forma 2D. El polígono P es un conjunto de [matemáticas] p_i [/ ​​matemáticas] puntos [matemáticas] (x_i, y_i) [/ matemáticas]

Si los puntos están ordenados en sentido antihorario (Figura 1), podemos usar la propiedad del producto cruzado para definir si un punto q = (x, y) está dentro de P.

Tenemos que comenzar con [math] p_0 [/ math] y calcular el producto cruzado:

[matemáticas] (p_0-q) \ veces (p_1-q) [/ matemáticas]

Si este producto cruzado es positivo, entonces el vector [math] \ vec {qp_1} [/ math] es en sentido antihorario desde [math] \ vec {qp_0} [/ math]

Debe calcular todos los productos cruzados en esta secuencia como en la Figura 2:

[matemáticas] (p_0-q) \ veces (p_1-q) [/ matemáticas]

[matemáticas] (p_1-q) \ veces (p_2-q) [/ matemáticas]

[matemáticas] (p_2-q) \ veces (p_3-q) [/ matemáticas]

[matemáticas] \ puntos [/ matemáticas]

[matemáticas] (p_ {n-1} -q) \ veces (p_n-q) [/ matemáticas]

[matemáticas] (p_n-q) \ veces (p_0-q) [/ matemáticas]

Si todos estos productos cruzados son positivos, entonces señale q dentro de P.

Si algunos de ellos son negativos, entonces q está fuera de P. La figura 3 muestra el caso cuando el punto q está fuera de P.

PRODUCTOS CRUZADOS

Encontrará esto en “Introducción a los algoritmos” (por Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein, págs. 1016):

[matemáticas] p_1 \ veces p_2 = x_1y_2 – x_2y_1 [/ matemáticas]

Si [math] p_1 \ times p_2 [/ math] es positivo, entonces [math] p_1 [/ math] es en sentido horario desde [math] p_2 [/ math] con respecto al origen (0,0). Cuando el producto cruzado es negativo, [math] p_1 [/ math] es en sentido antihorario desde [math] p_2 [/ math].

(*) [matemática] p_1 [/ matemática] es en sentido horario desde [matemática] p_2 [/ matemática] con respecto al origen (0,0) es equivalente a decir que [matemática] p_2 [/ matemática] es en sentido antihorario desde [matemática ] p_1 [/ math] con respecto al origen (0,0)

Si necesitamos verificar si [math] p_1 [/ math] está en sentido horario o antihorario desde [math] p_2 [/ math] con respecto a un punto final común [math] p_0 [/ math], entonces calculamos el producto cruzado:

[matemáticas] (p_1-p_0) \ times (p_2-p_0) = (x_1-x_0) (y_2-y_0) – (x_2-x_0) (y_1-y_0) [/ matemática]

Si este producto cruzado es positivo, [math] p_2 [/ math] es en sentido antihorario desde [math] p_1 [/ math] con respecto a [math] p_0 [/ math].

Answer 2

Punto en el polígono (PIP), usted dice … Supongo que la mayoría de la gente usa fundición de rayos.

Una manera simple de encontrar si el punto está dentro o fuera de un polígono simple es probar cuántas veces un rayo, comenzando desde el punto y yendo en una dirección fija, intersecta los bordes del polígono. Si el punto en cuestión no está en el límite del polígono, el número de intersecciones es un número par si el punto está afuera, y es extraño si está adentro. Este algoritmo a veces también se conoce como el algoritmo de número de cruce o el algoritmo de regla par-impar , y se conoce desde 1962. El algoritmo se basa en una simple observación de que si un punto se mueve a lo largo de un rayo desde el infinito hasta el punto de la sonda y si cruza el límite de un polígono, posiblemente varias veces, entonces alterna alternativamente de afuera hacia adentro, luego de adentro hacia afuera, etc. Como resultado, después de cada dos “cruces fronterizos”, el punto de movimiento sale hacia afuera. Esta observación puede demostrarse matemáticamente utilizando el teorema de la curva de Jordan.

(Wikipedia)

Answer 3

Puede usar el algoritmo de número de bobinado.
Mira este sitio:
Inclusión de un punto en una respuesta de PolygonWrite