新手求教：给定一个多边形的顶点序列，如何判断出其序

liurunfeng

已知一个多边形的顶点序列，我写了一个算法将其三角化，但其只能对顺时针的顶点序列能够正常运行，对于逆时针方向的序列就无法正常运行了。如何判断多边形的顶点序列是顺时针的还是逆时针的。
或者有能够忽略顶点方向的三角化方法么？
谢谢！

congy

你的算法是针对凸多边形还是凹多边形？如果是凸，并且给定的顶点序列是连续的，可以通过判断两点之间线段的点积，求出两线段之间的夹角的，大于180顺时针，小于180逆时针。

xgreenclover

根据外角和的正负判断？

liurunfeng

多边形是任意的，即可能是图多边形，也可能是凹多边形。

hugp1973

假设给定多边形顶点序列为0,1,....n,找出多边形的最大点，最小点在顶点序列中的索引，假定分别为a,b,以顶点a,（a==0?n-1: a+1）,b三点组成三角形，然后再判断。

hugp1973

嘿嘿，给定的答案有缺陷，但是思路就是先找出最大点和最小点，再另外找和最大点，或者最小点相邻的点。然后再判断。

lingjingqiu

同2楼，凸多边形O(1)
凹多边形似乎是O(n)...

xgreenclover

hugp1973: Re:新手求教：给定一个多边形的顶点序列，如何判断出其序列是顺时针还是逆时针的

假设给定多边形顶点序列为0,1,....n,找出多边形的最大点，最小点在顶点序列中的索引，假定分别为a,b,以顶点a,（a==0?n-1: a+1）,b三点组成三角形，然后再判断。

请教什么是最大点，什么是最小点？谢谢。

Enigmaya

我上次也是三角剖分的时候遇到这个问题的。。。呵呵

最简单的就是平均取3点，计算叉乘，再根据符号判断绕向，不过个别凹多边形的会出错。

所以用最大最小点(某一方向的极值，如左上角的点)来取这3点，以保证不会取到凹的顶点。

好像还有一种方法，好像和角度和有关，记不清了。

具体可以去看看 《计算几何》 和 《计算机图形学几何工具算法详解》。

liurunfeng

多谢大家，我找了一个算法，就是扇形计算多边形面积的，如果结果为正，则定为正向，如果为负，则定为负向。算法时间复杂度为o(n)，不是很理想。
看了大家的回答，感觉去极点的方式应该比较快，去试一下。