Сортировка 2D точек против часовой стрелки - PullRequest
Новая
       61

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

0 голосов
/ 31 октября 2018

Мой вопрос связан с этим: 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)

Ответы [ 2 ]

0 голосов
/ 31 октября 2018

  • Чтобы отсортировать точки, начиная с 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 голосов
/ 31 октября 2018

Я считаю, что было 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
...