第三章 空间数据结构和编码.ppt.Convertor.doc

文档介绍：怎样生成多边形?
左转算法:
从组成多边形边界的某一条弧段开始,如果该弧段与X轴的正向夹角a0为最小,则从该弧段的同一结点出发的其它弧段中,其方向角(弧段与X轴的夹角为方向角,设方向角ai, ai∈[0, 2π]),为最大的弧段是该多边形的后继弧段;如果a0不为最小,则最小的正偏差角(a0-ai)所对应的弧段为后继弧段。
①
②计算所选弧段以及与该弧段的起节点相连的所有弧段的方向角。计算方法为:选择要计算弧段上离所t选弧段起始节点最近的一个角点,连接两点计算出角度值。
a0
a1
a2
与a的起始节点5相关联的弧段为b、d,它们的方向角分别为a0,a1,a2
a0
a1
a2
③比较上一步所计算出来的方向角,如果a0为最小,则方向角ai为最大的弧段为后继弧段,否则最小正偏差角(a0-ai)所对应的弧段为后继弧段。
这里a0不为最小
而(a0-a1)为最小正值
所以与a1对应的弧段b为后继弧段
④用同样的方法找出后继弧段,直至最后生成多边形。
弧段
起
止
左P
右P
a
5
1
A
为什么叫左转算法?
当前弧段的后继弧段都在当前弧段的左边。
b
8
5
A
h
8
1
A
/
/
/
A
⑤定义左右多边形。
如果弧段成顺时针方向,则将右边定义为要处理的多边形,左多边形的定义分两种情况,如果该弧段未被处理过则左多边形定义为空,如果该弧段已处理过则继续用前面处理过的结果。如果弧段成逆时针方向则反之。
A
E
d
i
c
b
A
弧段
起
止
左P
右P
d
19
5
E
i
16
19
E
c
16
8
E
/
/
/
b
8
5
A
E
⑥继续处理未处理过的任一弧段(岛除外),重复步骤②-⑤。
⑦对岛进行处理。根据所给的角点坐标判断岛的闭合方向及