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

Offline japko

  • Użytkownik

# Styczeń 10, 2012, 19:06:33
Witam,

Na pierwszy rzut oka mam banalny program na zaliczenie. Mamy n punktów. Z tych punktów muszę wykreślić wielokąt (linie nie mogą się przecinać, wystarczy jedna taka figura). Problem w tym, że nie mam kompletnie pomysłu jak to zrobić;/ Język, w którym mam to napisać to Pascal. Pomożecie?

Offline Mr. Spam

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

Offline czoper

  • Użytkownik
    • czoper.devlog

# Styczeń 10, 2012, 19:13:18
Pierwsze, najbardziej banalne rozwiązanie, które przyszło mi do głowy to:
1) robisz otoczkę wypukłą używając danych punktów
2) jeżeli użyte zostały wszystkie punkty to cool
3) w przeciwnym przypadku dla każdego nieprzypisanego punktu znajdujesz dwa sąsiadujące ze sobą punkty które już należą do figury i wstawiasz między nie rozpatrywany punkt

niesprawdzane, więc mogą się znaleźć kontrprzykłady ;)

Offline Kelesh

  • Użytkownik

# Styczeń 10, 2012, 19:36:14
Policz średnią x i y tych punktów. Niech to będzie środek nowej figury. Policz kąt między każdym z punktów, a prostą y=x średnia (pozioma kreska przechodząca przez środek). Posortuj punkty względem kątów. Jeśli dwa punkty mają identyczny kąt, to posortuj je względem odległości od środka. Kolejne punkty na liście stanowią kolejne wierzchołki wielokąta. Gotowe.

Offline japko

  • Użytkownik

# Styczeń 10, 2012, 20:00:27
Typ prowadzący coś wspominał o algorytmie z powtórzeniami. Jaki sposób będzie najłatwiejszy do napisania?

Offline Kelesh

  • Użytkownik

# Styczeń 10, 2012, 21:20:18
Wydaje mi się, że moja wersja. W algorytmie wyznaczania otoczki wypukłej Grahama i tak musisz posortować po kącie, jednak odpada Ci reszta kroków, które ma algorytm Grahama oraz problem pozostałych punktów, które nie będą wchodzić w skład otoczki wypukłej. Sposób radzenia sobie z tymi punktami podany przez czopera nie będzie działać, tutaj przykład:

Punkt D byłby połączony z punktami A i C, co nie da nam wielokąta.

Offline Liosan

  • Redaktor

# Styczeń 10, 2012, 21:45:13
Polecam zajrzeć do Wprowadzenia do Algorytmów Cormena.

Liosan

Offline czoper

  • Użytkownik
    • czoper.devlog

# Styczeń 10, 2012, 22:14:45
Sposób radzenia sobie z tymi punktami podany przez czopera nie będzie działać, tutaj przykład:

Punkt D byłby połączony z punktami A i C, co nie da nam wielokąta.

Napisałem, że należy znaleźć dwa sąsiadujące ze sobą punkty w otoczce i między nie wstawić punkty. A i C nie są sąsiednie - D zostałby wstawiony albo między B i C albo B i A, co w obu przypadkach dałoby prawidłowy wielokąt.

Offline Kelesh

  • Użytkownik

# Styczeń 10, 2012, 22:26:20
Przepraszam, rzeczywiście, mój błąd.

Offline Anton Chigurh

  • Użytkownik

# Styczeń 11, 2012, 00:38:18
Mi przyszedł do głowy taki algorytm:

1. znaleźć taką parę punktów (a, b), że dla każdego innego punktu x iloczyn skalarny (a, b) . (a, x) ma taki sam znak
2. poczynając od a lub b szukać kolejnych c, d, itd. takich, że znów dla np. b, c i x te iloczyny mają taki sam znak.

Złożoność nienajlepsza, ale krok pierwszy wydaje mi się eleganckim sposobem na ustalenie choć pierwszych punktów z otoczki np. na potrzeby alg. Grahama.

edit: pomyłka! iloczyn skalarny musi być właściwie między wektorem prostopadłym do (a, b) a wektorem (a, x), bo to przecież cosinus.
« Ostatnia zmiana: Styczeń 11, 2012, 00:42:55 wysłana przez Anton Chigurh »

Offline Kelesh

  • Użytkownik

# Styczeń 11, 2012, 00:54:06
Złożoność pierwszego punktu, bez żadnej heurestyki, to n^3, całego algorytmu n^4. Algorytm do działania wymaga, by punkty stanowiły otoczkę wypukłą. Zadanie, o którym piszę japko, wymaga stworzenia wielokąta z dowolnego zbioru punktów - a więc potencjalnie może to być wielokąt wklęsły.

Offline Anton Chigurh

  • Użytkownik

# Styczeń 11, 2012, 01:00:46
Na "chama" to chyba wystarczy trzasnąć trójkąt - wtedy linie na pewno się nie przetną i będzie wielokąt. Chyba, że źle rozumiem zadanie.

Offline japko

  • Użytkownik

# Styczeń 11, 2012, 10:52:19
No właśnie tu jest problem, bo może być wklęsły. Mam n punktów, nie wiem jakich. Mam z nich stworzyć przynajmniej 1 wielokąt.

Offline Kos

  • Użytkownik
    • kos.gd

# Styczeń 11, 2012, 11:50:45
A zwykły backtracking nie da zadowalających rezultatów? Jedziesz po kolei po punktach i je łączysz, po drodze sprawdzając, czy nie przecinasz żadnego innego odcinka. Jeśli przecinasz, to odrzucasz tę kombinację i próbujesz innej. Jeśli nie znajdziesz, to odrzucasz poprzednio narysowany odcinek itd. Wolne, ale chyba względnie proste.

Albo:
10 policzyć convex hull
20 zobaczyć, czy należą do niego wszystkie punkty
30 jeśli tak, to koniec
40 policzyć convex hull pozostałych punktów
50 połączyć go (jakoś :)) z wcześniejszym convex hullem
60 goto 20

Offline stefan123

  • Użytkownik

# Styczeń 11, 2012, 16:24:10
Ja bym tak samo dodawal do figury kolejne pkty i patrzyl czy nie przecina

Offline czoper

  • Użytkownik
    • czoper.devlog

# Styczeń 11, 2012, 16:52:30
Ok, znalazłem kontrprzykład na swój własny algorytm:

http://imageshack.us/photo/my-images/407/otoczka.jpg/

z punktów 1, 2, 3, 4 mamy otoczkę
rozpatrujemy punkt 5, najbliżej niego znajduje się 2. Najbliższy do punktu 5 połączony z 2 jest punkt 1, wstawiamy punkt 5 między 1 i 2

http://imageshack.us/photo/my-images/32/otoczka2.jpg/

następny rozpatrujemy punkt 6, najbliższy w otoczce jest punkt 5. Najbliższy do punktu 6 połączonego z 5 jest 2. Wstawiamy 6 między 2 i 5. Crash.

http://imageshack.us/photo/my-images/440/otoczka3.jpg/

Pierwsza myśl jest taka:
a) wybierz najbliższy punkt w otoczce
b) wybierz punkt sąsiadujący z punktem z a) taki, że włączenie rozpatrywanego punktu nie spowoduje przecinania się odcinków. Jeżeli oba pasują, to wybierz ten bliższy.
c) jeżeli w punkcie b wybrano punkt, to wstaw rozpatrywany punkt między ten z punktu a) i b)
    jeżeli nie -> wybierz kolejny po odległości najbliższy punkt z otoczki i idź do b)

Będę dalej myślał nad tym, bo to ciekawy problem :)