 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第四节 包含与重叠 | ||||
 凸多边形的包含算法
沿逆时针行进，凸多边形内部均在其各边所在直线的左侧,因此只要对询问点P,逐个检查它是否在凸多边形每一边所在直线的左侧就可。 判断坐标为  的点P是在直线的位置
设直线的端点为  和 ,直线方向是由到的方向。直线的方程记为Ax+By+C=0,则有: 
计算D: D=A  +B +C
若D<0,则点在直线左侧; 若D>0,则点在直线右侧; 若D=0,则点在直线上。 |
||||
 |
||||
| 再进一步,引人“折半查找”思想,写出下面更有效率的算法。 设算法的输入是一个凸多边形的顶点序列  ,询问点P,可有包含性检验算法如下:
1.〔准备〕i←1,j←n-1; 2.〔查找是否结束〕若j-i=1则到4,否则继续; 3.〔折半查找〕k←[(i+j)/2],检查询问点相对直线  的位置关系,分三种情况:3.1 在直线上,若点在线段 上或内部,则点在原凸多边形内部,,若点在线段延长线上,则在原凸多边形外;输出回答后算法结束;3.2 在左侧,i←k返回步2 3.3 在右侧,j←k返回步2 4.〔最后检查〕检查询问点P对  的包含性,若在内则也在原凸多边形内部,若在外则也在原凸多边形外部,输出回答后算法结束. |
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
