Wyszukiwanie miejscowości wokół...

Tak przedstawia się wzór Pelsty (no, a przynajmniej tak go nazwano parę tematów niżej ;) ). Wiem, że jest on mocno uogólniony i bodaj bogdans podał jego dokładniejszą wersję, ale na tę chwilę nie jest mi ona potrzebna. Celem błedy odległości nie będą tak duże, żęby mi to przeszkadzało (błąd rzędu 100m na 10 jakoś mnie nie rusza, bo taka specyfika zastosowania ;) ). No i ładnie, w miarę ten wzór rozumiem, ale pojawia się problem. Chciałbym go trochę przekształcić i nie wiem, czy to jest możliwe, sam nie mogę dojść jakos do ładu... Otóż powiedzmy, że mam listę ze współrzędnymi miejscowości. Wybieram sobie jakąś miejscowość, mam jej współrzędne. Chciałbym teraz znaleźć wszystkie miejscowości, leżące w odległości x km od wybranej. I teraz jak to zrobić? Tak by to wyglądało po przekształceniu i przeniesieniu danych na jedną, a szukanych na drugą stronę. No i tak na to patrzę i nie wiem, czy da się z tego wyliczyć to, czego potrzebuję? Mam Lat1 i Lon1, ale potrzebuję jakiegoś równania na Lat2 i Lon2. Nie mogę dojsć z tym do ładu jak i czy w ogóle to możliwe. Czasem wydaje mi się, że rozwiązanie mojego problemu jest banalne i już mi umyka... a czasem, że jednak nie. Cóż, z matematyki nigdy orłem nie byłem, chociaż wiem jak się cyferki dodaje i parę innych rzeczy też mi się tam w głowie kołata. Ale jak mam się miotać i wymyślać cuda, od których się w grobach co niektórzy przewracaja, to wolę jednak zapytać, wiedząc, że parę osób mocno się w tematach takich orientujących jest.

Ja bym zrobił tak: (m₀ to wybrana miejscowość), dla każdej miejscowości m z listy obliczam d_m = d(m_o,m) i sprawdzam czy wyliczona odległość d_m spełnia wymagania (jest czemuś równa, jest od czegoś mniejsza, leży w przedziale <100;200>,...)
pozdrawiam
BTW, ja stosowałem prawie ten sam wzór, tylko promień był czymś pośrednim między promieniem równikowym = 6378,245 km a promieniem biegunowym = 6356,863 km. Dla punktów w rejonie Polski różnica wynosi około 200m przy odległościach rzędu 100km. Możesz uzyskać dużą poprawę dokładności małym kosztem biorąc za r średnią arytmetyczną promienia równikowego i promienia biegunowego.

Hmm, fakt, był tam ten wzór ze średnią arytmetyczną. Może go więc zastosuję.
A w tym zadaniu to raczej rozwiązanie, które podałeś będzie złe. Znaczy wyniki da poprawne, ale liczenie odleglości dla wszystkich miejscowości w Polsce byłoby ciężkie.
Zapomniałem dodać, że w gruncie rzeczy docelowo ma to być zamknięte w zapytaniu SQL. No i obawiam się, że odczytywanie z bazy danych na temat każdej miejscowości i liczenie odległości zabiłoby wydajnością. Dlatego szukam jakiegoś innego rozwiazania.

Inaczej chyba się nie da. Rozważ taki problem: dany jest zbór A punktów na płaszczyźnie. Dla danego punktu o masz znaleźć wszystkie punkty p ze zbioru A, których odległość od o jest w przedziale [c;d]. Musisz wszystkie odległość d(o,p) obliczyć.
Można postąpić tak:

• wybrać punkt O mniej więcej w środku Polski
• zrzutować miejscowości na płaszczyznę P styczną do sfery w punkcie O
• dla każdej miejscowości M wyliczyć współrzędne kartezjańskie rzutu prostopadłego pr(M)
  miejscowości M i zapamiętać je w bazie
• skoro dokładność nie jest priorytetem, to posługiwać się odległościami na płaszczyźnie P.
  Mogę policzyć jaka będzie różnica np. dla Ustrzyk i Świnoujścia.

