 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第四节 包含与重叠 | ||||
 简单多边形包含性检验的算法
1.〔准备〕xn←x0,yn←y0,m←-1,i←0; 2.〔排除必不相交情形〕若下列条件有一个成立,则到4。 2.1  < 并且< :2.2 ≥并且≥;2.3  < 并且< ;3.〔计算交点〕y= +(-)(-)/(-),分二种情形:(1)若y= ,则点P在多边形边界上,算法结束;(2)若y< ",则m←(-1)m;4.〔结束判断〕i←i+1,若i<n",则返回到2,否则算法结束,此时若m=-1则点P在多边形外部,m=1则在内部。 |
||||
 |
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
