Creando objeto poligonal para geofencing ruby

En Ruby, quiero escribir un objeto Polígono que tome una matriz de puntos en longitud y latitud (cada punto se conecta con el siguiente en orden de matriz). Ahora mi pregunta principal es ¿cuál es la mejor manera de representar los bordes (líneas) entre los dos puntos para poder luego agregar un punto y ver si está dentro o fuera del polígono?

¿Hay una gem que agregue fácilmente esta funcionalidad?

Este es todo el código que he escrito hasta ahora.

class Polygon attr_reader :vertices def initialize(vertices) @vertices = vertices end end 

Aquí hay una manera de determinar si un punto dado está dentro de un polígono (o en un borde).

Código

 def inside?(vertices, test_point) vs = vertices + [vertices.first] xi, yi = vertices.reduce([0,0]) { |(sx,sy),(x,y)| [sx+x, sy+y] }.map { |e| e.to_f/vertices.size } # interior point x, y = test_point vs.each_cons(2).all? do |(x0,y0),(x1,y1)| if x0 == x1 # vertical edge (xi > x0) ? (x >= x0) : (x <= x0) else k, slope = line_equation(x0,y0,x1,y1) (k + xi*slope > yi) ? (k + x*slope >= y) : (k + x*slope <= y) end end end def line_equation(x0,y0,x1,y1) s = (y1-y0).to_f/(x1-x0) [y0-s*x0, s] end 

He asumido que el polígono no es una línea recta (es decir, todos los vértices no son co-lineales).

Ejemplo

 vertices = [[5,1],[2,4], [2,8], [6,10], [9,6]] inside?(vertices, [6,7]) #=> true inside?(vertices, [9,9]) #=> false inside?(vertices, [5,1]) #=> true 

Explicación

Aquí hay una gráfica del polígono en el ejemplo.

introduzca la descripción de la imagen aquí

Cada borde del polígono, si se extiende infinitamente en ambas direcciones, forma una línea que divide el plano en dos partes. Para que un punto dado esté dentro del polígono (incluidos los puntos en los bordes), debe estar en los lados de todas las líneas formadas por los bordes que contienen el polígono.

En el ejemplo, las flechas indican los lados aplicables para las líneas que pasan por [5,1] y [2,4] , y por [2,4] y [2,8] . La ecuación para la línea a través de [5,1] y [2,4] se encuentra que es:

 y = 6.0 - x 

Por lo tanto, los puntos a cada lado de esta línea están dados por 6.0 - x <= y y 6.0 - x >= y . Para determinar qué desigualdad se aplica a cada borde, necesitamos un punto interior del polígono. Como es convexo, bastan muchas combinaciones convexas de los vértices. Si, por ejemplo, tres vértices consecutivos no fueran co-lineales, podríamos usar, digamos, el promedio de dos vértices no adyacentes. He elegido usar el punto que es el promedio de todos los vértices, que será un punto interior incluso si tres o más vértices consecutivos (pero no todos) son co-lineales:

 xi, yi = vertices.reduce([0,0]) { |(sx,sy),(x,y)| [sx+x, sy+y] }.map { |e| e.to_f/vertices.size } #=> [4.8, 5.8] 

Volviendo ahora a la línea que pasa a través de los dos primeros vértices, vemos que:

 6.0 - x = 6.0 - 4.8 = 1.2 => (1.2 < 5.8) => true 

Por lo tanto, el punto interior se encuentra en el medio espacio dado por:

 6 - x <= y 

Por lo tanto, aplicamos la siguiente prueba para ver si el punto de interés, [6,7] , se encuentra dentro de este medio espacio:

 6.0 - 6.0 = 0 <= 7.0 

Lo hace, al igual que el punto [9,9] . Si tuviéramos que considerar el punto [2,2] , encontraríamos:

 6.0 - 2.0 = 4.0 > 2.0 

¿Así concluiría lo contrario, y devolvería el false desde inside? .

Ahora considere la línea que pasa por [6,10] y [9,6] , cuya ecuación es:

 y = 18.0 - 1.333*x 

Como

 18.0 - 1.33*xi => 18.0 - 1.333*4.8 = 11.6 => (11.6 < 5.8) => false 

Por lo tanto, el espacio intermedio asociado con esta línea que contiene el polígono viene dado por la desigualdad:

 18.0 - 1.333*x >= y 

Podemos usar esta desigualdad para probar si los puntos caen dentro de este espacio medio. Para [6,7] :

 18.0 - 1.333*6 #=> (10.0 >= 7) #=> true 

Para [9,9] :

 18.0 - 1.333*9 #=> (6.0 >= 7) #=> false 

La respuesta aceptada no me funcionó, sin embargo, después de buscar más encontré esta solución, que convertí en Ruby:

 def inside?(vertices, test_point) sides = vertices.count - 1 j = sides - 1 point_status = false x, y = test_point vertices.each_with_index do |item_i, index| item_j = vertices[j] if item_i.y < y && item_j.y >= y || item_j.y < y && item_i.y >= y if item_i.x + (y - item_i.y) / (item_j.y - item_i.y) * (item_j.x - item_i.x) < x point_status = !point_status end end j = index end point_status end 

La publicación original está en: https://www.codeproject.com/Articles/62482/A-Simple-Geo-Fencing-Using-Polygon-Method

El póster también ha utilizado otra fuente que es: http://alienryderflex.com/polygon/

Espero que esto ayude a alguien.