http://blog.sina.com.cn/s/blog_8e6bfecf0100zve9.html
方法1:
从点P向左做射线,计算与多边形的交点数。如果交点个数为奇数,点P在多边形内部;如果交点个数为偶数,点P在多边形外部。可以按任意顺序考虑多边形的每一条边,来求取交点的总个数。
计算时需要注意:(以边P1P2为例)
-
如果一个多边形顶点以该射线为切线,则直接忽略该顶点(因为射线会与两条线段的端点相交,而这两条线段有一个共同的端点);
-
如果边P1P2水平,射线与其无交点或有无数个交点,该边也可以直接忽略;
-
如果边P1P2竖直,很容易判断是否相交(只能有一个交点);
-
判断相交之前,先判断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) |