如何确定多边形点列表是否按顺时针顺序？

有一个点列表，我怎么find，如果他们顺时针顺序？

例如：

point[0] = (5,0) point[1] = (6,4) point[2] = (4,5) point[3] = (1,5) point[4] = (1,0) 

会说这是逆时针（某些人逆时针）。

Answer 1

一些build议的方法在非凸多边形（例如新月形）的情况下将失败。 这里有一个简单的方法，它可以和非凸多边形一起工作（它甚至可以和一个像八的自相交多边形一起工作，告诉你它是否大部分是顺时针的）。

在边上求和，（x ₂ – x ₁ ）（y ₂ + y ₁ ）。 如果结果是正的，曲线是顺时针的，如果是负的，曲线是逆时针的。 （结果是封闭区域的两倍，带有+/-规则。）

 point[0] = (5,0) edge[0]: (6-5)(4+0) = 4 point[1] = (6,4) edge[1]: (4-6)(5+4) = -18 point[2] = (4,5) edge[2]: (1-4)(5+5) = -30 point[3] = (1,5) edge[3]: (1-1)(0+5) = 0 point[4] = (1,0) edge[4]: (5-1)(0+0) = 0 --- -44 counter-clockwise 

Answer 2

因为交叉乘积测量两个vector的过度程度…如果你想象你的多边形的每个边是一个3维xyz空间的xy平面上的vector，那么两个连续边的叉积是（如果第二段是顺时针的）或负Z方向（逆时针）的vector，其大小与两个原始边缘之间的angular度的正弦成比例（当它们达到最大值时是perpindicular）

所以对于多边形的每个顶点（点），计算两个相邻边的叉积大小…

 using your data: point[0] = (5,0) point[1] = (6,4) point[2] = (4,5) point[3] = (1,5) point[4] = (1,0) 

说顶点A（点[0]）在之间

• 边点[4] – >点[0]是边A或vector（1-5,0）=（ – 4,0）
• 边点[0] – >点[1]是边B或vector（6-5,4）=（1,4）

那么它的交叉积是下面matrix的决定因素

  ijk a1 a2 0 b1 b2 0 

要么…

  ijk -4 0 0 1 4 0 

因为所有交叉乘积都垂直于两个向量相乘的平面，所以这将只有一个k（z轴）分量，它的值是a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16这个值的大小是两个原始vector之间的angular度的正弦的量度，乘以这两个vector的大小的乘积。因此，需要将它除以两个vector的幅度的乘积

 |A| * |B| = -16 / (4 * Sqrt(17)) 

（没有必要采取反正弦，所有我们会关心的是标志是正面还是负面）

为其他4点中的每一点做这个，然后加起来。

如果最终总和是正值，则顺时针，负值，逆时针。

Answer 3

我想这是一个相当古老的问题，但我要抛出另一个解决scheme，因为它简单直接，而不是math密集型 – 它只是使用基本的代数。 计算多边形的符号区域。 如果是负值，则按顺时针顺序，如果是正值，则按逆时针顺序。 （这与Beta的解决scheme非常相似。）

计算有符号面积：A = 1/2 *（x ₁ * y ₂ – x ₂ * y ₁ + x ₂ * y ₃ – x ₃ * y ₂ + … + x _n * y ₁ – x ₁ * y _n ）

或者在伪代码中：

 signedArea = 0 for each point in points: x1 = point[0] y1 = point[1] if point is last point x2 = firstPoint[0] y2 = firstPoint[1] else x2 = nextPoint[0] y2 = nextPoint[1] end if signedArea += (x1 * y2 - x2 * y1) end for return signedArea / 2 

请注意，如果你只是检查顺序，你不需要打扰除以2。

来源： http : //mathworld.wolfram.com/PolygonArea.html

Answer 4

以下是由Beta所描述的algorithm的一个简单的C＃实现：

