Sortowanie współrzędnych

0

Witam
Mam taki problem! Pisze aplikację która na wejściu otrzymuje współrzędne narożników budynku. Na podstawie tych danych mam na wyjściu otrzymać kierunki jego ścian jako duże litery N - północ, S, E, W . Pierwsza współrzędna na wejściu jest współrzędną startu. Obchodzenie budynku odbywa się w kierunku zegara! I moje pytanie jak najlepiej rozwiązać ten problem? Zastanawiam się jak posortować współrzędne? Czy może jest to dobry pomysł?
Przykład dla takiego budynku:
dane wejściowe:
1 1
2 2
0 1
1 0
0 2
2 0
Wynik:
WNESWN
Na rysunku wygląda to tak!
user image

0

Jeśli dobrze rozumiem, to współrzędne narożników są podane w przypadkowej kolejności, a ty chcesz je tak poprzestawiać, aby były podane kolejności zgodnej z ruchem wskazówek zegara.
Brakuje mi informacji jak ma być ustalany pierwszy narożnik (pierwsza ściana)?

Coś nie tak jest z wynikiem bo ja widzę 1 ścianę N, 2 ściny S, 2 ściny W i jedną ścianę E, a w twoim wyniku jest inaczej ściana N zamiast S.

// uzupełnienie:
a algorytm wygląda tak:
punkt opisujesz strukturą/klasą:

struct Corner{
     int x,y;
     Corner* cornerNS; // następny narożnik ściana łącząca północ-południe
     Corner* cornerWE; // następny narożnik ściana łącząca wschód-zachód.
};

Następnie szorujesz punkty najpierw ze względu na y i jeśli y są takie same to ze względu na x.
Następnie łączysz kolejne pary punktów ustawiając im cornerWE tak by wskazywały na siebie na wzajem.

Znowu szorujesz punkty najpierw ale tym razem najpierw ze względu na x i jeśli x są takie same to ze względu na y.
Następnie łączysz kolejne pary punktów ustawiając im cornerNS tak by wskazywały na siebie na wzajem.

Teraz korzystając z cornerNS i cornerWE dokładnie wiesz jak wyglądają ściny i jaka jest ich kolejność. Dla kolejnych rogów bierzesz na przemian cornerNS i cornerWE.

0

Trochę chyba źle zrozumiałeś :) Obchodzimy budynek w kierunku wskazówek zegara zaczynając od punktu startowego, który w danych wejściowych jest podany jako pierwszy. I teraz jeśli od punkty startowego idziemy w lewo to wpisujemy literę W, następnie od tego punku musimy iść w górę więc wpisujemy N, itd.

0

No właśnie. Ja ci opisałem to co najtrudniejsze, czyli jak ze sobą skojarzyć rogi między sobą (układ ścian). Na podstawie tego możesz już bez problemu "obejść budynek" i ustalić, w którym kierunku jest prawo (zwykły rachunek wektorowy). Opisałeś, że masz problem z posortowaniem punktów i właśnie to ci opisałem. Reszta jest prosta i powinieneś zrobić to sam.

0

Kurcze teraz dopiero załapałem i muszę przyznać, że pomysł wręcz fantastyczny. Mam jeszcze jednak kilka kwestii.

  1. Każdy punkt ma być osobną strukturą ?
  2. Jeśli tak to właśnie z tym mam kolejny problem, a dokładnie jak te wszystkie punkty powklejać każdy do osobnej struktury?
0

Może sformułuj dokładniej z czym masz problem bo "jak te wszystkie punkty powklejać każdy do osobnej struktury" wygląda mi na głupie lub nieprecyzyjne pytanie.

0

Chyba mu chodzi o to, że chce zrobić po 1 strukturze [obiekcie - przyp. tłum.] dla każdego punktu, czyli w tym przypadku 6 struktur [obiektów - przyp. tłum.].

0

Struktura może być taka

struct Punkt
{
   int x;
   int y;
   char kierunek;
   Punkt *nastepny;
};

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.