Сортировка по полярному углу - PullRequest
Новая
       74

Сортировка по полярному углу

0 голосов
/ 13 января 2019

Я пытаюсь реализовать алгоритм сканирования Грэма для выпуклой оболочки в Java, и у меня возникают проблемы с сортировкой точек по полярному углу относительно точки с наименьшим значением y.

Я нашел этот ответ и понимаю, как рассчитать полярный угол, а не как сортировать точки.

Я видел реализации, где Collections.sort() используется, но ни одна из них, похоже, не работает с классом Point2D, который я хочу использовать, потому что я хочу иметь возможность иметь двойные координаты.

По сути, я хочу иметь возможность отсортировать ArrayList<Point2D> по их полярному углу до точки с наименьшим значением y в том же ArrayList.

Может кто-нибудь помочь мне с этим? Благодарю.

Ответы [ 2 ]

0 голосов
/ 14 января 2019

Я изменил последний ответ на этот вопрос.

Определите новый класс для Point: 

class Point {
    private long x, y;
    Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
    Point() {
        x = 0;
        y = 0;
    }
    public long getX() {
        return x;
    }
    public long getY() {
        return y;
    }
}

Определить новую функцию для вычисления перекрестного произведения двух векторов: 

public long cross(long x1, long y1, long x2, long y2) {
    return x1 * y2 - x2 * y1;
}

Предположим, что initial - это Point с самой низкой координатой Y. Также предположим, что List<Point> points - это список со всеми остальными доступными точками, но он НЕ содержит точку initial.

Для сортировки списка мы можем использовать Collections.sort с компаратором: 

Collections.sort(points, (a, b) -> {
    long cr = cross(a.getX() - initial.getX(), a.getY() - initial.getY(), b.getX() - initial.getX(), b.getY() - initial.getY());
    if (cr > 0)
        return 1;
    else
        return -1;
});

В этом решении мы использовали перекрестное произведение, чтобы проверить, расположены ли два вектора по часовой или против часовой стрелки. Это решение имеет два преимущества:

  1. Более ценно, когда наши координаты являются целыми числами. Когда мы вычисляем углы в других решениях, мы можем иметь некоторые ошибки в вычислениях с плавающей запятой.
  2. В других решениях мы можем иметь «деление на ноль», но у нас нет этой проблемы здесь.
0 голосов
/ 13 января 2019

Предположим, что initial - это Point2D с самой низкой координатой Y. Также предположим, что List<Point2D> points - это список со всеми остальными доступными точками, но он НЕ содержит точку initial.

Для сортировки списка мы можем использовать Collections.sort с компаратором: 

Collections.sort(points, (a, b) -> {
    double cotanA = -(a.getX() - initial.getX()) / (a.getY() - initial.getY());
    double cotanB = -(b.getX() - initial.getX()) / (b.getY() - initial.getY());
    if (cotanA - cotanB < 0) {
        return 1;
    }
    return -1;
});
...