假设我们有一个具有typesdouble X和Y属性的Vectortypes。

 public bool IsClockwise(IList<Vector> vertices) { double sum = 0.0; for (int i = 0; i < vertices.Count; i++) { Vector v1 = vertices[i]; Vector v2 = vertices[(i + 1) % vertices.Count]; // % is the modulo operator sum += (v2.X - v1.X) * (v2.Y + v1.Y); } return sum > 0.0; } 

Answer 5

find最小y的顶点（如果有关系，则最大x）。 设顶点为A，列表中的下一个顶点为B和C.现在计算AB和AC叉积的符号。

参考文献：

• 我如何find一个简单的多边形的方向？ 常见问题解答：comp.graphics.algorithms 。

• 在维基百科的曲线方向 。

Answer 6

从其中一个顶点开始，计算每边所对的angular度。

第一个和最后一个将是零（所以跳过这些）; 对于其余的，angular度的正弦将由（点[n] – 点[0]）和（点[n-1] – 点[0]）的单位长度的归一化的叉积给出。

如果这些值的总和是正值，那么您的多边形按逆时针方向绘制。

Answer 7

顺便说一句：如果在MATLAB中这样做，你可以使用ispolycw 。

我做了这里提出的答案，然后我的同事向我展示了ispolycw函数，这样我就可以知道我浪费了多less时间。 🙁

Answer 8

对于它的价值，我使用这个mixin来计算Google Maps API v3应用程序的收费顺序。

该代码利用了多边形区域的副作用：顶点的顺时针顺序产生正面积，而相同顶点的逆时针顺序产生相同的面积作为负值。 该代码还在Google Maps几何库中使用了一种私有API。 我觉得使用它很自如 – 使用风险自负。

示例用法：

 var myPolygon = new google.maps.Polygon({/*options*/}); var isCW = myPolygon.isPathClockwise(); 

unit testing的完整示例@ http://jsfiddle.net/stevejansen/bq2ec/

 /** Mixin to extend the behavior of the Google Maps JS API Polygon type * to determine if a polygon path has clockwise of counter-clockwise winding order. * * Tested against v3.14 of the GMaps API. * * @author [e-mail] * * @license http://opensource.org/licenses/MIT * * @version 1.0 * * @mixin * * @param {(number|Array|google.maps.MVCArray)} [path] - an optional polygon path; defaults to the first path of the polygon * @returns {boolean} true if the path is clockwise; false if the path is counter-clockwise */ (function() { var category = 'google.maps.Polygon.isPathClockwise'; // check that the GMaps API was already loaded if (null == google || null == google.maps || null == google.maps.Polygon) { console.error(category, 'Google Maps API not found'); return; } if (typeof(google.maps.geometry.spherical.computeArea) !== 'function') { console.error(category, 'Google Maps geometry library not found'); return; } if (typeof(google.maps.geometry.spherical.computeSignedArea) !== 'function') { console.error(category, 'Google Maps geometry library private function computeSignedArea() is missing; this may break this mixin'); } function isPathClockwise(path) { var self = this, isCounterClockwise; if (null === path) throw new Error('Path is optional, but cannot be null'); // default to the first path if (arguments.length === 0) path = self.getPath(); // support for passing an index number to a path if (typeof(path) === 'number') path = self.getPaths().getAt(path); if (!path instanceof Array && !path instanceof google.maps.MVCArray) throw new Error('Path must be an Array or MVCArray'); // negative polygon areas have counter-clockwise paths isCounterClockwise = (google.maps.geometry.spherical.computeSignedArea(path) < 0); return (!isCounterClockwise); } if (typeof(google.maps.Polygon.prototype.isPathClockwise) !== 'function') { google.maps.Polygon.prototype.isPathClockwise = isPathClockwise; } })(); 

Answer 9

对于飞机上的2条线3点，使用这个：

Answer 10

这是一个专门针对OpenLayers的函数function。 正如你所看到的顺时针多边形的条件是区域<0 这个参考确认它。

 function IsClockwise(feature) { if(feature.geometry==null)return -1; var vertices=feature.geometry.getVertices(); var area=0; for (var i = 0; i < (vertices.length); i++) { j = (i + 1) % vertices.length; area += vertices[i].x * vertices[j].y; area -= vertices[j].x * vertices[i].y; // console.log(area); } return (area < 0); } 

Answer 11

这是我使用上述build议的解决scheme

 def segments(poly): """A sequence of (x,y) numeric coordinates pairs """ return zip(poly, poly[1:] + [poly[0]]) def check_clockwise(poly): clockwise = False if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0: clockwise = not clockwise return clockwise poly = [(2,2),(6,2),(6,6),(2,6)] check_clockwise(poly) False poly = [(2, 6), (6, 6), (6, 2), (2, 2)] check_clockwise(poly) True 

Answer 12

我认为为了顺时针给定一些点，所有的边缘都必须是正的，而不仅仅是边缘的总和。 如果一个边缘是负的，至less有3个点是逆时针的。

Answer 13

我的C＃/ LINQ解决scheme基于@charlesbretana的交叉产品build议如下。 您可以指定绕组的参考法线。 只要曲线大部分在向上向量所定义的平面内，它就应该工作。

 using System.Collections.Generic; using System.Linq; using System.Numerics; namespace SolidworksAddinFramework.Geometry { public static class PlanePolygon { /// <summary> /// Assumes that polygon is closed, ie first and last points are the same /// </summary> public static bool Orientation (this IEnumerable<Vector3> polygon, Vector3 up) { var sum = polygon .Buffer(2, 1) // from Interactive Extensions Nuget Pkg .Where(b => b.Count == 2) .Aggregate ( Vector3.Zero , (p, b) => p + Vector3.Cross(b[0], b[1]) /b[0].Length()/b[1].Length()); return Vector3.Dot(up, sum) > 0; } } } 

用unit testing

 namespace SolidworksAddinFramework.Spec.Geometry { public class PlanePolygonSpec { [Fact] public void OrientationShouldWork() { var points = Sequences.LinSpace(0, Math.PI*2, 100) .Select(t => new Vector3((float) Math.Cos(t), (float) Math.Sin(t), 0)) .ToList(); points.Orientation(Vector3.UnitZ).Should().BeTrue(); points.Reverse(); points.Orientation(Vector3.UnitZ).Should().BeFalse(); } } } 

Answer 14

对于任何人，只是试图在Python中实现这个解决scheme：在testing了几个不可靠的实现之后，提供了关于cw / ccw取向的令人满意的结果的algorithm是OP在这个线程（shoelace_formula_3）中发布的algorithm。

一如既往：正数为CW，负数CCW。

Answer 15

Sean在JavaScript中的答案的实现：

 function calcArea(poly) { if(!poly || poly.length < 3) return null; let end = poly.length - 1; let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1]; for(let i=0; i<end; ++i) { const n=i+1; sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1]; } return sum; } function isClockwise(poly) { return calcArea(poly) > 0; } let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]]; console.log(isClockwise(poly)); let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]]; console.log(isClockwise(poly2)); 

Answer 16

find这些点的质量中心。

假设有从这一点到你的观点的线。

findline0 line1的两条线之间的angular度

比line1和line2要好

…

…

如果该angular度比逆时针单调递增，

否则如果单调递减是顺时针的

其他（这不是单调的）

你不能决定，所以这是不明智的