Четыре точки 2D в массиве. Мне нужно отсортировать их по часовой стрелке. Я думаю, что это можно сделать только с одной операцией свопинга, но я не смог формально ее отложить.Сортировка четырех точек по часовой стрелке
Редактировать: Четыре точки являются выпуклым многоугольником в моем случае.
Редактировать: Четыре точки - это вершины выпуклого многоугольника. Они не должны быть в порядке.
Если вы хотите принять более математическую перспективу, мы можем рассмотреть перестановками 4 пункта
в нашем случае есть 4 перестановок, которые по часовой стрелке
A B C D
B C D A
C D A B
D A B C
Все другие возможные перестановки могут быть преобразованы в одну из этих форм с 0 или 1 свопами.(Я рассматривать только перестановками, начиная с А, так как он является симметричным)
Таким образом, только один SW ap всегда необходим, но может потребоваться некоторая работа, чтобы определить, какие.
Просмотрев первые три точки и проверив знак подписанной области ABC, мы можем определить, являются ли они по часовой стрелке или нет. Если они по часовой стрелке, то мы в случае 1 2 или 5
Чтобы отличить эти случаи, мы должны проверить еще два треугольника - если ACD по часовой стрелке, мы можем сузить это до случая 1, иначе мы должны быть в случае 2 или 5.
Чтобы выбрать между вариантами 2 и 5, мы можем проверить ABD
мы можем проверить для случая ABC против часовой стрелки аналогично.
В худшем случае нам необходимо проверить 3 треугольника.
Если ваши точки не выпуклые, вы можете найти внутреннюю точку, отсортировать остальную часть и затем добавить ее в любое ребро. Заметим, что если квадрат выпуклый, то 4 точки больше не однозначно определяют квад, то есть 3 одинаково допустимых квадратика.
Я считаю, что вы правы, что один обмен может гарантировать, что многоугольник, представленный четырьмя точками на плоскости, является выпуклым. Вопросы, на которые еще нужно ответить, являются:
Последующее размышление, я думаю, что единственный ответ на второй вопрос выше - «средний два».
-1, так как ваш ответ на второй вопрос неверен, если вы не принимаете точки находятся либо по часовой стрелке, либо по часовой стрелке (см. пример, который я приводил ниже). – 2008-10-28 23:00:36
Как насчет этого?
// Take signed area of ABC.
// If negative,
// Swap B and C.
// Otherwise,
// Take signed area of ACD.
// If negative, swap C and D.
Идеи?
Проделайте его долгий путь, а затем оптимизируйте его.
Более конкретная проблема заключалась бы в сортировке координат путем уменьшения угла относительно положительной оси х. Этот угол в радианах, будет определяться этой функцией:
x>0
AND y >= 0
angle = arctan(y/x)
AND y < 0
angle = arctan(y/x) + 2*pi
x==0
AND y >= 0
angle = 0
AND y < 0
angle = 3*pi/2
x<0
angle = arctan(y/x) + pi
Тогда, конечно, это просто вопрос сортировки координат на угол. Обратите внимание, что arctan (w)> arctan (z) тогда и только тогда, когда x> z, поэтому вы можете оптимизировать функцию, которая довольно легко сравнивает углы друг с другом.
Сортировка таким образом, что угол монотонно уменьшается по окну (или такой, что он увеличивается не более одного раза) немного отличается.
Вместо обширного доказательства я упомянул, что я проверил, что одна операция свопинга будет сортировать 4 2D-точки по часовой стрелке. Разумеется, определение того, какая операция подкачки необходима, - это трюк.
Несколько мыслей стоит рассмотреть здесь;
По часовой стрелке имеет смысл только относительно происхождения. Я бы подумал о происхождении как о центре тяжести множества точек. например По часовой стрелке относительно точки в среднем положении четырех точек, а не, возможно, очень далекого начала.
Если у вас есть четыре точки, a, b, c, d, существует несколько порядков по часовой стрелке тех точек вокруг вашего происхождения. Например, если (a, b, c, d) сформировали по часовой стрелке, то были бы (b, c, d, a), (c, d, a, b) и (d, a, b, c)
У вас четыре точки уже образуют многоугольник? Если это так, это вопрос проверки и реверсирования обмотки, а не сортировки точек, например. a, b, c, d становится d, c, b, a. Если нет, я буду сортировать, основываясь на соединении между каждой точкой и источником, согласно реакции Wedges.
Edit: относительно ваших комментариев, что указывает на своп;
В случае треугольника (а, б, в), мы можем сказать, что это происходит по часовой стрелке, если третья точка с, находится на правой стороне линии аб. Я использую следующую боковую функцию для определения этого на основе координат точки;
int side(double x1,double y1,double x2,double y2,double px,double py)
{
double dx1,dx2,dy1,dy2;
double o;
dx1 = x2 - x1;
dy1 = y2 - y1;
dx2 = px - x1;
dy2 = py - y1;
o = (dx1*dy2)-(dy1*dx2);
if (o > 0.0) return(LEFT_SIDE);
if (o < 0.0) return(RIGHT_SIDE);
return(COLINEAR);
}
Если у меня есть четыре точки выпуклого многоугольника, (а, б, в, г), можно рассматривать это как два треугольника, (а, б, в) и (C, D, A). Если (a, b, c) против часовой стрелки, я изменяю обмотку (a, b, c, d) на (a, d, c, b), чтобы изменить обмотку многоугольника в целом по часовой стрелке.
Я настоятельно рекомендую нарисовать это несколькими пунктами, чтобы увидеть, о чем я говорю. Обратите внимание, что у вас есть много исключительных случаев, таких как вогнутые полигоны, коллинеарные точки, совпадающие точки и т. Д.
Ответ на клин верен.
Чтобы реализовать это легко, я думаю так же, как smacl: вам нужно найти центр границы и перевести свои точки в этот центр.
Как это:
centerPonintX = Min(x) + ( (Max(x) – Min(x))/2 )
centerPonintY = Min(y) + ( (Max(y) – Min(y))/2 )
Затем уменьшить centerPointX и centerPointY от каждого POIN для того, чтобы перевести его на происхождение границах.
Наконец, примените решение Wedge только с одним поворотом. Получите абсолютное значение arctan (x/y) для каждого экземпляра (работая для меня таким образом).
if((p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y))
swap(&p1, &p3);
«>» может быть обращено не так, но вы получаете идею.
, если мы предположим, что точка х больше, чем точка у, если угол имеет с точки (0,0) больше, то мы можем осуществить это таким образом, в C#
class Point : IComparable<Point>
{
public int X { set; get; }
public int Y { set; get; }
public double Angle
{
get
{
return Math.Atan2(X, Y);
}
}
#region IComparable<Point> Members
public int CompareTo(Point other)
{
return this.Angle.CompareTo(other.Angle);
}
#endregion
public static List<Point> Sort(List<Point> points)
{
return points.Sort();
}
}
if AB crosses CD
swap B,C
elif AD crosses BC
swap C,D
if area (ABC) > 0
swap B,D
(I mean area(ABC) > 0 when A->B->C is counter-clockwise).
Let p*x + q*y + r = 0 be the straight line that joins A and B.
Then AB crosses CD if p*Cx + q*Cy + r and p*Dx + q*Dy + r
have different sign, i.e. their product is negative.
Первый «если/Элиф» приносит четыре точки по часовой стрелке или против часовой стрелки. (Поскольку ваш многоугольник выпуклый, единственной альтернативой «пересечения» является «AC crosses BD», что означает, что четыре точки уже отсортированы.) Последняя «if» инвертирует ориентацию, когда она направлена против часовой стрелки.
Вы должны взглянуть на Сканирование Грэма. Конечно, вам нужно будет адаптировать его, поскольку он находит точки против часовой стрелки.
p.s: Это может быть избыточна для 4-х очков, но если число точек увеличить это может быть интересно
Оливер прав. Этот код (сообщество wikified) генерирует и сортирует все возможные комбинации массива из 4 пунктов.
#include <cstdio>
#include <algorithm>
struct PointF {
float x;
float y;
};
// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
return a.x * b.y - a.y * b.x;
}
// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}
void Sort4PointsClockwise(PointF points[4]){
PointF& a = points[0];
PointF& b = points[1];
PointF& c = points[2];
PointF& d = points[3];
if (Orientation(a, b, c) < 0.0) {
// Triangle abc is already clockwise. Where does d fit?
if (Orientation(a, c, d) < 0.0) {
return; // Cool!
} else if (Orientation(a, b, d) < 0.0) {
std::swap(d, c);
} else {
std::swap(a, d);
}
} else if (Orientation(a, c, d) < 0.0) {
// Triangle abc is counterclockwise, i.e. acb is clockwise.
// Also, acd is clockwise.
if (Orientation(a, b, d) < 0.0) {
std::swap(b, c);
} else {
std::swap(a, b);
}
} else {
// Triangle abc is counterclockwise, and acd is counterclockwise.
// Therefore, abcd is counterclockwise.
std::swap(a, c);
}
}
void PrintPoints(const char *caption, const PointF points[4]){
printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
points[0].x, points[0].y, points[1].x, points[1].y,
points[2].x, points[2].y, points[3].x, points[3].y);
}
int main(){
PointF points[] = {
{5.0f, 20.0f},
{5.0f, 5.0f},
{20.0f, 20.0f},
{20.0f, 5.0f}
};
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(j == i) continue;
for(int k = 0; k < 4; k++){
if(j == k || i == k) continue;
for(int l = 0; l < 4; l++){
if(j == l || i == l || k == l) continue;
PointF sample[4];
sample[0] = points[i];
sample[1] = points[j];
sample[2] = points[k];
sample[3] = points[l];
PrintPoints("input: ", sample);
Sort4PointsClockwise(sample);
PrintPoints("output: ", sample);
printf("\n");
}
}
}
}
return 0;
}
У меня есть еще одно усовершенствование, чтобы добавить к моему предыдущему ответу
запомнить - это те случаи, мы можем быть в.
Если АВС против часовой (имеет отрицательный подписанную область), то в случаях 3, 4, 6. Если в этом случае мы заменим B & C, то мы останемся с Возможности мычание:
Далее мы можем проверить ABD и замены B & D, если она против часовой стрелки (случаи 5, 6)
Наконец, мы должны проверить ДСА и замены C & D, если ACD является против часовой стрелки. Теперь мы знаем, что все наши пункты в порядке.
Этот метод не так эффективен, как мой предыдущий метод - это требует 3 проверки каждый раз и более одного свопа; но код будет намного проще.
Если кому-то интересно, вот мое быстрое и грязное решение аналогичной проблемы.
Моя проблема в том, чтобы иметь мои прямоугольные углы заказана в следующем порядке:
верхний левый> правый верхний> нижний правый> нижний левый
В основном это происходит по часовой стрелке заказ начиная с верхнего левого угла.
Идея алгоритма:
Заказать углы по строкам, а затем заказать угловые пары на перевалы.
// top-left = 0; top-right = 1;
// right-bottom = 2; left-bottom = 3;
List<Point> orderRectCorners(List<Point> corners) {
if(corners.size() == 4) {
ordCorners = orderPointsByRows(corners);
if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points
Point tmp = ordCorners.get(0);
ordCorners.set(0, ordCorners.get(1));
ordCorners.set(1, tmp);
}
if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points
Point tmp = ordCorners.get(2);
ordCorners.set(2, ordCorners.get(3));
ordCorners.set(3, tmp);
}
return ordCorners;
}
return empty list or something;
}
List<Point> orderPointsByRows(List<Point> points) {
Collections.sort(points, new Comparator<Point>() {
public int compare(Point p1, Point p2) {
if (p1.y < p2.y) return -1;
if (p1.y > p2.y) return 1;
return 0;
}
});
return points;
}
var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}];
var reference = {x:2,y:2};
arr.sort(function(a,b) {
var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x));
var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x));
if (aTanA < aTanB) return -1;
else if (aTanB < aTanA) return 1;
return 0;
});
console.log(arr);
Где опорная точка лежит внутри многоугольника.
Более подробная информация по этим site
Вычислить площадь от координат с формулой (devoided шнурков абсолютного значения таким образом, что область может быть положительной или отрицательным) для каждых точки перестановок. Максимальные значения площади, кажется, соответствуют прямым простые четырехугольники: Simple direct quadrilaterals found with the shoelace formula
если вам просто нужно иметь дело с 4 очками, то есть самый простой способ сделать это
рода по значению y
верхний ряд - первые две точки, нижний ряд - остальные 2 балла
для верхней и нижней строке, сортировать их по значению х
.
corners.sort(key=lambda ii: ii[1], reverse=True)
topRow = corners[0:2]
bottomRow = corners[2:]
topRow.sort(key=lambda ii: ii[0])
bottomRow.sort(key=lambda ii: ii[0])
# clockwise
return [topRow[0], topRow[1], bottomRow[1], bottomRow[0]]
Вы имеете в виду по часовой стрелке вокруг начала координат? – 2008-10-28 06:41:14
Не обязательно. – 2008-10-28 06:49:06
Или он может быть по часовой стрелке вокруг бондарного центра. – vmarquez 2008-10-28 07:47:38