Chinaunix首页 | 论坛 | 博客
  • 博客访问: 482556
  • 博文数量: 120
  • 博客积分: 1853
  • 博客等级: 上尉
  • 技术积分: 1177
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-22 22:40
文章分类

全部博文(120)

文章存档

2013年(16)

2012年(104)

分类: LINUX

2013-10-19 21:13:35

http://blog.sina.com.cn/s/blog_8e6bfecf0100zve9.html

方法1:
    从点P向左做射线,计算与多边形的交点数。如果交点个数为奇数,点P在多边形内部;如果交点个数为偶数,点P在多边形外部。可以按任意顺序考虑多边形的每一条边,来求取交点的总个数。
    计算时需要注意:(以边P1P2为例)
  1. 如果一个多边形顶点以该射线为切线,则直接忽略该顶点(因为射线会与两条线段的端点相交,而这两条线段有一个共同的端点);
  2. 如果边P1P2水平,射线与其无交点或有无数个交点,该边也可以直接忽略;
  3. 如果边P1P2竖直,很容易判断是否相交(只能有一个交点);
  4. 判断相交之前,先判断P是否在边P1P2上,如果在,则P在多边形内部(可根据内部的不同定义更改)。
注意:可以使用bounding box进行加速。

方法2:
    首先保证多边形的所有点都有序。然后,做P点到多边形所有点的连线,计算P点与多边形所有边的端点所成的角度(在P点处所成的角)的和(根据边的顶点位置,求出来的角度有正有负)。如果所有角度的和等于 2PI ,则点P在多边形内;否则,点P在多边形外。
    同样,可以使用bounding box进行加速。

判断一个点P是否在三角形ABC内:
当点p在三角形abc内时,4个三角形的面积满足:abc = abp + apc + pbc
计算面积使用向量外积:abc = |ab x ac| / 2
而且因为:
pb x pc = (ab-ap) x (ac-ap) = ab x ac - ab x ap - ap x ac
所以公式转换为:
ab x ac 是否等于 ab x ap + ap x ac + (ab x ac - ab x ap - ap x ac)
阅读(3604) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~