Sortowanie punktów współrzędnych geograficznych

Witam,

Mam plik z danymi wejściowymi, które przechowują współrzędne geograficzne rzeki oraz głębokość w następującej postaci:

szerokość_geogr; długość_geogr; głębokość;

Algorytm, który napisałem pobiera te dane wejściowe, przetwarza. Problem jest taki, że wymagane jest aby dane wejściowe były posortowane tzn. żeby punkty prowadziły do celu. A ten plik z danymi wejściowymi, który mam jest ogromny i są nie uporządkowane. Bo np. jest tak, że jest punkt pierwszy, potem dalej do przodu punkt drugi, potem dalej do przodu punkt trzeci a punkt czwarty jest o jakieś 300 metrów wstecz.... Słyszałem, że jest program QGIS, do którego można wczytać współrzędne a potem jakoś posortować żeby były w kolejności do celu tylko nie wiem jak to się robi. Może ktoś z Was wie ? Albo jak nie program QGIS to jakiś inny pomysł?

Pozdrawiam.

te dane są w jakikolwiek sposób posortowane? Może są np. obszarami podzielone? Na chłopski rozum jeśli to jest rzeka to powinna to być linia ciągła więc na początek możesz je spróbować posortować po prostu po latitude albo longitude - to powinno być najszybsze. BTW jeśli nie masz ich podanych w odpowiedniej kolejności to jak rzeka jest mocno zagmatwana to może się okazać, że uzyskanie poprawnej kolejności jest niemożliwe. Natomiast najlepszy efekt powinno dać sortowanie ich w ten sposób:

1. bierzesz punkt (idealnie by było jakby to był początek lub koniec)
2. szukasz najbliższego w 2d punktu do niego
3. teraz szukasz najbliższego do 2 ale z wykluczeniem już "obrobionych"
   Jednak to zapewne się nie uda ze względów czasowych lub pamięciowych w zależności od metody. Zauważ, że za każdym razem trzeba sprawdzić wszystkie niesprawdzone albo zudować z tego graf (tu może po prostu zabraknąć pamięci jeśli tych punktów masz dużo)

@abrakadaber, płynąłeś kajakiem po Czarnej Hańczy? Rzeka wije się mniej więcej tak:

Algorytm najbliższego punktu zupełnie się do tej rzeki nie nadaje.

@bogdans To co narysowałeś jest linią ciągłą więc na moje oko przy zastosowaniu tego algorytmu można by uzyskać "ścieżkę" rzeki.

E tam, dojechaliśmy do punktu 1, algorytm najbliższego punktu zaproponuje zrobienie przekopu do punktu 2, do punktu 3 możemy nigdy nie trafić.

@bogdans zupełnie nie masz racji. Po pierwsze, co chyba logiczne, jakby nie sortować to WSZYSTKIE punkty biorą w tym udział. Więc co najwyżej możesz zmienić bieg koryta rzeki zamiast niebieskim mogło by wyjść zielonym

Po drugie jeśli masz trzy punkty na krzyż to choćbyś na głowie stawał to nic mądrego nie wymyślisz.

Optymista, do 3 trafisz dopiero z 4.

@bogdans ale co próbujesz udowodnić bo nie wiem? Poza tym pisałem w pierwszym poście

ja sam napisał(a)

BTW jeśli nie masz ich podanych w odpowiedniej kolejności to jak rzeka jest mocno zagmatwana to może się okazać, że uzyskanie poprawnej kolejności jest niemożliwe.

no i przed chwilą

też ja sam napisał(a)

Po drugie jeśli masz trzy punkty na krzyż to choćbyś na głowie stawał to nic mądrego nie wymyślisz.

Próbuje wykazać, że algorytm najbliższego punktu jest raczej kiepski. Wymaga dużej ilości obliczeń, dla zagmatwanej rzeki "wyprodukuje" nową rzeką niepodobną do oryginału, dla w miarę prostej rzeki zadowalający może być algorytm porządkowania wg. współrzędnych geograficznych.
A do czego odnosi się zdanie

Po drugie jeśli masz trzy punkty na krzyż to choćbyś na głowie stawał to nic mądrego nie wymyślisz.
to nie wiem.

algorytm jest dobry o ile masz odpowiednią ilość danych. Jeśli na 10km rzeki i 10 zakrętów o 360st masz 100 punktów, co 100m to żaden algorytm tego nie posortuje poprawnie. Ale już mając 10000 punktów, co 1m rysunek wyjdzie poprawnie.

Zauważ, że rzeka to nie droga - ona się nie przecina i nie wraca.

BTW jak taki jesteś pewny fiaska użycia tego algorytmu to zaproponuj coś mądrzejszego.

Nie mam pomysłu na coś mądrzejszego.

Jakość algorytmu można oceniać tylko doświadczalnie, brać zestawy punktów dla znanych rzek, wyrysowywać przypuszczalne trajektorię i porównywać z mapą.

Ciekawi mnie dlaczego wykonywany jest trudny (chyba) pomiar głębokości, a nie ma pomiaru szerokości. Byłoby wtedy dodatkowe kryterium - natężenie strumienia wody (w przybliżeniu głębokość*szerokość).