Hmm, może miałoby to jakiś sens... W momencie, gdy mam te miejscowości zrzutowane na płaszczyznę i w bazie trzymam ich współrzędne na tej właśnie płaszczyźnie, mogę od dowolnego pkt (miejscowości) M wyznaczyć koło o promieniu d i mam miejscowości zawierające się w tym kole, tak? Znaczy to będzie coś z x^{2 + y}2, jak to w równaniu koła (nie pamiętam go dokłądnie, ale to tam pikuś się doszuka). Dobrze kombinuję?

A co do błędu, oczywiście im mniejszy, tym lepiej, ale algorytm z założenia nie ma być używany do wyszukiwania miejscowości w obrębie 1000 km od wybranej, a sporo mniejszych. Dlatego myślę, że jeśli błąd rzeczywistej odległości do przyjetej przeze mnie nie będzie wiekszy niż 10% to nic złego się nie stanie. Odległość drogowa i tak będzie się dużo bardizej rózniła od odległości mapowej.

E:
Chwila, bo chyba głupoty tu piszę.... ten wzór na koło to (x-x0)^2, czyli i tak sprowadzałoby się to do liczenia wszystkich odległości, sama informacja o x i y mi nie wystarczy, musi być powiązana z x0 i y0...

Odległości (lepiej kwadraty odległości) będziesz musiał liczyć. Ale wzory są dużo prostsze, więc obliczenia będą szybsze. Możesz jeszcze usprawnić obliczenia odrzucając od razu te miejscowości dla których |x-x₀| > limit lub |y-y₀| > limit

Hmm, pozostaje więc przetestować to na jakieś paczce danych i zobaczyć, czy szybkość działania jest akceptowalna. Z rzutowaniem na płaszczyznę chyba sobie jakoś poradzę, a jak nie to dopytam. A reszta to już w miarę prosta rzecz.
Dzięki za pomoc.

A gdybyś do bazy danych dodał tabelę distances o strukturze id_miejsc1, id_miejsc2, distance ?

Można. Ale, biorąc pod uwagę że na liście mam wszystkie miejscowości w Polsce, czyli jakos tak ponad sto tysiecy (czy się mylę?), to taka tablica trochę by się rozrosła, nie?

W sumie zakres miejscowości sprawdzanych możnaby ograniczyć od północy i południa, przeliczając km na stopnie szerokości geograficznej. Równoleżniki mają zawsze taką samą szerokość, więc wystarczy przeliczyć i mozna ograniczyć. Pozostaje pas rozciągający się od wschodu na zachód z miejscowościami, ale byłby ich już sporo mniej (w porównaniu z całą Polską ;) ). Gdyby jeszcze ograniczyć od od wsch i zach to ilość miejscowości do zbadnia zmniejszyłaby się znacząco, dobrze rozumuję?
Kwestia jak ograniczyć od wschodu i zachodu, kiedy południki mają różną szerokość zależnie od miejsca. ale i tu dałoby się chyba wybrać jakąś odległość, chociażby szerokość południka w najbardizej wysuniętym na południe miejscu w Polsce. Tym sposobem otrzymujemy jakiś mały wycinek panstwa i w nim mozna juz przelecieć przez wszystkie miejscowości i sprawdzać ich odległości od wybranej.

Chyba jest to dobre rozumowanie, skutecznie powinno przyspieszyć obliczenia, jak mi się wydaje.

Na pewno warto (dla przyspieszenia obliczeń) przejść na współrzędne kartezjańskie. Ja bym przyjął za początek układu (środek Polski) punkt (19^o,52^o). Ponieważ Polska leży w przybliżeniu w połowie drogi między równikiem a biegunem północnym, to za promień Ziemi przyjąłbym 6367,5 km (średnia arytmetyczna promienia równikowego i biegunowego). Przeliczałbym tak: jeśli miejscowość ma długość geograficzną alfa i szerokość fi (w stopniach), to
y = (fi - 52)111,1 111,1 to długość (w km) łuku południka mającego 1^o
x = 2PI6367,5cos(fi)*(alfa - 19)/360.

Pamiętać nr sektora w którym leży miasto, sektor niech będzie np. kwadratem.
Znając sektor, poszukiwania można ograniczyć.