为地理围栏ruby创建多边形对象

uujelgoq  于 12个月前  发布在  Ruby
关注(0)|答案(2)|浏览(118)

在Ruby中,我想写一个Polygon对象,它将接受一个经度和纬度的点数组(每个点按数组顺序连接到下一个点)。现在我的主要问题是什么是最好的方法来表示两个点之间的边(线),这样我就可以插入一个点,看看它是在多边形的内部还是外部?
有没有一个gem可以轻松地添加此功能?
这是我到目前为止写的所有代码

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

06odsfpq1#

这里有一种方法来确定一个给定的点是否在凸多边形内(或在一个边上)。(注意OP在对问题的评论中确认了多边形是凸的。

验证码

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 <= y6.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
现在考虑通过[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
i1icjdpr

i1icjdpr2#

Accepted回答对我不起作用,但是在搜索更多之后,我找到了这个解决方案,我将其转换为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/
希望这对某人有帮助。

相关问题