 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第三节 平面中的凸壳算法 | ||||
 倾角计算记P点坐标为  ,O点坐标 ,这个角度数可如下简单地计算:
 。若B≥0则角度数=1-A,否则角度数=3+A。这里A是向量OP与OX向上单位向量的内积,因此是倾角的余弦数值。B用以判断该倾角是否大于180度。
Jarvis算法
1.〔准备〕  ←点集S中按x,y字典次序最小的点;
d←竖直向下的一个方向向量; 点送入收集凸壳顶点的队列Q中;S1←S-{ };u← 2.〔一步行进〕v1←Wrapping(u,d,  );3.〔准备下次〕若  ≠,则做:
接入队Q后部;
=S-{u,};d←从u到 的一个方向向量;
u← 返步2。 4.〔结束〕壳顶点已经全部存入队Q中,算法结束。 其中第2步引入函数Wrapping来实现一步行进。此函数的工作是,对 中所有各点,相对自u发出方向为d的射线,计算所成倾角。在所有倾角中取最小,若有多个则选与u距离最远的那个,它对应的点为函数的返回值。因此在步2求得的是一个行进步找到的下个壳顶点。Jarvis 若点集S中只有较少数点在壳上,则算法效率很高。若点集S中绝大多数点都在壳上,算法的效率一般来说就不如Graham扫描了。 |
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
