Как определить, если список точек полигона находятся в порядке по часовой стрелке?

The произведение измеряет степень перпендикулярности двух векторов. Представьте, что каждый край вашего многоугольника является вектором в плоскости x-y трехмерного (3-D) пространства xyz. Тогда поперечное произведение двух последовательных ребер является вектором в 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.

Тогда Вершина A (point0) между
edgeE [из point4 до point0]
edgeA [из point0 to 'point1'

эти два ребра сами являются векторами, координаты x и y которых можно определить путем вычитания координат их начальной и конечной точек:

edgeE = point0 -point4 = (1, 0) - (5, 0) = (-4, 0) и
edgeA = point1 -point0= (6, 4) - (1, 0)= (5, 4) и

и крест произведение этих двух соседних ребер вычисляется с использованием определителя следующей матрицы, которая строится путем помещения координат двух векторов ниже символов, представляющих три координатные оси (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), является мерой синуса угла между 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 точек вокруг замкнутого пути и сложите значения из этого расчета в каждой вершине..

если конечная сумма положительна, вы пошли по часовой стрелке, отрицательно, против часовой стрелки.

Я думаю, что это довольно старый вопрос, но я все равно собираюсь выбросить другое решение, потому что оно простое и не математически интенсивное - оно просто использует базовую алгебру. Вычислить площадь многоугольника. Если он отрицательный, точки расположены по часовой стрелке, если положительный-против часовой стрелки. (Это очень похоже на решение бета-версии.)

вычислить площадь: A = 1/2 * (x₁ * y₂ - x₂ * y₁ + x₂ * y₃ - x₃ * y₂ + ... + x_n * y₁ - x₁ * y_n)

или в псевдо-код:

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

вот простая реализация алгоритма 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]; // % is the modulo operator
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

найти вершину с наименьшим y (и наибольшим x, если есть связи). Пусть вершина будет A и следующие вершины в списке будут B и C. Теперь вычислите знак перекрестного произведения AB и AC.

---

ссылки:

• как найти ориентацию простого многоугольника? in Часто Задаваемые Вопросы: компания.графика.алгоритмы.

• ориентация Кривой в Википедии.

начните с одной из вершин и вычислите угол, под которым находится каждая сторона.

первый и последний будут равны нулю (так что пропустите их); для остальных синус угла будет задан поперечным произведением нормировок на единицу длины (точка[n]-точка[0]) и (точка[n-1]-точка[0]).

Если сумма значений положительна,то ваш полигон рисуется против часовой стрелки.

для чего это стоит, я использовал этот mixin для расчета порядка намотки для приложений Google Maps API v3.

код использует побочный эффект полигональных областей: порядок намотки по часовой стрелке вершин дает положительную область, в то время как порядок намотки против часовой стрелки тех же вершин дает ту же область, что и отрицательное значение. Код также использует своего рода частный API в библиотеке геометрии Google Maps. Я чувствовал себя комфортно, используя его-использовать по своему усмотрению риск.

пример использования:

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:

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, если вершины многоугольника в порядке обхода по часовой стрелке.

Как также объясняется в этой статье Википедии ориентация Кривой, учитывая 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 are коллинеарны.

в приведенной выше формуле мы добавляем те, которые находятся перед координатами p,q и r потому что мы используем однородных координат.

это реализованная функция для OpenLayers 2. Условием наличия многоугольника по часовой стрелке является area < 0, это подтверждается этой ссылке.

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);
}

Я думаю, что для того, чтобы некоторые точки были даны по часовой стрелке, все ребра должны быть положительными не только сумма ребер. Если один край отрицательный, то хотя бы 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

гораздо более простой в вычислительном отношении метод,Если вы уже знаете точку внутри полигона:

1. выберите любой сегмент линии из исходного полигона, точки и их координаты в этом порядке.

2. добавьте известную точку "внутри" и сформируйте треугольник.

3. вычислить часовой или против часовой стрелки как предложили здесь С этими тремя точками.

после тестирования нескольких ненадежных реализаций алгоритм, который обеспечил удовлетворительные результаты в отношении ориентации CW / CCW из коробки, был одним, опубликованным OP в этой thread (shoelace_formula_3).

как всегда, положительное число представляет собой ориентацию CW, тогда как отрицательное число CCW.

вот решение swift 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

найти центр масс этих точек.

предположим, что есть линии от этой точки до ваших точек.

найти угол между двумя линиями для line0 line1

чем сделать это для line1 и line2

...

...

Если этот угол монотонно увеличивается, чем против часовой стрелки,

иначе, если монотонно уменьшается по часовой стрелке

else (это не так монотонно)

вы не можете решить, так что не мудрите