第23卷第3期李军辉等:GIS中散乱点集凸包的快速算法及编程

33

min和x

-

2 凸包算法描述

211 相关定义

定义1:设P=(x,y,1)为平面内任一点,计算P与AB的点积,可得点与直线的位置判断函数:

F(P,AB)=(x,y,1)

(yA-yB,xB-xA,xA#yB-xB#yA)=(yA-yB)#x+(xB-xA)#y

+(xA#yB-xB#yA)

根据F的正负号可以判断P与AB的相对位置关系,如图1所示。

1)如果F>0,P在AB的左半平面内;2)如果F=0,P在AB所在的直线上;3)如果F<0,P在AB

的右半平面内。

大最小的两个点x

-

max。

步骤3:,比较好的一个小区间的宽度选择为w=x

--

intervalP(2n)

1

[7]

。其中x

interval=x

-

max-x-min。

步骤4:找到各个区间中y方向上的两个极值点k[i]1miny和k[i]1maxy。

步骤5:把各个区间中的极值点按照顺序连接起来,如图3所示,首先按照i大小的次序依次连接k[i]1miny,同理连接k[i]1maxy。最后连接xmin和k[0]1miny、x

--

min和k[0]1maxy、x

-

max

和k[m-1]1miny、x-max和k[m-1]1maxy,构成一个封闭的多边形,即前文提到的边界。

图1 P与AB相对位置关系

定义2:采用矢量叉积法判断连续的三矢量顶点的凹凸性,如图2所示

:

图3 边界构成示意图

图2 点的凹凸性判断

步骤6:根据定义1依次判断输入的点是否在边界内部并删除边界内部的点。

步骤7:在平面的离散点集中选择y坐标最小的点,如有相同最小y坐标的点,则选择其中x坐标最小点记为P0。

步骤8:以P0为起点与其它所有点构成矢量P0P1,P0P2,,,P0Pn-1,步骤9:按角度排序所有点,构成一个逆时针顺序的数据结构,作为一个有序的序列。

步骤10:保留同一矢量方向上振幅最大的矢量端点,其余矢量端点删除。

步骤11:根据定义2采判断连续的三矢量顶点的凹凸性。

步骤12:删除所有凹点,所有保留的离散点集即为凸包的子集。

以Vi为其任一顶点,Vi+1和Vi-1为其前后相邻顶点,作矢量叉积:

T=Vi-1Vi@ViVi+1。

取T的z坐标分量,可得点的凹凸性判断函数:

S(Vi,Vi+1,Vi-1)=(xi-xi-1)@(yi+1-yi)-(xi+1-xi)@(yi-yi-1) 根据S的正负号可以判断点Vi的凹凸性。

1)如果S>0,Vi为凸点;2)如果S=0,Vi为中性点;3)如果S<0,Vi为凹点。212 凸包算法描述

算法步骤:

步骤1:读取离散点集的数据坐标及个数n。

,