Algorytm prośba o małą pomoc

[arek_wroc]

Potrzebuje pomocy napisania na papierze algorytmu tzw pseudokod, opisowo.
Mam wymyśłeć algorytm do autoamtycznej generalizacji map wektorowych,
tak aby nasze mapy w gpsach były dokładniejsze, chodzi o drogi i rzeki,
jakie propozycje mozna przedstawić?
Na podstawie mapy polski w mapedit.
Prosze o jakies rady wskazówki podpowiedzi.

[sdsyc]

Mam wymyśłeć algorytm do autoamtycznej generalizacji map wektorowych,
tak aby nasze mapy w gpsach były dokładniejsze, chodzi o drogi i rzeki,

Czy zapoznałeś się z pojęciem generalizacji? Np. wpisując hasło w Google?
Czy nie jesteś w błędzie, że dzięki niej mapy w gpsach będą dokładniejsze?

[popej]

Nie będzie dokładniejsza: http://pl.wikipedia.org/wiki/Generalizacja_mapy

W najprostszym wydaniu generalizacja mapy dla Garmina polega na określeniu dla różnych obiektów do jakiej skali (level mapy) obiekt ma być widoczny.

[asandrzej]

Może Kolega pomylił szczegółowość mapy z dokładnością, to często się zdarza.

[arek_wroc]

Tak patrzyłem co to generalizacja, macie racje nie bedzie dokładniejsza, troche źle napisałem, chodzi o szczegółowość, w temacie pracy mam napisane Opracowanie algorytmu (lub algorytmów) wspomagających proces generalizacji map wektorowych.
Informacją dodatkową jest to co mi Pan ostatnio podpowiedział że w efekcie pracy powinien powstać program automatycznie generalizujący sieć dróg na mapie wektorowej. Sieć dróg w projekcie UMP-pcPL (www.ump.waw.pl) umieszczona jest na 4 poziomach widoczności odpowiadających powiększeniu w urządzeniu GPS.Rysowana jest ona jednak tylko na pierwszym z nich, a wygląd w oddaleniu jest uzyskiwany automatycznie podczas kompilacji.
Obecnie efekty jednak nie są zadowalające - sieć dróg jest poszarpana, nieciągła, składająca się z wielkiej
liczby krótkich odcinków co ma niekorzystny wpływ na szybkość wyświetlania. Taką podpowiedz mi dał moj nauczuciel, ale ja mam problemy co z tym zrobić, jesli mozecie cos podpowiedziec to bardzo prosze.

[popej]

Trzeba wziąć dane z UMP, w tym wypadku wszystkie drogi. Zbudować z nich graf a następnie przeprowadzać na tym grafie optymalizacje, zależnie od docelowej skali mapy. To co możesz zrobić to:
- usunąć drogi najniższej kategorii,
- usunąć ronda i połączyć drogi prowadzące do ronda,
- usunąć rampy,
- usunąć krótkie odcinki dróg i połączyć węzły tych odcinków,
- pogrupować drogi o podobnych typach i nadać im jeden wspólny typ
- połączyć odcinki ze wspólnym węzłem i identycznym typem drogi.

I co tam jeszcze wymyślisz

[Alf/red/]

Sieć dróg w projekcie UMP-pcPL (www.ump.waw.pl) umieszczona jest na 4 poziomach widoczności odpowiadających powiększeniu w urządzeniu GPS.Rysowana jest ona jednak tylko na pierwszym z nich, a wygląd w oddaleniu jest uzyskiwany automatycznie podczas kompilacji.
Obecnie efekty jednak nie są zadowalające - sieć dróg jest poszarpana, nieciągła, składająca się z wielkiej
liczby krótkich odcinków

Tak, racja. Ale po pierwsze nie przejmuj się w ogóle warstwami, patrz tylko na tą najdokładniejszą (wyższe są wyłącznie do przyspieszenia wyświetlania), a po drugie nie pracuj na plikach img, które są ... no powiedzmy popsute z punktu widzenia tego, co chcesz zrobić, ale pracuj na źródłach.

[arek_wroc]

Dzieki koledze za podpowiedzi, spróbuje coś wymyslec, a jak co to znow poprosze o rade.
Pozdro.

[arek_wroc]

Drodzy koledzy jednak potrzebuj dalszej waszej pomocy, gdyż nie wychodzi mi to Chodzi o ten pseudokod do automatycznej generalizacji map wektorowych na podstawie dróg i rzek, pomoże mi ktoś? Proszę. Tak aby pokazać zasadę działania algorytmu i wyciągnąć jakiś wniosek poźniej z tego pseudokodu.
Ja tylko takie coś napisałem

Kod: Zaznacz cały

for każda droga na mapie
{
for każdy punkt drogi
{
         if ...
         then
         else
}
}

Pozdrawiam i z góry dzięki Wam.

[Miszka]

Pisanie kodu algorytmu nie ma sensu jak się nie wie co i JAK ten algorytm ma robić.

Nie pisz pseudokodu tylko napisz jak chcesz tę mapę generalizować swoimi słowami.

Podpowiedz Twojego nauczyciela jest sensowna a i popej też napisał dobre podpowiedzi.

Tak wiec napisz pół strony A4 swoimi słowami co i jak algorytm ma robić i ci z pseudokodem pomożemy.

[arek_wroc]

