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
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();
}
}
}
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
/** 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;
}
})();
20 回答
这是我的解决方案,使用其他答案中的解释:
R确定方向的解决方案,如果是顺时针方向则反转(发现对于owin对象是必要的):
找到这些点的质量中心 .
假设从这一点到你的观点都有一条线 .
找到line0 line1的两行之间的角度
而不是line1和line2
...
...
如果这个角度单调增加而不是逆时针,
否则,如果单调减少它是顺时针
别的(这不是单调的)
你不能决定,所以这不明智
我的C#/ LINQ解决方案基于@charlesbretana的交叉产品建议如下 . 您可以指定绕组的参考法线 . 只要曲线主要位于由向上矢量定义的平面中,它就应该工作 .
进行单元测试
在测试了几个不可靠的实现之后,提供了关于开箱即用的CW / CCW方向的令人满意的结果的算法是OP在this thread(
shoelace_formula_3
)中发布的算法 .与往常一样,正数表示CW方向,而负数表示CCW .
我认为为了顺时针给出一些点,所有边缘都需要是正的而不仅仅是边的总和 . 如果一个边是负的,则逆时针给出至少3个点 .
这是OpenLayers 2的实现函数 . 具有顺时针多边形的条件是
area < 0
,由this reference确认 .JavaScript中Sean's answer的实现:
很确定这是对的 . 它似乎工作:-)
如果你想知道那些多边形看起来像这样:
正如本维基百科文章Curve orientation中所解释的那样,在平面上给出3点
p
,q
和r
(即使用x和y坐标),您可以计算以下行列式的符号如果行列式是负的(即
Orient(p, q, r) < 0
),则多边形顺时针(CW)定向 . 如果行列式是正的(即Orient(p, q, r) > 0
),则多边形逆时针(CCW)定向 . 如果点p
,q
和r
是collinear,则行列式为零(即Orient(p, q, r) == 0
) .在上面的公式中,我们在
p
,q
和r
的坐标前面加上那些,因为我们使用homogeneous coordinates .从其中一个顶点开始,计算每一侧所对的角度 .
第一个和最后一个将为零(所以跳过那些);对于其余部分,角度的正弦将由归一化与(点[n] - 点[0])和(点[n-1] - 点[0])的单位长度的叉积给出 .
如果值的总和为正,则以逆时针方向绘制多边形 .
如果使用Matlab,如果多边形顶点按顺时针顺序,函数ispolycw将返回true .
我想这是一个非常古老的问题,但无论如何我都会抛出另一个解决方案,因为它很简单,而且不是数学密集的 - 它只是使用基本代数 . 计算多边形的有符号区域 . 如果它是负数,则点是顺时针顺序,如果它是正数,则它们是逆时针 . (这与Beta的解决方案非常相似 . )
计算有符号区域:A = 1/2 *(x1 * y2 - x2 * y1 x2 * y3 - x3 * y2 ... xn * y1 - x1 * yn)
或者在伪代码中:
请注意,如果您只是检查订购,则无需费力除以2 .
资料来源:http://mathworld.wolfram.com/PolygonArea.html
这是基于以上答案的快速3.0解决方案:
在非凸多边形(例如新月形)的情况下,一些建议的方法将失败 . 这里's a simple one that will work with non-convex polygons (it' ll甚至可以使用像八字形一样的自相交多边形,告诉你它是否主要是顺时针方向) .
边上的和,(x2 - x1)(y2 y1) . 如果结果为正,则曲线为顺时针,如果为负,则曲线为逆时针 . (结果是封闭区域的两倍,使用/ - 约定 . )
另一个解决方案;
将所有顶点作为这样的数组;
cross product测量两个向量的垂直度 . 想象一下,多边形的每个边都是三维(3-D)xyz空间的x-y平面中的向量 . 然后,两个连续边的叉积是z方向上的矢量,(如果第二段是顺时针,则为正z方向,如果是逆时针,则为z方向) . 该矢量的大小与两个原始边缘之间的角度的正弦成比例,因此当它们垂直时达到最大值,并且当边缘是锥形时逐渐减小以消失 . 共线(平行) .
因此,对于多边形的每个顶点(点),计算两个相邻边的叉积大小:
因此,将边缘连续标记为
edgeA
是从point0
到point1
的段edgeB
介于point1
至point2
之间...
edgeE
介于point4
和point0
之间 .然后是顶点A(
point0
)edgeE
[从point4
到point0
]edgeA
[从point0
到'point1'这两个边是它们自己的向量,其x和y坐标可以通过减去它们的起点和终点的坐标来确定:
edgeE
=point0
-point4
=(1, 0) - (5, 0)
=(-4, 0)
和edgeA
=point1
-point0
=(6, 4) - (1, 0)
=(5, 4)
和并且使用以下矩阵的行列式计算这两个相邻边的叉积,该矩阵是通过将两个向量的坐标放在表示三个坐标轴(
i
,j
,&k
)的符号下面而构造的 . 第三个(零)值坐标是因为交叉积概念是三维构造,因此我们将这些二维向量扩展为三维以应用交叉积:假设所有交叉乘积产生垂直于两个矢量平面的矢量,则上述矩阵的行列式仅具有
k
,(或z轴)分量 .计算
k
或z轴分量的大小的公式是a1*b2 - a2*b1 = -4* 4 - 0* 1
=-16
该值的大小(
-16
)是2个原始矢量之间角度的正弦值的乘积,乘以2个矢量的幅度乘积 .实际上,其 Value 的另一个公式是
A X B (Cross Product) = |A| * |B| * sin(AB)
.因此,要回到角度的度量,您需要将此值(
-16
)除以两个向量的大小的乘积 .|A| * |B|
=4 * Sqrt(17)
=16.4924...
所以罪的衡量标准(AB)=
-16 / 16.4924
=-.97014...
这是衡量顶点向左或向右弯曲后的下一个段以及多少的度量 . 没有必要采用正弦波 . 我们所关心的只是它的大小,当然还有它的标志(正面或负面)!
对闭合路径周围的其他4个点中的每个点执行此操作,并在每个顶点处将此计算中的值相加 .
如果最终总和是正数,则顺时针方向,负方向,逆时针方向 .
这是基于this answer的算法的简单C#实现 .
假设我们有
Vector
类型X
和Y
属性double
类型 .找到y最小的顶点(如果有连接则找到最大的x) . 设顶点为
A
,列表中的上一个顶点为B
,列表中的下一个顶点为C
. 现在计算AB
和AC
的叉积的符号 .参考文献:
维基百科
为了它的 Value ,我使用这个mixin来计算Google Maps API v3应用程序的上弦顺序 .
该代码利用了多边形区域的副作用:顶点的顺时针缠绕顺序产生正区域,而相同顶点的逆时针缠绕顺序产生与负值相同的区域 . 该代码还在Google Maps几何库中使用了一种私有API . 我觉得使用它很舒服 - 使用风险自负 .
样品用法:
单元测试的完整示例@ http://jsfiddle.net/stevejansen/bq2ec/
如果您已经知道多边形内的一个点,那么计算方法更简单:
从原始多边形,点和它们的坐标中按顺序选择任何线段 .
添加已知的“内部”点,并形成三角形 .
按照建议here计算CW或CCW这三点 .