Mam plik z ponad 100 000 tys punktów które są jakby blisko siebie co 0,5 lub 1 metra. Ale właśnie są nieuporządkowane.
Czytałem wyżej posty, widzę że może by dało się napisać algorytm, ale nie ma czasu na pracę magisterską gdyż z nim za dużo roboty będzie. W mojej pracy magisterskiej można mieć założenie, że wymagane są posortowane na wejściu.

A może są specjalistyczne programy GIS, które wczytają ten plik i uporządkują chcociaż fragment ? Kto wie ?

Pozdrawiam.

Rozumiem, że pracę magisterską oddajesz jutro i dlatego taki "skomplikowany" program nie wchodzi w grę. ;P

Nie oddaję jutro, dopiero w czerwcu :-)

Algorytm który przyszedł mi do głowy:

1 Posortuj punkty względem X, przy okazji zerowym kosztem policzysz min/max
2 Przyjmij sobie jakiś epsilon odległości, który powie jaka maksymalna odległość pomiędzy punktami jest uznawana jeszcze za ciągłość rzeki (wspomniałeś o 1m - dobre na początek)
3 dodaj do listy 1 punkt z lewej i poruszając się w prawo sprawdzaj czy kolejny punkt jest mniejszy od epsilon jeśli tak to jest obok i możesz go dodać do odcinka rzeki, jeśli nie oznacza to, że w danym X jest kilka Y więc tworzysz nową tablicę odcinka rzeki dla każdego "nowego" Y
4 sprawdzasz kolejne punkty w prawo i przypisujesz do odpowiednich odcinków
5 łączysz odcinki rzeki w całość - tutaj już dowolny naiwny algo zagra

Weź napisz po ludzku czego chcesz to pomogę, ale zrób to porządnie to też porządnie odpiszę.

Coś tam z gisami do czynienia miałem. Jakiż to plik jest i dlaczego są poszczególne punkty zapisane chaotycznie? Czy punkty dotyczą tylko rzeki, czy są też jakieś punkty z terenu (np. o głębokości 0). Czy na pewno punkty da się jednoznacznie posortować? W tym sensie, że nie ma danych punktów, które są w danej rzece "obok siebie", albo na zakręcie? Wizualizowałeś sobie ten plik? Jak wygląda rysunek?

PS. Gdzie piszesz pracę mgr? :)

damianu90 napisał(a):

Mam plik z ponad 100 000 tys punktów które są jakby blisko siebie co 0,5 lub 1 metra. Ale właśnie są nieuporządkowane.
Czytałem wyżej posty, widzę że może by dało się napisać algorytm, ale nie ma czasu na pracę magisterską gdyż z nim za dużo roboty będzie. W mojej pracy magisterskiej można mieć założenie, że wymagane są posortowane na wejściu.

A może są specjalistyczne programy GIS, które wczytają ten plik i uporządkują chcociaż fragment ? Kto wie ?

Pozdrawiam.

1. Jeżeli są tak bardzo blisko siebie to algorytm szukający najbliższego punktu powinien dać zadowalające wyniki.

2. 100 tysiecy punktów to nie jest ogromna liczba, zwłaszcza że nie potrzebujesz jakiegoś super krótkiego czasu działania algorytmu, jak podziała nawet 2 dni to przeżyjesz. Taka liczba punktów też spokojnie zmieści się w pamięci (zakładając z nadmiarem, że 1 punkt w pamięci zajmuje 1 kilobajt ramu to i tak zajmie to to tylko 100 MB ramu).

3. Z tych powodów możesz sobie pozwolić na taki algorytm (dość kosztowny obliczeniowo, ale prosty w implementacji):
   a) Na początku Twojej listy umieszczasz punkt będący początkiem rzeki (robisz to ręcznie, w pliku)
   b) Wczytujesz wszystkie punkty do pamięci (do listy/tablicy).
   c) Algorytm zaczyna od pierwszego punktu (tego jaki w pliku wskazałeś jako początek).
   d) Algorytm liczy odległość do każdego z pozostałych i nieprzetworzonych jeszcze punktów rzeki. Liczenie odległości mając współrzędne zrobisz według tego wzoru: https://pl.wikipedia.org/wiki/Ortodroma - wzór pomija to, że ziemia jest elipsoidą, a nie kulą, ale w tym zastosowaniu nie ma to znaczenia.
   e) Jako punkt następny wybierasz ten, do którego odległość jest najmniejsza. Oznaczasz oba punkty jako przetworzone - możesz oznaczać dodatkową flagą lub np. ustawiać im głębokość na 30 km i na tej podstawie twój program będzie wiedział, że punkt jest już przetworzony i trzeba go ignorować w szukaniu.
   f) Czynności powtarzasz dla kolejnego punktu.

4. Pamiętaj, że jak napiszesz to przetestuj program najpierw na mniejszym fragmencie danych, bo dla 100 tys. pewnie program podziała jakiś dłuższy czas. Możesz sobie dodać wypisywanie numeru aktualnie przetwarzanego punktu co np. 1 tysiąc przetworzonych (tylko nie co każdy punkt bo to spowolni program).