有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
会说它是逆时针的(对某些人来说是逆时针的)
有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
会说它是逆时针的(对某些人来说是逆时针的)
当前回答
如果使用Matlab,如果多边形顶点按顺时针顺序排列,函数ispolycw将返回true。
其他回答
我的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();
}
}
}
如果使用Matlab,如果多边形顶点按顺时针顺序排列,函数ispolycw将返回true。
对于那些不想“重新发明轮子”的人,我认为值得一提的是,这个检查是在一个名为Shapely (github)的漂亮的Python包中实现的(它基于GEOS C/ c++库):
Shapely is a BSD-licensed Python package for manipulation and analysis of planar geometric objects. It is using the widely deployed open-source geometry library GEOS (the engine of PostGIS, and a port of JTS). Shapely wraps GEOS geometries and operations to provide both a feature rich Geometry interface for singular (scalar) geometries and higher-performance NumPy ufuncs for operations using arrays of geometries. Shapely is not primarily focused on data serialization formats or coordinate systems, but can be readily integrated with packages that are.
来源:https://shapely.readthedocs.io/en/stable/
一个给出OP坐标的小例子:
import numpy as np
from shapely.geometry import Polygon
points = np.array([
(5,0),
(6,4),
(4,5),
(1,5),
(1,0)
])
P = Polygon(points)
这是新构造的多边形:
import matplotlib.pyplot as plt
x,y = P.exterior.coords.xy
plt.plot(x,y)
plt.axis('equal')
plt.grid()
plt.show()
你可以直接使用LinearRing的is_ccw属性来检查多边形是CW还是CCW:
type(P.exterior)
>: shapely.geometry.polygon.LinearRing
P.exterior.is_ccw
>: True
如果颠倒:
points = np.flipud(points)
points
>:
array([[1, 0],
[1, 5],
[4, 5],
[6, 4],
[5, 0]])
P1 = Polygon(points)
P1.exterior.is_ccw
>: True
进一步阅读的文档和参考资料:
shaely is_ccw (github): https://github.com/shapely/shapely/blob/eba985c6e0170ecdd90c83592fd0afa7ae793cb8/shapely/predicates.py#L72-L108 Libgeos (github): https://github.com/libgeos/geos GEOS API参考:https://libgeos.org/doxygen/classgeos_1_1algorithm_1_1Orientation.html#a5af93795969b80f97d7997195974d7c8 GEOS实现(github): https://github.com/libgeos/geos/blob/ab0ce6dafdf7f75ec6d234b6c65bb209037dda17/src/algorithm/Orientation.cpp#L43-L133
在测试了几个不可靠的实现之后,在CW/CCW方向方面提供令人满意结果的算法是由OP在这个线程(shoelace_formula_3)中发布的算法。
与往常一样,正数表示CW方向,而负数表示CCW方向。
解决方案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