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

EDIT: я обновил program с ответом, и он отлично работает!

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

Вот как определяются точки:

function Point(x, y) {
    this.x = x;
    this.y = y;
}

var vertices = [];

// Called on click
function addPoint(mouseX, mouseY) {
    vertices.push(new Point(mouseX, mouseY));
}

Вот изображение многоугольника по часовой стрелке:

Вот изображение полигона против часовой стрелки:

Если бы вы могли помочь мне выяснить, как определить "по часовой стрелке" точек, я был бы очень благодарен!

Ответ 1

Вычислите область многоугольника, используя формулу shoelace, но без знака абсолютного значения. Если результат положительный, точки упорядочены против часовой стрелки, а если отрицательный - по часовой стрелке.

function polygonArea() { 
    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;
    }
    return area / 2;
}
var clockwise = polygonArea() > 0;

Ответ 2

Общая идея состояла бы в том, чтобы взглянуть на выпуклую оболочку вашего полигона и угадать ориентацию оттуда. Тем не менее, я думаю, что вам не нужно строить весь корпус, чтобы найти ориентацию, но только один сегмент, принадлежащий ему.

Итак:

Найдите две точки ваших полигонов, чтобы все остальные точки были на одной стороне этой линии.
Если все точки находятся слева (просто проверьте одну из точек), то против часовой стрелки. Если они справа, то по часовой стрелке.

Пример:

На верхней фигуре: 4-5 пусть фигура справа, 5-11 пусть фигура справа,... На нижней фигуре: 6-7 пусть фигура слева, 7-14 пусть фигура слева,...

Предупреждение. Во время "ходьбы" на вашем полигоне не перезапускайте нумерацию, иначе это будет неправильно. На верхней фигуре 4- (n-1) пусть фигура слева!

Ответ 3

Ваше интуитивное определение часового механизма не определено. Например, если я рисую подкову:

   /---a-b--\
  /   _d_c_  \
 /  /       \ \
 | |        | |
 | |        | |
  \ \       / /
   \ \     / /
    --     --

Если 0 = a < b < b < d и я смотрю на a и b, я бы сделал из вашего описания, что форма была нарисована по часовой стрелке, но если 0 = c < d < a < b, я бы сделал вывод, что форма была нарисована против часовой стрелки. Поскольку оба этих сценария связаны с тем же направлением, в котором были нарисованы точки, только из разных исходных точек, я могу только заключить, что ваше определение отсутствует.

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

Если вы заинтересованы в более строгом определении вещей, я предлагаю что-то в следующих строках:

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

Как только у вас будет такое более четкое определение, реализация может быть такой же простой, как подсчет числа обмотки. Возьмите середину любой упорядоченной пары, скажем 0 и 1, возьмите отрезок прямой справа от упорядоченной пары (под любым углом, скажем, перпендикулярно), и подсчитайте, сколько пересечений оно имеет с другими отрезками линии: кривая по часовой стрелке, если число нечетное.

Это просто реализовать, линейное по времени O(n) и добавляет постоянное пространство O(1).

Ответ 4

Если кто-то использует three.js, ShapeUtils имеет встроенный метод isClockWise, который внутренне использует метод area для определения знака вычисленной области.

isClockWise: function ( pts ) {

    return ShapeUtils.area( pts ) < 0;

}

Метод ShapeUtils.isClockWise можно найти здесь.

area: function ( contour ) {

    var n = contour.length;
    var a = 0.0;

    for ( var p = n - 1, q = 0; q < n; p = q ++ ) {

        a += contour[ p ].x * contour[ q ].y - contour[ q ].x * contour[ p ].y;

    }

    return a * 0.5;

},

Метод ShapeUtils.area можно найти здесь.

Ответ 5

Это функция, которая специализируется на OpenLayers. Как вы можете видеть состояние по часовой стрелке. Область < 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);
}