• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

pnpoly判断点是否在多边形内部(c++)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

遇到了一个问题,如何判断一个点是否在一个多边形内部。

主要有以下几种方法:

(1)面积和判别法:判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形,相等则在多边形内部。

(2)夹角和判别法:判断目标点与所有边的夹角和是否为360度,为360度则在多边形内部。

(3)引射线法:从目标点出发引一条射线,看这条射线和多边形所有边的交点数目。如果有奇数个交点,则说明在内部,如果有偶数个交点,则说明在外部。

 

简洁的C++代码如下:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) 
  {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

 

Matlab验证代码:

clc;
close;


%% poly points 设定的多边形顶点
% poly_point_x = [1 1 10 14 7];
% poly_point_y = [0 12 13 2 4];
poly_point_x = [0 0 9];
poly_point_y = [1 12 1];

%% actual points 待测试顶点
test_x = 6;
test_y = 0;

c=0;
m=0;
%% return test point in poly or not 判断测试点是否在多边形内
hold on;
plot(poly_point_x,poly_point_y,'*')
plot(test_x,test_y,'.')
n = 4;%n=顶点数+1
for i = 1: n-1
    if i == 1
        j = n - 1;
    else
        j = i - 1;
    end
    y = ((poly_point_y(:,i) > test_y) ~= (poly_point_y(:,j) > test_y));
    x = ((poly_point_x(:,j) - poly_point_x(:,i))*(test_y - poly_point_y(:,i))/(poly_point_y(:,j) - poly_point_y(:,i)) + poly_point_x(:,i))>test_x;
    
    if y&&x
        c = ~c;
    end
end
c

 

当返回0时,代表点不在多边形中。当返回1时,代表点在多边形中。

 

参考资料:    

笔记A0320180207

http://blog.csdn.net/luyuncsd123/article/details/27528519

https://www.cnblogs.com/luxiaoxun/p/3722358.html

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#连接PDA扫码枪发布时间:2022-07-13
下一篇:
ubuntu下的c/c++环境搭建发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap