Autor Wątek: optymalizacja zwyczajnej linii łamanej  (Przeczytany 2914 razy)

Offline nembutal

  • Użytkownik

# Styczeń 13, 2011, 20:27:26
Chce znaleźć minimalny podzbiór wierzchołków oryginalnej linii, który tworzy zoptymalizowaną łamaną oddalaną o mniej niż jakaś zadana odległość od oryginalnej linii. Dodatkowo zoptymalizowana linii musi pozostać zwyczajna (czyli jej segmenty się nie przecinają). Czy znany jest dobry algorytm do tego problemu?

Offline Mr. Spam

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

Offline Liosan

  • Redaktor

# Styczeń 13, 2011, 21:42:21
Wiesz co pentobarbital... a mógłbyś to wytłumaczyć tak, żeby taki laik jak ja to zrozumiał? :) Bo nie mam pojęcia co to jest zoptymalizowana łamana, a jedyna odległość jaka mi przychodzi do głowy to odległość Hausdorffa, a to chyba nie o to chodzi :)

Liosan

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Styczeń 13, 2011, 21:48:29
Najprostszy algorytm:
1.Szukasz wierzchołka, który możesz usunąć nie łamiąc żadnego z założeń.
2. Usuwasz go, go to 1.

Offline izaw

  • Użytkownik

# Styczeń 13, 2011, 21:58:42
Krzysiek K.,
 co y Twoje pojęcia nie oznaczały (a to jest najważniejsze), nie jest to optymalne. Trzeba zastosować programowanie dynamiczne. Twój algorytm zachłanny w ogólnym przypadku jest nieoptymalny.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Styczeń 13, 2011, 22:07:50
co y Twoje pojęcia nie oznaczały (a to jest najważniejsze), nie jest to optymalne. Trzeba zastosować programowanie dynamiczne. Twój algorytm zachłanny w ogólnym przypadku jest nieoptymalny.
Wiadomo. Za to jest szybki i spełnia wszystkie założenia zadania, a wątpię, by użytkownikowi przeszkadzało to, że linia nie jest rysowana w sposób optymalny. :)

Offline izaw

  • Użytkownik

# Styczeń 13, 2011, 22:13:48
Niekoniecznie. Chce zoptymalizowanego. W Twoim sposobie jeden dość daleki punkt po usunięciu może wyczerpać pulę niedokładności a łamana pozostanie szarpana. Optymalnie może wyjść dość gładka. Dodatkowo ten jeden punkt może diametralnie zmienić jej charakter.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Styczeń 13, 2011, 22:25:49
Cytuj
W Twoim sposobie jeden dość daleki punkt po usunięciu może wyczerpać pulę niedokładności a łamana pozostanie szarpana.
Nie może wyczerpać, bo kryterium jest lokalne.

Offline nembutal

  • Użytkownik

# Styczeń 14, 2011, 00:17:16
Wiesz co pentobarbital... a mógłbyś to wytłumaczyć tak, żeby taki laik jak ja to zrozumiał? :) Bo nie mam pojęcia co to jest zoptymalizowana łamana, a jedyna odległość jaka mi przychodzi do głowy to odległość Hausdorffa, a to chyba nie o to chodzi :)

Segmenty oryginalnej łamanej (http://en.wikipedia.org/wiki/Polygonal_chain) otaczasz dyskami o szerokości odpowiadającej zadanej granicy błędu (to jest ta odległość * 2) i w ramach tej otoczki musisz znaleźć optymalną krzywą - to jest z minimalną liczbą wierzchołków.

Gdzieś wyczytałem, że jeśli usunie się wymaganie żeby wierzchołki optymalnej krzywej należały do zbioru wierzchołków oryginalnej krzywej to są możliwe wydajniejsze algorytmy, więc niniejszym to wymaganie porzucam ;)

Z kolei w Approximating polygons and subdivisions with minimum-link paths (http://people.cs.ubc.ca/~snoeyink/papers/minlink.ps.gz - sory, ale nie daje rady przekonwertować tego czytelnie do PDF) wyczytałem chyba jakąś przerażającą rzecz (oczywiście o ile dobrze zrozumiałem):
We also show that approximating subdivisions and approximating with chains with no self-intersections are NP-hard


Najprostszy algorytm:
1.Szukasz wierzchołka, który możesz usunąć nie łamiąc żadnego z założeń.
2. Usuwasz go, go to 1.
Za mało konkretów jak dla mnie, nieuka. Zwłaszcza problematyczne dla mnie jest to jak wydajnie w każdym kroku sprawdzać, że nowo powstały segment nie przecina pozostałych i obliczać jego odległość od oryginalnych segmentów?
« Ostatnia zmiana: Styczeń 14, 2011, 00:20:17 wysłana przez nembutal »

Offline counterClockWise

  • Użytkownik

# Styczeń 14, 2011, 00:29:51
Chce znaleźć minimalny podzbiór wierzchołków oryginalnej linii, który tworzy zoptymalizowaną łamaną oddalaną o mniej niż jakaś zadana odległość od oryginalnej linii. Dodatkowo zoptymalizowana linii musi pozostać zwyczajna (czyli jej segmenty się nie przecinają). Czy znany jest dobry algorytm do tego problemu?

Jak policzyć odległość zoptymalizowanej łamanej od linii?
Potrafię kilka metod sobie wyobrazić, ale przyznam szczerze, że nie bardzo wiem jaka jest naturalna ani jaka w tym zadaniu.

Cytuj
We also show that approximating subdivisions and approximating with chains with no self-intersections are NP-hard

Jeśli to problem NP-trudny, to mało pomoże optymalne rozwiązanie. I tak każdy dokładny algorytm będzie wolny.
« Ostatnia zmiana: Styczeń 14, 2011, 00:32:34 wysłana przez counterClockWise »

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Styczeń 14, 2011, 14:39:58
Możnaby dla każdego wierzchołka policzyć jakąś "wagę" mówiącą, jak bardzo jego usunięcie zmieni kształt linii łamanej. Potem usunąć te o najmniejszych wagach.

Offline nembutal

  • Użytkownik

# Styczeń 14, 2011, 15:36:38
Niech ktoś zrobi kompo o tym problemie :) Można tu podawać trzyzdaniowe opisy algorytmu, ale przypuszczam, że mając już implementacje bardzo łatwo znalazłbym przypadki testowe, które dałyby zupełnie nieakceptowalne wyniki, albo by się okazało, że są koszmarnie wolne.

Offline osculati

  • Użytkownik

  • +1
# Lipiec 04, 2012, 15:45:00
Alleluja! Od ca dwóch lat - fakt, że z dużymi przerwami - chodzi mi po głowie identyczny, jak sądzę, problem! Choć nazwałbym go raczej uproszczeniem (przerzedzeniem, redukcją) łamanej niż optymalizacją.
Chodzi o to żeby odrzucić część wierzchołków łamanej ale tak aby: 1) łamana po redukcji miała jak najmniej wierzchołków, 2) żaden z odrzuconych wierzchołków nie leżał dalej (od łamanej po redukcji) niż jakaś zadana odległość.

Moje rozwiązanie w uproszczeniu polega na:
  • obliczeniu dla każdego wierzchołka: 1) minimalnej liczby kroków w jakich można do niego dotrzeć, 2) numeru wierzchołka poprzedzającego na tej minimalnej trasie,
  • odtworzeniu takiej minimalnej trasy przeglądając obliczone wartości od tyłu.
Nie wchodzę w niuanse, których jednak kilka jest. Załączam obrazek, który może coś dodatkowo wyjaśni.

Mam to napisane. Działa (czasem się zacina - może jakiś błąd w kodzie). Ale główny problem w tym, że algorytm ma złożoność O(n3) i wypadku moich danych (np. 30000 wierzchołków) skrypt działa kilka godzin.

Może można to jakoś udoskonalić ( zredukować do O(n2)? ).
Twoja kolej nembutal.

Offline osculati

  • Użytkownik

# Lipiec 04, 2012, 15:59:15
Jeszcze jeden obrazek, z rozwiązaniem dla łamanej przykładowej.

Na amarantowo - wierzchołki łamanej po redukcji (niebieska linia).
Kółka wokół wierzchołków pokazują zadaną, dopuszczalną odległość wierzchołków od łamanej. Łamana po redukcji przechodzi nie dalej niż ta właśnie odległość od każdego z wierzchołków.

czarne cyfry - numeracja wierzchołków,
czerwone cyfry - najkrótsza odległość od początku łamanej,
w nawiasach - numer wierzchołka poprzedzającego.
« Ostatnia zmiana: Lipiec 04, 2012, 16:06:48 wysłana przez osculati »

Offline nembutal

  • Użytkownik

# Lipiec 04, 2012, 16:58:01
Mam to napisane. Działa (czasem się zacina - może jakiś błąd w kodzie).
Czyli nie działa :) Właśnie to jest zabawne z algorytmami graficznymi, że wyeliminowanie takiego problemu często prowadzi do odrzucenia całego już napisanego algorytmu :)

Ale główny problem w tym, że algorytm ma złożoność O(n3) i wypadku moich danych (np. 30000 wierzchołków) skrypt działa kilka godzin.
Nieakceptowalne :)

Twoja kolej nembutal.
Nic z tego. Porzuciłem ten problem jak tylko uświadomiłem sobie, że zadanie jest na wiele miesięcy, zwłaszcza przy moich wymaganiach (ma działać szybko i zawsze dawać poprawny rezultat).

BTW W czym zrobiłeś te rysunki? (to absolutna konieczność żeby mieć dobrą wizualizacje pisząc taki algorytm)
« Ostatnia zmiana: Lipiec 04, 2012, 17:03:13 wysłana przez nembutal »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +1
# Lipiec 04, 2012, 17:12:25
Moja propozycja:
- pierwszy wierzchołek bierzemy zawsze,
- na bieżąco trzymamy informację o tym gdzie ma prawo znaleźć się kolejny wierzchołek (część płaszczyzny),
- przychodzą kolejne wierzchołki -> aktualizujemy listę ograniczeń,
- jeżeli przyjdzie wierzchołek, który leży w nieuprawnionym fragmencie płaszczyzny, albo który dodaje ograniczenia powodujące sprzeczność -> oznaczamy poprzedni wierzchołek jako wybrany i zaczynamy nowy zestaw ograniczeń

Algorytm zachłanny, więc nie da idealnych wyników, ale powinien być szybki i sensowny. Listę ograniczeń można trzymać jako wypukły fragment płaszczyzny ograniczonymi półprostymi/odcinkami (można sensownie na tym robić CSG, czyli dodawać nowe ograniczenia). Złożoność pesymistyczna jest O(n^2) (gdy ignorujemy wszystkie punkty poza pierwszym i ostatnim), ale można po drodze upraszczać zestaw ograniczeń (np. założyć max liczbę wierzchołków wypukłego fragmentu i powyżej niej usuwać te, które najmniej powiększają płaszczyznę figury). Wtedy będzie O(n).