为geofencing ruby​​创建多边形对象

在Ruby中我想写一个Polygon对象，它将采用经度和纬度的点数组（每个点以数组顺序连接到下一个点）。 现在我的主要问题是什么是表示两点之间的边（线）的最佳方法，以便我可以插入一个点，看看它的多边形内部或外部？

有没有一个gem可以轻松添加此function？

这是我到目前为止所写的所有代码

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

Answer 1

这是确定给定点是在多边形内（或在边缘上）的一种方法。

码

 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 

我假设多边形不是直线（即，所有顶点都不是共线的）。

例

 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 

说明

这是示例中多边形的图形。

多边形的每个边缘，如果在两个方向上无限延伸，则形成将平面分成两部分的线。 对于给定点在多边形内（包括边缘上的点），它必须位于由包含多边形的边形成的所有线的边上。

在该示例中，箭头表示通过[5,1]和[2,4]以及通过[2,4]和[2,8]线的适用侧。 通过[5,1]和[2,4]的线的等式被发现是：

 y = 6.0 - x 

因此，该线两侧的点由6.0 - x <= y和6.0 - x >= y 。 为了确定哪个不等式适用于每个边，我们需要多边形的内部点。 由于它是凸的，顶点的许多凸组合都可以。 例如，如果没有三个连续顶点是共线的，我们可以使用任意两个非相邻顶点的平均值。 我选择使用所有顶点的平均点，即使三个或更多（但不是全部）连续顶点是共线的，它也是一个内点：

 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] 

现在返回到通过前两个顶点的线，我们看到：

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

因此，内部点位于由下式给出的半空间中：

 6 - x <= y 

因此，我们应用以下测试来确定兴趣点[6,7]位于此半空间内：

 6.0 - 6.0 = 0 <= 7.0 

确实如此， [9,9] 。 如果我们考虑点[2,2] ，我们会发现：

 6.0 - 2.0 = 4.0 > 2.0 

所以会得出相反的结论，并从inside?返回false inside? 。

现在考虑通过[6,10]和[9,6] ，其等式为：

 y = 18.0 - 1.333*x 

如

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

因此，与包含多边形的这条线相关联的半空间由不等式给出：

 18.0 - 1.333*x >= y 

我们可以使用这个不等式来测试点是否落在这个半空间内。 对于[6,7] ：

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

对于[9,9] ：

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

Answer 2

接受的答案对我不起作用，但是经过更多的搜索，我找到了这个解决方案，我将其转换为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 

原帖如下： https ： //www.codeproject.com/Articles/62482/A-Simple-Geo-Fencing-Using-Polygon-Method

海报还使用了另一个来源： http ： //alienryderflex.com/polygon/

希望这有助于某人。