已知n凸多边形的各顶点坐标 如何将他们顺时针排列
已知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
判断象限。
排序不用说了吧。
(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
判断象限。
排序不用说了吧。
温馨提示：内容为网友见解，仅供参考
第1个回答 2008-10-11
最基本的凸包问题啊。
算法导论上有详细的两种扫描法的讲解，可以去看一下。
一般的算法书上都会有凸包的讲解。
给个最简单的算法（算法导论的第一种方法，俗称“卷包裹”）：
以最右侧点为起始点，顺时针扫描直到碰到第一个点，放如数组，并将此点设为起始点，再进行下次扫描。。。知道所有点都放入数组。形式上看就像围篱笆。
算法导论上有详细的两种扫描法的讲解，可以去看一下。
一般的算法书上都会有凸包的讲解。
给个最简单的算法（算法导论的第一种方法，俗称“卷包裹”）：
以最右侧点为起始点，顺时针扫描直到碰到第一个点，放如数组，并将此点设为起始点，再进行下次扫描。。。知道所有点都放入数组。形式上看就像围篱笆。
第2个回答 2019-04-26
将这些点全部画在CAD里面，然后按照顺时针方向排列就可以了
第3个回答 2019-04-26
凸多边形是一个内部为凸集的简单多边形。凸多边形（Convex Polygon）指如果把一个多边形的所有边中，任意一条边向两方无限延长成为一直线时，其他各边都在此直线的同侧，那么这个多边形就叫做凸多边形，否则就是凹多边形。凸多边形的内角应该全不是优角，任意两个顶点间的线段位于多边形的内部或边上。
凸多边形（Convex Polygon）可以有以下三种定义：
没有任何一个内角是优角（Reflexive Angle）的多边形。
如果把一个多边形的所有边中，有一条边向两方无限延长成为一直线时，其他各边都在此直线的同一侧，那么这个多边形就叫做凸多边形。
凸多边形是一个内部为凸集的简单多边形。简单多边形的下列性质与其凸性等价：
1、所有内角小于等于180度。
2、任意两个顶点间的线段位于多边形的内部或边上。
3、多边形内任意两个点，其连线全部在多边形内部或边上。
所有的正多边形都是凸多边形。
所有的三角形都是凸多边形。
希望我能帮助你解疑释惑。
凸多边形（Convex Polygon）可以有以下三种定义：
没有任何一个内角是优角（Reflexive Angle）的多边形。
如果把一个多边形的所有边中，有一条边向两方无限延长成为一直线时，其他各边都在此直线的同一侧，那么这个多边形就叫做凸多边形。
凸多边形是一个内部为凸集的简单多边形。简单多边形的下列性质与其凸性等价：
1、所有内角小于等于180度。
2、任意两个顶点间的线段位于多边形的内部或边上。
3、多边形内任意两个点，其连线全部在多边形内部或边上。
所有的正多边形都是凸多边形。
所有的三角形都是凸多边形。
希望我能帮助你解疑释惑。
第4个回答 2019-04-26
你已触犯银河正义法中不可饶恕之蛇皮罪，我独秀铠甲将剥夺你的一切权利并对你实行封印缉捕，束手就擒吧
相似回答
