Używam .NET 2.0, więc nie mam dostępu do ładnego Linq; jednak opracowałem kod, który sortuje listę punktów zgodnie z ruchem wskazówek zegara / przeciwnie do ruchu wskazówek zegara.

Mój problem polega na tym, że sortowanie działa doskonale, jeśli lista nie jest już posortowana, ale jeśli z jakiegoś powodu lista jest już posortowana, funkcja sortowania kończy się niepowodzeniem.

Zastanawiałem się, czy ktoś mógłby mi pomóc wskazać właściwy kierunek, dlaczego to może być przyczyną.

Oto moje wezwanie do tego rodzaju:

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

A oto funkcja 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;
    }

Gdzie moim odniesieniem jest punkt, od którego określam odpowiedni kąt do każdego punktu na mojej liście punktów.

Teraz powiedz, że mam listę punktów:

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

Są one już posortowane we właściwej kolejności, ale wywołanie funkcji sort daje:

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

Teraz weź kolejny zestaw punktów próbkowania:

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

Ta lista nie jest już we właściwej kolejności, a wywołanie funkcji sortowania daje:

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

Który jest prawidłowo posortowany. Ten wzorzec powtarza się dla każdego zestawu współrzędnych, które są już posortowane i dla tych, które nie są. Jakieś pomysły?

2
Nathan Raley 9 sierpień 2011, 17:31
3
Naprawdę powinieneś przekazać swój punkt odniesienia do metody, zamiast odwoływać się (nie jest to zamierzone) do zmiennej „globalnej”.
 – 
John Kraft
9 sierpień 2011, 17:36

3 odpowiedzi

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

Te dwa warunki są takie same! Albo zamień zmienne albo obróć znak nierówności, ale nie jedno i drugie.

8
hmakholm left over Monica 9 sierpień 2011, 17:40
Teraz czuję się głupio, bawiłem się tą funkcją i źle napisałem tę linię. Dziękuję.
 – 
Nathan Raley
9 sierpień 2011, 17:51

Oprócz doskonałej obserwacji, którą poczynił Henning, możesz być również zaskoczony wynikami, gdy naprawisz ten problem.

Symetria kołowa sprawia, że ​​jest to nieco nietypowy algorytm sortowania w porównaniu z normalnymi sortowaniami w całkowicie uporządkowanych domenach. Ponieważ istnieje symetria kołowa, istnieje n prawidłowych porządków zgodnych z ruchem wskazówek zegara, biorąc pod uwagę n punktów i może mieć dla ciebie znaczenie, który z tych porządków wolisz.

W obecnej postaci użycie niezmodyfikowanego atan2 spowoduje powstanie linii cięcia o współrzędnych (x,0), gdzie x<0.

Rozważ współrzędne A = (-10, 1) i B = (-10, -1), mierzone względem odniesienia. Prawdopodobnie wyobrażasz sobie, że w wyniku A powinno pojawić się przed B, ale w rzeczywistości będzie odwrotnie, ponieważ atan2 zwraca tylko mniej niż π dla A, ale tylko więcej niż -π dla B.

Jeśli chcesz uzyskać linię cięcia ze współrzędnymi (x,0), gdzie x>0, po prostu dodaj 2π do wszelkich ujemnych wartości zwracanych z atan2.

3
David Heffernan 9 sierpień 2011, 17:49
Doskonała obserwacja. Zauważyłem to samo zdarzenie, gdy 2 (lub więcej) punkty znajdowały się na płaszczyźnie -X. Świetna wskazówka co do rozwiązania... Miałem zamiar zająć się czymś znacznie trudniejszym jeśli (X == ref.X).
 – 
IAbstract
21 marzec 2016, 16:39

Nie powinno być:

else if(aTanA > aTanB) return 1;

Nie jestem pewien, czy spowodowałoby to Twój problem.

1
JaCraig 9 sierpień 2011, 17:40