Сортировка 2D точек против часовой стрелки

Question

Сортировка 2D точек против часовой стрелки

Мой вопрос связан с этим: c ++ сортировка 2D точек по часовой стрелке, но каким-то образом это решение не работает для меня. Я пытаюсь отсортировать 4 2d точки против часовой стрелки.

Это мой код:

typedef struct p {
float x,y;
} Point;

double getClockwiseAngle(Point p) {
double angle = 0.0;

angle = atan2(p.x, -p.y);
return angle;
}

bool comparePoints(Point p1, Point p2) {
return getClockwiseAngle(p1) < getClockwiseAngle(p2);
}

int main() {
...
sort(givenPoints.begin(), givenPoints.end(), comparePoints);
...
}

Пример:
Вход (-4, 2), (1, 4), (0,1), (-1, 4)

Выход (-4, 2), (-1, 4), (1, 4), (0,1)

0

2d c++convex points sorting

Решение

Другие решения

Чтобы отсортировать точки, начиная с 12 часов, против часовой стрелки, вы должны сначала вращаться они -90 градусов (12 часов становится 3 часа):
```
x’ = y
y’ = -x
```
atan2 использует аргументы знаки для вычисления квадранта. Следующие строки не эквивалентны:
```
bool b = atan2(0.0, 1.0) < atan2(0.0, -1.0); // true
bool b = atan2(-0.0, 1.0) < atan2(-0.0, -1.0); // false
```
Поэтому вы не можете использовать atan2 сортировать точки.

Вместо atan2( -x, y) пытаться atan2( x == .0f ? .0f : -x, y ) — не испытано.

0

Источник

Accepted Answer

Я считаю, что было 2 негативных признака, которые нужно было исправить, как указано в комментарии. Это похоже на работу:

#include <iostream>
#include <vector>
#include <cmath>

typedef struct p {
float x,y;
} Point;

double getClockwiseAngle(Point p) {
double angle = 0.0;

angle = -1 * atan2(p.x, -1 * p.y);
return angle;
}

bool comparePoints(Point p1, Point p2) {
return getClockwiseAngle(p1) < getClockwiseAngle(p2);
}

int main() {
std::vector<Point> givenPoints{{-4,2}, {1,4}, {0,1}, {-1,4}};
sort(givenPoints.begin(), givenPoints.end(), comparePoints);
std::cout << "Sorted Points: ";

for(auto it = givenPoints.begin(); it != givenPoints.end(); it++) {
std::cout << "(" << it->x << ", " << it->y << ")" ;
}
std::cout << std::endl;

}

Выход:

Sorted Points: (0, 1)(1, 4)(-4, 2)(-1, 4)

Process finished with exit code 0

0