有一个点列表,我如何找到顺时针顺序?
例如:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
会说它是逆时针(或逆时针,对某些人来说)。
在非凸多边形(例如新月形)的情况下,一些建议的方法将失败。这是一个非常简单的非凸多边形(它甚至可以使用自相交的多边形,如图8,告诉你它是否主要是顺时针方向)。
边上的和,(x2 - x1)(y2 + y1)。如果结果为正,则曲线为顺时针,如果为负,则曲线为逆时针。 (结果是封闭区域的两倍,带有+/-约定。)
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
这是OpenLayers 2的实现功能。具有顺时针多边形的条件是area < 0
,由this reference确认。
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);
}
正如在维基百科文章Curve orientation中所解释的那样,在平面上给出3点p
,q
和r
(即使用x和y坐标),您可以计算以下行列式的符号
如果行列式是负的(即Orient(p, q, r) < 0
),则多边形顺时针(CW)定向。如果行列式是正的(即Orient(p, q, r) > 0
),则多边形逆时针(CCW)定向。如果点Orient(p, q, r) == 0
,p
和q
是r
,则行列式为零(即collinear)。
在上面的公式中,我们在p
,q
和r
的坐标前面加上那些,因为我们使用的是homogeneous coordinates。
我认为为了顺时针给出一些点,所有边缘都需要是正的而不仅仅是边的总和。如果一个边是负的,则逆时针给出至少3个点。
我的C#/ LINQ解决方案基于@charlesbretana的交叉产品建议如下。您可以指定绕组的参考法线。只要曲线主要位于由向上矢量定义的平面中,它就应该工作。
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;
}
}
}
单元测试
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();
}
}
}
这是我的解决方案,使用其他答案中的解释:
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
如果您已经知道多边形内的一个点,那么计算方法就更简单了:
在测试了几个不可靠的实现之后,开箱即用的CW / CCW方向提供了令人满意的结果的算法是OP在this线程(shoelace_formula_3
)中发布的算法。
与往常一样,正数表示CW方向,而负数表示CCW。
这是基于以上答案的快速3.0解决方案:
for (i, point) in allPoints.enumerated() {
let nextPoint = i == allPoints.count - 1 ? allPoints[0] : allPoints[i+1]
signedArea += (point.x * nextPoint.y - nextPoint.x * point.y)
}
let clockwise = signedArea < 0
另一个解决方案;
const isClockwise = (vertices=[]) => {
const len = vertices.length;
const sum = vertices.map(({x, y}, index) => {
let nextIndex = index + 1;
if (nextIndex === len) nextIndex = 0;
return {
x1: x,
x2: vertices[nextIndex].x,
y1: x,
y2: vertices[nextIndex].x
}
}).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);
if (sum > -1) return true;
if (sum < 0) return false;
}
将所有顶点作为这样的数组;
const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);
R确定方向的解决方案,如果顺时针方向反转(发现对于owin对象是必要的):
coords <- cbind(x = c(5,6,4,1,1),y = c(0,4,5,5,0))
a <- numeric()
for (i in 1:dim(coords)[1]){
#print(i)
q <- i + 1
if (i == (dim(coords)[1])) q <- 1
out <- ((coords[q,1]) - (coords[i,1])) * ((coords[q,2]) + (coords[i,2]))
a[q] <- out
rm(q,out)
} #end i loop
rm(i)
a <- sum(a) #-ve is anti-clockwise
b <- cbind(x = rev(coords[,1]), y = rev(coords[,2]))
if (a>0) coords <- b #reverses coords if polygon not traced in anti-clockwise direction
cross product测量两个向量的垂直度。想象一下,多边形的每个边都是三维(3-D)xyz空间的x-y平面中的向量。然后,两个连续边的叉积是z方向上的矢量,(如果第二段是顺时针,则为正z方向,如果是逆时针,则为z方向)。该矢量的大小与两个原始边缘之间的角度的正弦成比例,因此当它们垂直时达到最大值,并且当边缘共线(平行)时逐渐减小以消失。
因此,对于多边形的每个顶点(点),计算两个相邻边的叉积大小:
Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)
因此,将边缘连续标记为
edgeA
是从point0
到point1
和
在edgeB
和point1
之间的point2
...
edgeE
介于point4
和point0
之间。
然后Vertex A(point0
)介于两者之间
edgeE
[从point4
到point0
]
edgeA
[从point0
到`point1'
这两个边本身就是向量,其x和y坐标可以通过减去它们的起点和终点的坐标来确定:
edgeE
= point0
- point4
= (1, 0) - (5, 0)
= (-4, 0)
and
edgeA
= point1
- point0
= (6, 4) - (1, 0)
= (5, 4)
and
并且使用以下矩阵的行列式计算这两个相邻边的叉积,该矩阵是通过将两个向量的坐标置于表示三个坐标轴(i
,j
,&k
)的符号下面而构造的。第三个(零)值坐标是因为交叉积概念是三维构造,因此我们将这些二维向量扩展为三维以应用交叉积:
i j k
-4 0 0
1 4 0
假设所有交叉乘积产生垂直于两个矢量平面的矢量,则上述矩阵的行列式仅具有k
,(或z轴)分量。
计算k
或z轴分量的大小的公式是
a1*b2 - a2*b1 = -4* 4 - 0* 1
= -16
该值的大小(-16
)是2个原始矢量之间角度的正弦的乘积,乘以2个矢量的大小的乘积。
实际上,其价值的另一个公式是
A X B (Cross Product) = |A| * |B| * sin(AB)
。
因此,为了回到角度的一个度量,你需要将这个值(-16
)除以两个向量的大小的乘积。
|A| * |B|
4 * Sqrt(17)
= = 16.4924...
所以罪的衡量标准(AB)= -16 / 16.4924
= -.97014...
这是衡量顶点向左或向右弯曲后的下一个段的度量,以及是多少。没有必要采用正弦波。我们所关心的只是它的大小,当然还有它的标志(正面或负面)!
对闭合路径周围的其他4个点中的每个点执行此操作,并在每个顶点处将此计算中的值相加。
如果最终总和为正,则顺时针方向,负方向,逆时针方向。
虽然这些答案是正确的,但它们在数学上比必要的更强烈。假设地图坐标,其中最北点是地图上的最高点。找到最北点,如果2点并列,则最北,然后最东(这是lhf在他的答案中使用的点)。在你的观点中,
point [0] =(5,0)
点[1] =(6,4)
点[2] =(4,5)
点[3] =(1,5)
点[4] =(1,0)
如果我们假设P2是最北,那么前一点或下一点确定顺时针,CW或CCW。由于最北点位于北面,如果P1(前一个)到P2向东移动,则方向为CW。在这种情况下,它向西移动,所以方向是CCW,正如接受的答案所说。如果前一个点没有水平移动,则同一系统应用于下一个点P3。如果P3在P2的西边,那么移动是CCW。如果P2到P3的运动是向东的,那么在这种情况下它是向西,运动是CW。假设数据中的nte,P2是最北,然后是东点,prv是前一个点,数据中是P1,nxt是下一个点,数据中是P3,[0]是水平或东/西部小于东部的西部,[1]是垂直的。
if (nte[0] >= prv[0] && nxt[0] >= nte[0]) return(CW);
if (nte[0] <= prv[0] && nxt[0] <= nte[0]) return(CCW);
// Okay, it's not easy-peasy, so now, do the math
if (nte[0] * nxt[1] - nte[1] * nxt[0] - prv[0] * (nxt[1] - crt[1]) + prv[1] * (nxt[0] - nte[0]) >= 0) return(CCW); // For quadrant 3 return(CW)
return(CW) // For quadrant 3 return (CCW)
实现lhf's answer的C#代码:
// https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
public static WindingOrder DetermineWindingOrder(IList<Vector2> vertices)
{
int nVerts = vertices.Count;
// If vertices duplicates first as last to represent closed polygon,
// skip last.
Vector2 lastV = vertices[nVerts - 1];
if (lastV.Equals(vertices[0]))
nVerts -= 1;
int iMinVertex = FindCornerVertex(vertices);
// Orientation matrix:
// [ 1 xa ya ]
// O = | 1 xb yb |
// [ 1 xc yc ]
Vector2 a = vertices[WrapAt(iMinVertex - 1, nVerts)];
Vector2 b = vertices[iMinVertex];
Vector2 c = vertices[WrapAt(iMinVertex + 1, nVerts)];
// determinant(O) = (xb*yc + xa*yb + ya*xc) - (ya*xb + yb*xc + xa*yc)
double detOrient = (b.X * c.Y + a.X * b.Y + a.Y * c.X) - (a.Y * b.X + b.Y * c.X + a.X * c.Y);
// TBD: check for "==0", in which case is not defined?
// Can that happen? Do we need to check other vertices / eliminate duplicate vertices?
WindingOrder result = detOrient > 0
? WindingOrder.Clockwise
: WindingOrder.CounterClockwise;
return result;
}
public enum WindingOrder
{
Clockwise,
CounterClockwise
}
// Find vertex along one edge of bounding box.
// In this case, we find smallest y; in case of tie also smallest x.
private static int FindCornerVertex(IList<Vector2> vertices)
{
int iMinVertex = -1;
float minY = float.MaxValue;
float minXAtMinY = float.MaxValue;
for (int i = 0; i < vertices.Count; i++)
{
Vector2 vert = vertices[i];
float y = vert.Y;
if (y > minY)
continue;
if (y == minY)
if (vert.X >= minXAtMinY)
continue;
// Minimum so far.
iMinVertex = i;
minY = y;
minXAtMinY = vert.X;
}
return iMinVertex;
}
// Return value in (0..n-1).
// Works for i in (-n..+infinity).
// If need to allow more negative values, need more complex formula.
private static int WrapAt(int i, int n)
{
// "+n": Moves (-n..) up to (0..).
return (i + n) % n;
}
找到这些点的质量中心。
假设从这一点到你的观点都有一条线。
找到line0 line1的两行之间的角度
而不是line1和line2
...
...
如果这个角度单调增加而不是逆时针,
否则,如果单调减少它是顺时针
别的(它不是单调的)
你不能决定,所以这不明智
我想这是一个非常古老的问题,但无论如何我都会抛弃另一个解决方案,因为它很简单而且不是数学密集型 - 它只是使用基本代数。计算多边形的有符号区域。如果它是负数,则点是顺时针顺序,如果它是正数,则它们是逆时针。 (这与Beta的解决方案非常相似。)
计算有符号区域:A = 1/2 *(x1 * y2 - x2 * y1 + x2 * y3 - x3 * y2 + ... + xn * y1 - x1 * yn)
或者在伪代码中:
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。
找到y最小的顶点(如果有连接则找到最大的x)。设顶点为A
,列表中的前一个顶点为B
,列表中的下一个顶点为C
。现在计算AB
和AC
的叉积的符号。
参考文献:
这是基于this answer的算法的简单C#实现。
让我们假设我们有一个Vector
类型具有X
类型的Y
和double
属性。
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];
sum += (v2.X - v1.X) * (v2.Y + v1.Y);
}
return sum > 0.0;
}
%
是执行模运算的模运算或余数运算符,(according to Wikipedia)在将一个数除以另一个数之后找到余数。
从其中一个顶点开始,计算每一侧所对的角度。
第一个和最后一个将为零(所以跳过那些);对于其余部分,角度的正弦将由归一化与单位长度(点[n] - 点[0])和(点[n-1] - 点[0])的叉积给出。
如果值的总和为正,则以逆时针方向绘制多边形。
对于它的价值,我使用这个mixin来计算Google Maps API v3应用程序的上弦顺序。
该代码利用了多边形区域的副作用:顶点的顺时针缠绕顺序产生正区域,而相同顶点的逆时针缠绕顺序产生与负值相同的区域。该代码还在Google Maps几何库中使用了一种私有API。我觉得使用它很舒服 - 使用风险自负。
样品用法:
var myPolygon = new google.maps.Polygon({/*options*/});
var isCW = myPolygon.isPathClockwise();
完整的单元测试示例@ 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 [email protected]
*
* @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;
}
})();
在JavaScript中实现Sean's answer:
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));
很确定这是对的。它似乎工作:-)
如果你想知道那些多边形看起来像这样:
如果使用Matlab,如果多边形顶点按顺时针顺序,则函数ispolycw
返回true。