Определить, был ли задан набор точек в массиве, которые являются вершинами сложного многоугольника, по часовой стрелке или против часовой стрелки?
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));
}
Вот изображение многоугольника по часовой стрелке:
![Clockwise Polygon]()
Вот изображение полигона против часовой стрелки:
![Counterclockwise Polygon]()
Если бы вы могли помочь мне выяснить, как определить "по часовой стрелке" точек, я был бы очень благодарен!
Ответы
Ответ 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);
}