问个小问题啊，有思路就可以 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>CS - 计算机科学

问个小问题啊，有思路就可以

问个小问题啊，有思路就可以# CS - 计算机科学

r*o2005-03-13 08:03

1 楼

有若干个点，坐标知道。怎么才能给他们排序，使得：如果一条线从第一个点连到最后一
个点再到第一个点，能组成一个封闭的形状。有时候可能有不同的连法，随便怎么都可以
，但是连线不能交叉。然后给这个封闭的形状填充颜色。
其实我很菜，是想用vb for excel来做这个问题。不知道可能吗？

j*h2005-03-13 08:03

2 楼

1.选取屏幕最左边（x坐标最小）的点作为起点。
2.连接该起点与其余所有点的射线，计算所有的射线的幅角，并将这些俯角排序。
3.按排好的顺序，依次连接各点。就构成了你想要的多边形。

【在 r*******o 的大作中提到】

: 有若干个点，坐标知道。怎么才能给他们排序，使得：如果一条线从第一个点连到最后一
: 个点再到第一个点，能组成一个封闭的形状。有时候可能有不同的连法，随便怎么都可以
: ，但是连线不能交叉。然后给这个封闭的形状填充颜色。
: 其实我很菜，是想用vb for excel来做这个问题。不知道可能吗？

A*l2005-03-13 08:03

3 楼

我的思路是：
0.initialize two array: beginning array and destination array.
1. 按X坐标大小给所有点编号( 1 has the smallest X value)
2. 连接1，2这样经过1，2的直线把平面分为两个部分。如果所有的点都在期中一个部分
，go on (将1,2放入目标数组中,并且从初始数组中删除). else, 连接1,3; 1,4 until条
件满足为止。
3.假设上面的算法连接的是点1，2，继续连接点2，3(就是现有的未连接的点中序号最小
的那一个,或者说初始数组中第一个元素) 如果所有的点都在直线2，3的一面，go on，否
则try 2,4..2,5
4.继续，知道所有的点都被连上(初始数组为空)。最后一个点连回点1。

后一
可以

【在 j*****h 的大作中提到】

: 1.选取屏幕最左边（x坐标最小）的点作为起点。
: 2.连接该起点与其余所有点的射线，计算所有的射线的幅角，并将这些俯角排序。
: 3.按排好的顺序，依次连接各点。就构成了你想要的多边形。