这一篇说说求凸包的Graham算法的代码。
typedef struct tPointStructure tsPoint;
typedef tsPoint *tPoint;
struct tPointStructure {
int vnum;
tPointi v;
bool delete;
};
一个点包含的信息：编号vnum，坐标v，是否因共线等原因需要删除delete。
程序中的堆栈，用链表实现：
typedef struct tStackCell tsStack; /* Used on in NEW() */
typedef tsStack *tStack;
struct tStackCell {
tPoint p;
tStack next;
};
堆栈的push和pop实现都很简单，不展示了。
寻找排序的参考点。
void FindLowest( void ) {
int i;
int m = 0; /* Index of lowest so far. */
for ( i = 1; i < n; i++ )
if ( (P[i].v[Y] < P[m].v[Y]) ||
((P[i].v[Y] == P[m].v[Y]) && (P[i].v[X] > P[m].v[X])) )
m = i;
printf("Swapping %d with 0\n", m);
Swap(0,m); /* Swap P[0] and P[m] */
}
就是寻找给定的点集中y坐标最小同时x坐标最大的一个点。然后把它换到p[0]
排序是按照角度。选定的排序参考点是给定点集中y坐标最小的一个点，
因此所有点的角度都在[0, 180]区间，这已经简化很多了。
但是显然的，不论是使用现成的atan2函数还是用计算斜率的方法，
都会遇到浮点数计算误差的问题。
解决这个问题还是求助于我们的老朋友Area2()就可以了。
如果p[t-1],pt,pi形成的三角形面积大于0，pi就在直线p[t-1],pt左边
如果面积等于0，这三个点就是共线的。
排序过程使用了C标准库中的qsort方法。比较元素大小的函数是：
int Compare( const void *tpi, const void *tpj ) {
int a; /* area */
int x, y; /* projections of ri & rj in 1st quadrant */
tPoint pi, pj;
pi = (tPoint)tpi;
pj = (tPoint)tpj;
a = AreaSign( P[0].v, pi->v, pj->v );
if (a > 0)
return -1;
else if (a < 0)
return 1;
else { /* Collinear with P[0] */
x = abs( pi->v[X] - P[0].v[X] ) - abs( pj->v[X] - P[0].v[X] );
y = abs( pi->v[Y] - P[0].v[Y] ) - abs( pj->v[Y] - P[0].v[Y] );
ndelete++;
if ( (x < 0) || (y < 0) ) {
pi->delete = TRUE;
return -1;
}
else if ( (x > 0) || (y > 0) ) {
pj->delete = TRUE;
return 1;
}
else { /* points are coincident */
if (pi->vnum > pj->vnum)
pj->delete = TRUE;
else
pi->delete = TRUE;
return 0;
}
}
}
需要解释一下最后一个else分支。
程序求出点pi和pj在x，y轴上的投影到原点距离的差值。
明显的，哪个点在坐标轴上的投影距离原点远，哪个点本身就距离原点更远。
上次说了，如果两个点共线，距离原点较近的那个肯定不是凸包的顶点，
可以把它标记为删除。如果两个点重合，规定删除编号较小的一个。
算法的主要过程就是实现上一篇中描述的计算过程，没啥可说的：
tStack Graham() {
tStack top;
int i;
tPoint p1, p2; /* Top two points on stack. */
top = NULL;
top = Push ( &P[0], top );
top = Push ( &P[1], top );
/* Bottom two elements will never be removed. */
i = 2;
while ( i < n ) {
if( !top->next) printf("Error\n"),exit(EXIT_FAILURE);
p1 = top->next->p;
p2 = top->p;
if ( Left( p1->v , p2->v, P[i].v ) ) {
top = Push ( &P[i], top );
i++;
} else
top = Pop( top );
}
return top;
}
主函数。唯一需要提一下的就是qsort之后，Squash()删除所有delete标记
为true的点，更新数组。数组P，变量n, ndelete都是全局的。代码是：
main() {
tStack top;
n = ReadPoints();
FindLowest();
PrintPoints();
qsort(
&P[1], /* pointer to 1st elem */
n-1, /* number of elems */
sizeof( tsPoint ), /* size of each elem */
Compare /* -1,0,+1 compare function */
);
if (ndelete > 0) {
Squash();
printf("After squashing:\n");
}
top = Graham();
printf("Hull:\n");
PrintStack( top );
PrintPostscript( top );
}
阅读(660) | 评论(0) | 转发(0) |
