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?
3 odpowiedzi
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.
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.
Nie powinno być:
else if(aTanA > aTanB) return 1;
Nie jestem pewien, czy spowodowałoby to Twój problem.
Podobne pytania
Nowe pytania
c#
C # (wymawiane „patrz ostro”) jest językiem programowania wysokiego poziomu, statycznie typowanym, wieloparadygmatowym opracowanym przez firmę Microsoft. Kod C # zwykle jest przeznaczony dla rodziny narzędzi Microsoft .NET i czasów wykonywania, do których należą między innymi .NET Framework, .NET Core i Xamarin. Użyj tego tagu w przypadku pytań dotyczących kodu napisanego w C # lub C # formalnej specyfikacji.