 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第一节 线段的交点计算 | ||||
| 规定的次序关系对垂直的线段不适合
两线段相交的必要条件,即若两线段相交,则必然存在某个x,使它们在规定的次序关系  下是相邻的。
算法从左向右扫描,在扫描过程维持正确的线段间上述次序关系。这种次序关系只能有三种可能的变化方式: 1．遇见某条线段S的左端点,此时S应加入次序关系。 2．遇见某线段S的右端点,此时S应从次序关系中删除。 3．遇到某两条线段  和
的交点,这时在次序关系中和交换位置。
算法实施需要两个基本的数据结构: 扫描线状态表和事件点进度表 扫描线状态表L中存放按所规定次序关系  排序的线段的序列。此表初始应为空,在平面扫描过程中当关系改变时变化。
事件点指扫描进行中可能使所规定次序关系 发生变化的点,存放于事件点进度表E中,该表初始时应是排序的要求交点的各线段端点的坐标。在平面扫描过程中求出的交点,应及时地插入到事件点进度表中。
扫描线状态表应能支持以下四个操作: (1) INSERT(S,L),把线段S插入到扫描线状态表L中,注意应插入到适当位置以保持正确的次序关系。 (2) DELETE(S,L),从L中删除线段S。 (3) ABOVE(S,L),返回次序关系中S上面紧接着的线段的编号。 (4) BELOW(S,L),返回次序关系中S下面紧接着的线段的编号。 事件点进度表E应能支持以下三个操作: (1) MIN(E),取出表E中的最小元素。 (2) INSERT(x,E),把横坐标为x的一个点插入到表E中,插入要使E中事件点存放保持递增次序。 (3 ) MEMBER(x,E),判定横坐标为x的点是否在事件点进度表E中。 |
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