Witam!
Ok napisze o co chodzi wdług mnie, a więc celem pracy jest stworzenie algorytmu (lub algorytmów) wspomagających proces generalizacji map wektorowych.
Sieć dróg w tym projekcie UMP-pcPL (www.ump.waw.pl) umieszczona jest na 4 poziomach widoczności odpowiadających powiększeniu w urządzeniu GPS. Rysowana jest ona jednak tylko na pierwszym z nich, a wygląd w oddaleniu jest uzyskiwany automatycznie podczas kompilacji.
Obecne efekty jednak nie są zadowalające - sieć dróg jest poszarpana, nieciągła, składająca się z wielkiej liczby krótkich odcinków co ma niekorzystny wpływ na szybkość wyświetlania.
W efekcie pracy powinny powstać rozważania o złożoności obliczeniowej mające na celu przeanalizowanie algorytmu, którego program automatycznie generalizuje sieć dróg na mapie wektorowej, którego działania będzie efektywniejsze od dotychczasowych wersji. Czyli tn algorytm ma dać nam to aby nasze mapy były lepsze, efektywniejsze, bardziej szczegółowe, aby drogi i rzeki bo to mam pokazać w pracy były tak pokazane aby zwykły użytkownik widział różnice i te różnice żeby robiły na nim dobry wpływ.
Do tego stworzenia algorytmu trzeba wziąć dane z UMP, w tym wypadku wszystkie drogi i rzeki. Zbudować z nich grafy a następnie przeprowadzać na tych grafach optymalizacje, zależnie od docelowej skali mapy. A więc np:
- znaleść te drogi i rzeki,
- Znalezienie jednej rzeki (wszystkie kawałki tej rzeki)
- posklejanie kawałków w jeden lub kilka wielokątów
- dla każdego kawałka znalezienie kawałków przylegających
- połączenie wielokątów (wielokąty zamieniamy na linie)
- usunąć drogi i rzeki najniższej kategorii,
- usunąć ronda i połączyć drogi prowadzące do ronda,
- usunąć rampy,
- usunąć krótkie odcinki dróg i połączyć węzły tych odcinków,
- pogrupować drogi o podobnych typach i nadać im jeden wspólny typ
- połączyć odcinki ze wspólnym węzłem i identycznym typem drogi.
I trzymając sie tych wytycznych stworzyć pseudokod algorytmu muszę.
Mam nadzieje że zrozumieliście i teraz pomożecie mi? Będę bardzo wdzięczny.
Pozdrawiam.

[Alf/red/]

umieszczona jest na 4 poziomach widoczności odpowiadających powiększeniu w urządzeniu GPS. Rysowana jest ona jednak tylko na pierwszym z nich

Bądźmy precyzyjni. Nie rysowana, ale tworzona albo definiowana. Bo rysowana jest przez odbiorniki albo inne cosie wyświetlające mapę - to co jest na pierwszej warstwie, umieszczają (uwaga: po uproszczeniu) na wyższych.

ma dać nam [...] bardziej szczegółowe

Nienie. Przecież usuwasz szczegóły. Po takiej obróbce nie będą bardziej szczegółowe w żadnym sensie.

Temat zaczął się rozbijać na kilka wątków, do których powinieneś podchodzić osobno (przynajmniej częściowo).

- znaleść te drogi i rzeki,
- Znalezienie jednej rzeki (wszystkie kawałki tej rzeki)

Znajdowanie obiektów, hmm - jak usuniesz np. rondo, to go nie znajdziesz, chyba że jakoś zapamiętasz co i skąd usunąłeś.

- posklejanie kawałków w jeden lub kilka wielokątów
- dla każdego kawałka znalezienie kawałków przylegających
- połączenie wielokątów (wielokąty zamieniamy na linie)

Drogi zawsze są liniami. Rzeki czasem są wielokątami, i tylko na większych powiększeniach.

- usunąć drogi i rzeki najniższej kategorii,
- usunąć ronda i połączyć drogi prowadzące do ronda,
- usunąć rampy,
- usunąć krótkie odcinki dróg i połączyć węzły tych odcinków,

Tak, to dobre upraszczanie. Po usunięciu ramp też powinieneś łączyć rozdzielone w ten sposób drogi (w miejscu, gdzie się krzyżują?)

- pogrupować drogi o podobnych typach i nadać im jeden wspólny typ
- połączyć odcinki ze wspólnym węzłem i identycznym typem drogi.

Typów nie ma dużo, więc dużo tu nie ugrasz. Ale owszem, można.
Łącząc odcinki pamiętaj też o nazwach dróg (ulic) - jeśli masz robić także wyszukiwanie...

Ogólnie całość jest w dobrym kierunku. Teraz poszczególne kroki próbuj w tym samym stylu rozbijać na drobniejsze kroczki tak, jak Ci się wydaje (tak powstają algorytmy). I samo wyjdzie, co zależy od czego. No i nikt nie będzie mógł zarzucić, że to nasza praca

Acha, i przy końcu tworzenia pracy zadbaj o dobrą korektę językową (widzę zagrożenia: niespójność terminologii, skomplikowane zdania, błędy językowe aż do ortograficznych - celowo nie poprawiam w oryginalnej treści).

[arek_wroc]

Witam!
No dobra dzieki za sprostowania małe, ale mieliście mi pomóc napisać.... pomóżcie jak możecie? Sam sobie nie poradze akurat w tym. Miszka pomóc mi jak możesz tak jak pisałeś i inni też.
Pozdrawiam.

[arek_wroc]

Koledzy pomóżcie chociaż trochę, zróbcie dobry uczynek? Nic mi się nie układa, nawet komp mi się psuje:( i mam kłopot z tym.
Pozdrawiam Was!

[popej]

Zadałeś ogólne pytanie i dostałeś ogólną odpowiedź. Jak zadasz konkretne pytanie, to możesz się spodziewać szczegółowej odpowiedzi.

Całej pracy za Ciebie nie zrobimy.