halcon中如何判断一个点是否在多边形内部?

如何判断一个点是否在多边形内部?
(1)面积和判别法:判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形,相等则在多边形内部。--采纳
(2)夹角和判别法:判断目标点与所有边的夹角和是否为360度,为360度则在多边形内部。
(3)引射线法:从目标点出发引一条射线,看这条射线和多边形所有边的交点数目。如果有奇数个交点,则说明在内部,如果有偶数个交点,则说明在外部。

(4)转角法:按照多边形顶点逆时针顺序,根据顶点和判断点连线的方向正负(设定角度逆时针为正)求和判断;

 

射线法的实现(转载文章:https://www.jianshu.com/p/ba03c600a557

射线法就是以判断点开始,向右(或向左)的水平方向作一射线,计算该射线与多边形每条边的交点个数,如果交点个数为奇数,则点位于多边形内,偶数则在多边形外。该算法对于复合多边形也能正确判断

image.png

复合多边形的情况


射线法的关键是正确计算射线与每条边是否相交。并且规定线段与射线重叠或者射线经过线段下端点属于不相交。首先排除掉不相交的情况,下图的情况都是需要排除掉的:

image.png

求交之前可排除的情况


排除掉这些情况的函数如下:

def isRayIntersectsSegment(poi,s_poi,e_poi): #[x,y] [lng,lat]
    #输入:判断点,边起点,边终点,都是[lng,lat]格式数组
    if s_poi[1]==e_poi[1]: #排除与射线平行、重合,线段首尾端点重合的情况
        return False
    if s_poi[1]>poi[1] and e_poi[1]>poi[1]: #线段在射线上边
        return False
    if s_poi[1]<poi[1] and e_poi[1]<poi[1]: #线段在射线下边
        return False
    if s_poi[1]==poi[1] and e_poi[1]>poi[1]: #交点为下端点,对应spoint
        return False
    if e_poi[1]==poi[1] and s_poi[1]>poi[1]: #交点为下端点,对应epoint
        return False
    if s_poi[0]<poi[0] and e_poi[1]<poi[1]: #线段在射线左边
        return False
 
    xseg=e_poi[0]-(e_poi[0]-s_poi[0])*(e_poi[1]-poi[1])/(e_poi[1]-s_poi[1]) #求交
    if xseg<poi[0]: #交点在射线起点的左侧
        return False
    return True  #排除上述情况之后

排除掉上述情况真正需要求交点来判断的情况只有两种:

image.png

需要求交的两种情况

函数isRayIntersectsSegment()里求交的部分就是利用两个三角形的比例关系求出交点在起点的左边还是右边;用图去理解如下:

image.png

求交的具体过程

最后判断的代码如下:

def isPoiWithinPoly(poi,poly):
    #输入:点,多边形三维数组
    #poly=[[[x1,y1],[x2,y2],……,[xn,yn],[x1,y1]],[[w1,t1],……[wk,tk]]] 三维数组
 
    #可以先判断点是否在外包矩形内 
    #if not isPoiWithinBox(poi,mbr=[[0,0],[180,90]]): return False
    #但算最小外包矩形本身需要循环边,会造成开销,本处略去
    sinsc=0 #交点个数
    for epoly in poly: #循环每条边的曲线->each polygon 是二维数组[[x1,y1],…[xn,yn]]
        for i in range(len(epoly)-1): #[0,len-1]
            s_poi=epoly[i]
            e_poi=epoly[i+1]
            if isRayIntersectsSegment(poi,s_poi,e_poi):
                sinsc+=1 #有交点就加1
 
    return True if sinsc%2==1 else  False


参考文献:

------------------------

判断点是否在多边形内的Python实现及小应用(射线法)

配套源码:https://github.com/QLWeilcf/LcfGeoProject/blob/master/poiWithinPolygon.py

判断一个坐标点是否在不规则多边形内部的算法

PNPOLY - Point Inclusion in Polygon Test W. Randolph Franklin (WRF)

Point in Polygon Strategies


本文出自勇哥的网站《少有人走的路》wwww.skcircle.com,转载请注明出处!讨论可扫码加群:

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

会员中心
搜索
«    2024年3月    »
123
45678910
11121314151617
18192021222324
25262728293031
网站分类
标签列表
最新留言
    热门文章 | 热评文章 | 随机文章
文章归档
友情链接
  • 订阅本站的 RSS 2.0 新闻聚合
  • 扫描加本站机器视觉QQ群,验证答案为:halcon勇哥的机器视觉
  • 点击查阅微信群二维码
  • 扫描加勇哥的非标自动化群,验证答案:C#/C++/VB勇哥的非标自动化群
  • 扫描加站长微信:站长微信:abc496103864
  • 扫描加站长QQ:
  • 扫描赞赏本站:
  • 留言板:

Powered By Z-BlogPHP 1.7.2

Copyright Your skcircle.com Rights Reserved.

鄂ICP备18008319号


站长QQ:496103864 微信:abc496103864