C # Сортировка списка координат X, Y по часовой стрелке

Question

Я использую .NET 2.0, поэтому у меня нет доступа к изящному Linq;Тем не менее, я разработал некоторый код, который сортирует список точек по часовой стрелке / против часовой стрелки.

Моя проблема в том, что сортировка работает отлично, если список еще не отсортирован, но если по какой-то причине список ужесортировать функцию сортировки с треском проваливается.

Я бродил, если кто-то может помочь мне указать правильное направление, почему это может быть причиной.

Вот мой вызов сортировке:

positions.Sort(new Comparison<Position>(MapUtils.SortCornersClockwise));

А вот функция SortCornersClockwise:

public static int SortCornersClockwise( Position A, Position B)
    {
        //  Variables to Store the atans
        double aTanA, aTanB;

        //  Reference Point
        Pixels reference = Program.main.reference;

        //  Fetch the atans
        aTanA = Math.Atan2(A.Pixel.Y - reference.Y, A.Pixel.X - reference.X);
        aTanB = Math.Atan2(B.Pixel.Y - reference.Y, B.Pixel.X - reference.X);

        //  Determine next point in Clockwise rotation
        if (aTanA < aTanB) return -1;
        else if (aTanB > aTanA) return 1;
        return 0;
    }

Где моя ссылка - это точка, из которой я определяю соответствующий угол каждой точке в моем списке точек.

Теперь скажите, что у меня есть список точек:

15778066, 27738237
15778169, 27738296
15778185, 27738269
15778082, 27738210 

Они уже отсортированы в правильном порядке, но вызов функции сортировки дает:

15778082, 27738210
15778066, 27738237
15778185, 27738269
15778169, 27738296

Теперь возьмем другой набор выборокpoints:

15778180, 27738255
15778081, 27738192
15778064, 27738219
15778163, 27738282 

Этот список уже не в правильном порядке, и вызов функции сортировки дает:

15778064, 27738219
15778081, 27738192
15778180, 27738255
15778163, 27738282

, который отсортирован правильно.Этот шаблон повторяется самостоятельно для каждого набора координат, которые уже отсортированы, и для тех, которые не отсортированы.Есть идеи?

Answer 1

if (aTanA < aTanB) return -1;
else if (aTanB > aTanA) return 1;

Эти два условия одинаковы! Либо поменяйте местами переменные , либо , поверните знак неравенства, но не оба.

Answer 2

В дополнение к превосходному наблюдению, сделанному Хеннингом, вы также можете быть удивлены выходом, как только исправите эту проблему.

Круговая симметрия делает этот алгоритм сортировки несколько необычным по сравнению с обычными сортировками в полностью упорядоченных областях. Поскольку существует круговая симметрия, существует n действительных порядков по часовой стрелке с учетом n точек, и вам может иметь значение, какой из этих порядков вы предпочитаете.

В нынешнем виде использование неизмененного atan2 приведет к линии среза с координатами (x, 0), где x <0. </p>

Рассмотрим координаты A = (-10, 1) и B = (-10, -1), измеренные относительно эталона. Вы, вероятно, думаете, что A должен появиться перед B в результате, но на самом деле все будет наоборот, поскольку atan2 возвращает чуть меньше π для A, но чуть больше -π для B.

Если вам нужна линия среза с координатами (x, 0), где x> 0, просто добавьте 2π к любым отрицательным значениям, возвращаемым из atan2.

Answer 3

Не должно ли это быть:

else if(aTanA > aTanB) return 1;

Не уверен, что это вызовет вашу проблему.