Jarvis.算法 1.〔准备〕V←点集S中按x,y字典次序最小的点； d←竖直向下的一个方向向量； 点v送入收集凸壳顶点的队列Q中； S,←S-{vol; u+vo 2.〔一步行进)v,←Wrapp ing(u,d,S); 3.〔准备下次)若v丰vo,则做：V接入队Q后部； S1=S-{u,v}; d←从u到V,的一个方向向量；
Jarvis算法 1.〔准备〕v0←点集S中按x,y字典次序最小的点; d←竖直向下的一个方向向量; 点v0送入收集凸壳顶点的队列Q中; S1←S-{ v0 }; u←v0 2.〔一步行进〕v1←Wrapping(u,d,S1 ); 3.〔准备下次〕若v1≠v0 ,则做: v1接入队Q后部; S1 =S-{u,v1 }; d←从u到v1的一个方向向量;
返步2。 4.〔结束)壳顶点已经全部存入队Q中，算法结束. 其中第2步引入函数Wrapp ing来实现一步行 进。此函数的工作是，对$中所有各点，相对自u 发出方向为d的射线，计算所成倾角。在所有倾角 中取最小，若有多个则选与u距离最远的那个，它 对应的点为函数的返回值。因此在步2求得的v, 是一个行进步找到的下个壳顶点。 Jarvis若点集S中只有较少数点在壳上，则 算法效率很高。若点集$中绝大多数点都在壳上， 算法的效率一般来说就不如Gr aham扫描了
u←v1 返步2。 4.〔结束〕壳顶点已经全部存入队Q中,算法结束. 其中第2步引入函数Wrapping来实现一步行 进。此函数的工作是,对S1中所有各点,相对自u 发出方向为d的射线,计算所成倾角。在所有倾角 中取最小,若有多个则选与u距离最远的那个,它 对应的点为函数的返回值。因此在步2求得的v1 是一个行进步找到的下个壳顶点。 Jarvis 若点集S中只有较少数点在壳上,则 算法效率很高。若点集S中绝大多数点都在壳上, 算法的效率一般来说就不如Graham扫描了
第四节 包含与重叠 ·简单多边形的包含算法 平面上的简单多边形是不相邻的边不能 相交的多边形，设它用顶点坐标的逆时针序 列（0，y0),(x1,y1),,(xn-1,yn-1)确 定，即沿顶点序列前行时内部在左侧。 对平面上坐标为(xp,yp)的任意一点P,包 含性检验问题是判断它是否在所给出简单多 边形的内部
第四节 包含与重叠 • 简单多边形的包含算法 平面上的简单多边形是不相邻的边不能 相交的多边形,设它用顶点坐标的逆时针序 列（x0,y0）,(x1,y1),…,(xn-1, yn-1)确 定,即沿顶点序列前行时内部在左侧。 对平面上坐标为(xp,yp)的任意一点P,包 含性检验问题是判断它是否在所给出简单多 边形的内部
一个简便的判断方法是由P做竖直向下的 射线，计算此射线与多边形各边交点的个数
一个简便的判断方法是由P做竖直向下的 射线,计算此射线与多边形各边交点的个数
当由点P竖直向下的射线恰好通过多边 形的顶点或某一边时，交点计数可采取简单 的"左闭右开"法来处理，即：当多边形一边的 两个顶点的x坐标都小于或等于点P的x坐标 时，相应交点不计算在内。 P E A B A (1) (2) (3) (4)
当由点P竖直向下的射线恰好通过多边 形的顶点或某一边时,交点计数可采取简单 的"左闭右开"法来处理,即:当多边形一边的 两个顶点的x坐标都小于或等于点P的x坐标 时,相应交点不计算在内