有了一个点列表,我如何确定它们是否是顺时针顺序的?
例如:
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)
会说它是逆时针的(对某些人来说是逆时针的)
当前回答
正如这篇维基百科文章中所解释的曲线方向,给定平面上的3个点p, q和r(即x和y坐标),您可以计算以下行列式的符号
如果行列式为负(即定向(p, q, r) < 0),则多边形是顺时针方向(CW)。如果行列式为正(即定向(p, q, r) > 0),则多边形是逆时针方向(CCW)。如果点p, q和r共线,行列式为零(即定向(p, q, r) == 0)。
在上面的公式中,由于我们使用的是齐次坐标,我们将1放在p, q和r的坐标前面。
其他回答
求出这些点的质心。
假设有直线从这个点到你们的点。
求line0 line1的两条直线夹角
而不是直线1和直线2
...
...
如果这个角是单调递增的,而不是逆时针递增的,
如果是单调递减,则是顺时针递减
Else(它不是单调的)
你不能决定,所以这是不明智的
一个计算上更简单的方法,如果你已经知道多边形内的一个点:
从原始多边形中选择任意线段,按此顺序选择点及其坐标。 加上一个已知的“内部”点,形成一个三角形。 根据以上三点计算CW或CCW。
在测试了几个不可靠的实现之后,在CW/CCW方向方面提供令人满意结果的算法是由OP在这个线程(shoelace_formula_3)中发布的算法。
与往常一样,正数表示CW方向,而负数表示CCW方向。
我将提出另一个解决方案,因为它很简单,不需要大量的数学运算,它只是使用了基本的代数。计算多边形的带符号面积。如果是负的,点是顺时针的,如果是正的,点是逆时针的。(这与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。
来源:http://mathworld.wolfram.com/PolygonArea.html
为了它的价值,我使用这个mixin来计算谷歌Maps API v3应用程序的缠绕顺序。
该代码利用了多边形区域的副作用:顺时针旋转顺序的顶点产生一个正的区域,而逆时针旋转顺序的相同顶点产生一个负的区域。该代码还使用了谷歌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 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;
}
})();