Sortowanie punktów współrzędnych geograficznych

0

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.

1

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)
0

@abrakadaber, płynąłeś kajakiem po Czarnej Hańczy? Rzeka wije się mniej więcej tak:
River2.png
Algorytm najbliższego punktu zupełnie się do tej rzeki nie nadaje.

0

@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.

0

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ć.

0

@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

River2.png

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

0

Optymista, do 3 trafisz dopiero z 4.River3.png

0

@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.

0

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.

0

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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1