Autor Wątek: Łączenie punktów.  (Przeczytany 3829 razy)

Offline lukaszw

  • Użytkownik

# Styczeń 11, 2012, 19:33:45
Posortowanie punktów kątowo względem jednego z nich nie będzie najprostszym rozwiązaniem?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kelesh

  • Użytkownik

# Styczeń 12, 2012, 13:25:36
Posortowanie punktów kątowo względem jednego z nich nie będzie najprostszym rozwiązaniem?

Nie jeśli trafią się dwa punkty o tym samym kącie względem rozpatrywanego punktu. Ale wtedy wystarcza dla tych samych kątków posortować jeszcze po odległości. Pisałem o tym rozwiązaniu wcześniej.

Offline owyn

  • Użytkownik

# Styczeń 12, 2012, 14:12:58
Kiedyś robiłem coś podobnego, dość prosty algorytm (zakładam że oś y jest skierowana w górę):
1. Bierzemy dwa punkty:
x1 - położony najbardziej na lewo (najmniejsza współrzędna x)
x2 - położony najbardziej na prawo (największa współrzędna x)
2. Dzielimy zbiór pozostałych punktów na dwa zbiory:
s1 - punkty leżące ponad lub na prostej wyznaczonej przez x1 i x2
s2 - punkty leżące poniżej tej prostej
3. Sortujemy s1 według współrzędnej x rosnąco (jeśli dwa punkty mają taką samą współrzędną - to po y rosnąco), s2 sortujemy odwrotnie (po x malejąco, jeśli taka sama - po y malejąco).
4. Wynikowy wielokąt jest utworzony przez kolejne punkty: x1 - s1 - x2 - s2.
« Ostatnia zmiana: Styczeń 12, 2012, 14:16:50 wysłana przez owyn »

Offline lukaszw

  • Użytkownik

# Styczeń 14, 2012, 02:37:52
Nie jeśli trafią się dwa punkty o tym samym kącie względem rozpatrywanego punktu. Ale wtedy wystarcza dla tych samych kątków posortować jeszcze po odległości. Pisałem o tym rozwiązaniu wcześniej.
Dokładnie. O to właśnie mi chodziło - nie przypominam sobie, abym musiał kiedyś kodzić drugorzędne kryterium w sortowaniu kątowym inne niż odległość [bo to rozróżnia punkty jednoznacznie], więc pominąłem to w swojej wypowiedzi.

owyn: imho wprost genialne w swojej prostocie! Osobiście nie widzę kontrprzykładu. Wydaje się działać. Od siebie dodam, że sprawdzenie po której stronie prostej leży punkt najłatwiej wykonać licząc wyznacznik.
Pozdrawiam.
« Ostatnia zmiana: Styczeń 14, 2012, 02:39:28 wysłana przez lukaszw »

Offline japko

  • Użytkownik

# Styczeń 26, 2012, 12:02:14
do zamknięcia;)

// tutaj nie zamykamy tematów - a nuż ktoś wynajdzie jakiś lepszy sposób ;) -Xirdus
« Ostatnia zmiana: Styczeń 26, 2012, 15:19:35 wysłana przez Xirdus »