随笔 - 85  文章 - 47  trackbacks - 0

常用链接

随笔分类

随笔档案

搜索

  •  

最新评论

1. 叉乘判别法(只适用于凸多边形)

想象一个凸多边形,其每一个边都将整个2D屏幕划分成为左右两边,连接每一边的第一个端点和要测试的点得到一个矢量v,将两个2维矢量扩展成3维的,然后将该边与v叉乘,判断结果3维矢量中Z分量的符号是否发生变化,进而推导出点是否处于凸多边形内外。这里要注意的是,多边形顶点究竟是左手序还是右手序,这对具体判断方式有影响。

2. 面积判别法(只适用于凸多边形)

第四点分别与三角形的两个点组成的面积分别设为S1,S2,S3,只要S1+S2+S3>原来的三角形面积就不在三角形范围中.可以使用海伦公式 。推广一下是否可以得到面向凸多边形的算法?(不确定)

3. 角度和判别法(适用于任意多边形)

double angle = 0;
realPointList::iterator iter1 = points.begin();
for (realPointList::iterator iter2 = (iter1 + 1); iter2 < points.end(); ++iter1, ++iter2)
 {
   double x1 = (*iter1).x - p.x;  
   double y1 = (*iter1).y - p.y;  
   double x2 = (*iter2).x - p.x;
   double y2 = (*iter2).y - p.y;  
   angle += angle2D(x1, y1, x2, y2);
 }

if (fabs(angle - span::PI2) < 0.01) return true;
else return false;

另外,可以使用bounding box来加速。
if (p.x < (*iter)->boundingBox.left ||
   p.x > (*iter)->boundingBox.right ||
   p.y < (*iter)->boundingBox.bottom ||
   p.y > (*iter)->boundingBox.top) 。。。。。。

对于多边形来说,计算bounding box非常的简单。只需要把水平和垂直方向上的最大最小值找出来就可以了。

对于三角形:第四点分别与三角形的两个点的交线组成的角度分别设为j1,j2,j3,只要j1+j2+j3>360就不在三角形范围中。

4. 水平/垂直交叉点数判别法(适用于任意多边形)

注意到如果从P作水平向左的射线的话,如果P在多边形内部,那么这条射线与多边形的交点必为奇数,如果P在多边形外部,则交点个数必为偶数(0也在内)。所以,我们可以顺序考虑多边形的每条边,求出交点的总个数。还有一些特殊情况要考虑。假如考虑边(P1,P2),
1)如果射线正好穿过P1或者P2,那么这个交点会被算作2次,处理办法是如果P的从坐标与P1,P2中较小的纵坐标相同,则直接忽略这种情况
2)如果射线水平,则射线要么与其无交点,要么有无数个,这种情况也直接忽略。
3)如果射线竖直,而P0的横坐标小于P1,P2的横坐标,则必然相交。
4)再判断相交之前,先判断P是否在边(P1,P2)的上面,如果在,则直接得出结论:P再多边形内部。

posted on 2007-09-06 14:46 w2001 阅读(26274) 评论(7)  编辑 收藏 引用

FeedBack:
# re: 判断点是否处于多边形内的三种方法 2008-09-23 19:34  Torres
第二种方法我试过,利用面积相等即可,但是第一种方法我倒是不太懂,可以叫我一下吗?  回复  更多评论
  
# re: 判断点是否处于多边形内的三种方法[未登录] 2008-09-23 19:56 Xw.Y
第一种方法是利用向量叉乘的物理意义,
如果某点在多边形内,按照描述所叉乘的向量是不会改变方向的,
如果点在多边形外,会得到两组相反的向量。  回复  更多评论
  
# re: 判断点是否处于多边形内的三种方法 2010-12-30 22:11 芋头
第四种方法挺容易理解的,回头试试  回复  更多评论
  
# re: 判断点是否处于多边形内的三种方法 2011-06-17 14:51 aa
第四种不全面
如果射线穿越顶点,则是不确定的,需要再进行计算。  回复  更多评论
  
# re: 判断点是否处于多边形内的三种方法 2011-12-21 16:17 龙凼毛毛虫
第3种好像不太对吧。我只考虑三角形的情况,就算点钟三角形外,这个点和三角形两两相连所成都夹角和依然是360度,有一个角是大于180度的。三角形的情况判别条件是否可以改为:选择小于180度的角度情况下,算3个角度的和小于360度就可以判断点钟三角形外了吧。  回复  更多评论
  
# re: 判断点是否处于多边形内的三种方法 2014-01-08 15:49 gcd0318
角度和法对凹多边形可能不适用,只是充分条件,不是必要条件。例如:正三角形ABC的顶点和中心D组成一个凹四边形ABCD,连接AD延长,和BD交于O,显然O在ABCD外,但是AOB+BOC+COD+DOC(四个直角)=360
交叉点法也要额外判断如果延长线经过顶点怎么计算  回复  更多评论
  
# re: 判断点是否处于多边形内的三种方法 2014-02-28 14:15 rcx92
@gcd0318

角度是有方向的,虽然是四个直角,两个是顺时针,两个是逆时针,它们的和为0  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理