已知n凸多边形的各顶点坐标 如何将他们顺时针排列

来源：百度知道 编辑：UC知道 时间：2024/06/30 08:23:08
已知n凸多边形的n个顶点的坐标 如何将他们顺时针排列

坐标都是不超过100的正整数,分别储存在int x[n] 和 int y[n]里面.

对于同一个编号为i(0<=i<n)的点，它的坐标为(x[i],y[i]).

新建int sx[n],sy[n];

如何把上面n个顶点按照顺时针的顺序放进新的数组里面（开始的点不管，只要是顺时针就可以了）。
只要算法.....

给出代码也可以.

要求 C/C++.

(1)找一个内点
(2)计算这个内点到各顶点的角度0-360度
(3)按角度排序

找一个内点：
任选3点x1,y1,x2,y2,x3,y3
计算：
x0=(x1 + x2 + x3)/3
y0=(y1 + y2 + y3)/3.

计算这个内点到各顶点的角度：
dy=yi-y0
dx=xi-x0
ds=sqrt(dx*dx+dy*dy)
sin(Ai) = dy/ds
判断象限。

排序不用说了吧。

最基本的凸包问题啊。
算法导论上有详细的两种扫描法的讲解，可以去看一下。
一般的算法书上都会有凸包的讲解。

给个最简单的算法（算法导论的第一种方法，俗称“卷包裹”）：
以最右侧点为起始点，顺时针扫描直到碰到第一个点，放如数组，并将此点设为起始点，再进行下次扫描。。。知道所有点都放入数组。形式上看就像围篱笆。