因此,这条线两侧的点由6.0 - x <= y和6.0 - x >= y给出。为了确定每条边适用哪个不等式,我们需要多边形的一个内点。因为它是凸的,所以顶点的许多凸组合都可以。例如,如果没有三个连续的顶点共线,我们可以使用任何两个不相邻顶点的平均值。我选择使用所有顶点的平均值,即使三个或更多(但不是所有)连续顶点共线,它也将是一个内部点:
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
2条答案
按热度按时间06odsfpq1#
这里有一种方法来确定一个给定的点是否在凸多边形内(或在一个边上)。(注意OP在对问题的评论中确认了多边形是凸的。
验证码
我假设多边形不是一条直线(即所有顶点都不是共线的)。
示例
说明
这是例子中多边形的图形。
多边形的每条边,如果在两个方向上无限延伸,则形成将平面分成两部分的线。对于要在多边形内的给定点(包括边上的点),它必须位于由包含多边形的边形成的所有线的边上。
在本例中,箭头表示通过
[5,1]
和[2,4]
以及通过[2,4]
和[2,8]
的直线的适用边。通过[5,1]
和[2,4]
的直线方程为:因此,这条线两侧的点由
6.0 - x <= y
和6.0 - x >= y
给出。为了确定每条边适用哪个不等式,我们需要多边形的一个内点。因为它是凸的,所以顶点的许多凸组合都可以。例如,如果没有三个连续的顶点共线,我们可以使用任何两个不相邻顶点的平均值。我选择使用所有顶点的平均值,即使三个或更多(但不是所有)连续顶点共线,它也将是一个内部点:现在回到通过前两个顶点的直线,我们可以看到:
因此,内点位于由下式给出的半空间中:
因此,我们应用以下测试来查看感兴趣的点
[6,7]
是否位于该半空间内:它是,点
[9,9]
也是。如果我们考虑点[2,2]
,我们会发现:所以会得出相反的结论,从
inside?
返回false
。现在考虑通过
[6,10]
和[9,6]
的直线,其方程为:作为
因此,与包含多边形的这条线相关联的半空间由以下不等式给出:
我们可以用这个不等式来检验点是否落在这个半空间内。对于
[6,7]
:对于
[9,9]
:i1icjdpr2#
Accepted回答对我不起作用,但是在搜索更多之后,我找到了这个解决方案,我将其转换为Ruby:
原始帖子在:https://www.codeproject.com/Articles/62482/A-Simple-Geo-Fencing-Using-Polygon-Method
海报还使用了另一个来源,即:http://alienryderflex.com/polygon/
希望这对某人有帮助。