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

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

例如:

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

会说这是逆时针(某些人逆时针)。

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

在边上求和,(x 2 – x 1 )(y 2 + y 1 )。 如果结果是正的,曲线是顺时针的,如果是负的,曲线是逆时针的。 (结果是封闭区域的两倍,带有+/-规则。)

 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 

因为交叉乘积测量两个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点中的每一点做这个,然后加起来。

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

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

计算有符号面积:A = 1/2 *(x 1 * y 2 – x 2 * y 1 + x 2 * y 3 – x 3 * y 2 + … + x n * y 1 – x 1 * 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

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

假设我们有一个具有typesdouble XY属性的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; } 

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

参考文献:

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

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

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

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

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

顺便说一句:如果在MATLAB中这样做,你可以使用ispolycw

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

对于它的价值,我使用这个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 stevejansen_github@icloud.com * * @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; } })(); 

对于飞机上的2条线3点,使用这个:

在这里输入图像描述

这是一个专门针对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); } 

这是我使用上述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 

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

我的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(); } } } 

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

一如既往:正数为CW,负数CCW。

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)); 

find这些点的质量中心。

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

findline0 line1的两条线之间的angular度

比line1和line2要好

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

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

其他(这不是单调的)

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