有了一个点列表，我如何确定它们是否是顺时针顺序的?
例如:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
会说它是逆时针的(对某些人来说是逆时针的)
当前回答
为了它的价值，我使用这个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;
}
})();
其他回答
Javascript实现的lhf的答案 (再次强调，这只适用于简单的多边形，即不适用于图8)
let polygon = [ {x:5,y:0}, {x:6,y:4}, {x:4,y:5}, {x:1,y:5}, {x:1,y:0} ] document.body.innerHTML += `Polygon ${polygon.map(p=>`(${p.x}, ${p.y})`).join(", ")} is clockwise? ${isPolygonClockwise(polygon)}` let reversePolygon = [] polygon.forEach(point=>reversePolygon.unshift(point)) document.body.innerHTML += `<br/>Polygon ${reversePolygon.map(p=>`(${p.x}, ${p.y})`).join(", ")} is clockwise? ${isPolygonClockwise(reversePolygon)}` function isPolygonClockwise (polygon) { // From http://www.faqs.org/faqs/graphics/algorithms-faq/ "How do I find the orientation of a simple polygon?" // THIS SOMETIMES FAILS if the polygon is a figure 8, or similar shape where it crosses over itself // Take the lowest point (break ties with the right-most). if (polygon.length < 3) { return true // A single point or two points can't be clockwise/counterclockwise } let previousPoint = polygon[0] let lowestPoint = polygon[1] let nextPoint = polygon[2] polygon.forEach((point, index)=>{ if (point.y > lowestPoint.y || (point.y === lowestPoint.y && point.x > lowestPoint.x)) { // larger y values are lower, in svgs // Break ties with furthest right previousPoint = polygon[(index-1) >= (0) ? (index-1) : (polygon.length-1)] lowestPoint = polygon[index] nextPoint = polygon[(index+1) <= (polygon.length-1) ? (index+1) : (0)] } }) // Check the angle between the previous point, that point, and the next point. // If the angle is less than PI radians, the polygon is clockwise let angle = findAngle(previousPoint, lowestPoint, nextPoint) return angle < Math.PI } function findAngle(A,B,C) { var AB = Math.atan2(B.y-A.y, B.x-A.x); var BC = Math.atan2(C.y-B.y, C.x-B.x); if (AB < 0) AB += Math.PI*2 if (BC < 0) BC += Math.PI*2 return BC-AB; }
为了它的价值，我使用这个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;
}
})();
找出y最小的顶点(如果有平手，则x最大)。假设顶点是A，列表中的前一个顶点是B，列表中的下一个顶点是c。现在计算AB和AC的叉乘的符号。
引用:
如何确定一个简单多边形的方向?在 常见问题:计算机。图形。算法。 维基百科的曲线定位。
The cross product measures the degree of perpendicular-ness of two vectors. Imagine that each edge of your polygon is a vector in the x-y plane of a three-dimensional (3-D) xyz space. Then the cross product of two successive edges is a vector in the z-direction, (positive z-direction if the second segment is clockwise, minus z-direction if it's counter-clockwise). The magnitude of this vector is proportional to the sine of the angle between the two original edges, so it reaches a maximum when they are perpendicular, and tapers off to disappear when the edges are collinear (parallel).
因此，对于多边形的每个顶点(点)，计算两条相邻边的叉乘大小:
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的段 点1到点2之间的edgeB .．. edgeE在point4和point0之间。
那么顶点A (point0)在两者之间 edgeE[从点4到点0] 从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)下面来构造的。第三个(零)值坐标在那里，因为外积概念是一个三维结构，所以我们将这些2-D向量扩展到3-D，以便应用外积:
i j k
-4 0 0
1 4 0
假设所有的叉乘都产生一个垂直于两个向量相乘平面的向量，上面矩阵的行列式只有一个k(或z轴)分量。 计算k轴或z轴分量大小的公式为 A1 *b2 - a2*b1 = -4* 4 - 0* 1 = -16
这个值的大小(-16)是两个原始向量夹角的正弦值，乘以两个向量大小的乘积。 实际上，它值的另一个公式是 A X B(叉乘)= |A| * |B| * sin(AB)。
为了得到角度的大小你需要用这个值(-16)除以两个向量大小的乘积。
|A| * |B| = 4 *根号(17)= 16.4924…
所以sin(AB) = -16 / 16.4924 = -.97014…
这是一个度量顶点后的下一段是否向左或向右弯曲，以及弯曲的程度。不需要取arcsin函数。我们只关心它的大小，当然还有它的符号(正的还是负的)!
对闭合路径周围的其他4个点都这样做，并将每个顶点的计算值相加。
如果最终的和是正的，就顺时针，负的，逆时针。
我的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();
}
}
}
