[MySQL] Afstand tussen coordinaten

[maartenba]

Voor een testcase met Googlemaps ben ik bezig met het aanleggen van een database met wat locaties en hun coordinaten, vereenvoudigd voorbeeld:
tblLocations(id, naam, latitude, longitude)

Nu zou ik een query willen draaien: "Geef me alle locaties die binnen een straal van 50km rond punt x,y liggen".

Probleempjes:
- MySQL heeft geen Spatial Extensions geïnstalleerd
- MySQL 4: geen functions die je zelf kan maken
- Met PHP kan je alle records aflopen, er een rekensommetje opgooien en indien de afstand voldoet hou je hem bij in een array (= overhead)

Nog iemand suggesties om in de MySQL query zelf de afstand al te berekenen ipv na ophalen van alle records en processing door een andere taal?

Deze heb ik na lang zoeken gevonden: http://www.artfulsoftware.com/queries.php#16 . Nadeel: hij is voor MySQL 5 wat nog niet wordt ondersteund door de server hier...

[maartenba]

Gevonden!

code:

SELECT * FROM tblLocations
WHERE <aantal_km> > (1.609344 * (3958 * PI() * SQRT( POW( (<latitude> - sat_lat) , 2) + COS( <latitude> / 57.29578 ) * COS( sat_lat / 57.29578 ) * POW( (<longitude> - sat_lon) , 2) ) / 180) )

[PanMan]

Ik wou je even bedanken voor het posten van je oplossing! Ik ben hier al een paar dagen mee aan het klooien, en jouw oplossing lijkt eindelijk te werken! Thanx! (dat mag ook wel's gezegd!)

[NMe]

Uiteraard mag dat gezegd worden, maar liefst niet elke keer, als iedereen dat zou doen zou dat nogal een rommeltje opleveren.

[GX]

Coordinaatsystemen kunnen nogal wat verschillen; voor Mercator (vrij gebruikelijk) heb je bijvoorbeeld iets nodig als (ik mis GoT-LaTeX skills)..

edit:
argh, laat maar

Ieder systeem kent zijn eigen conversie / calculatie, zo zal WGS84 anders rekenen als EuroConform, Lambert of Mercator.

[ Voor 37% gewijzigd door GX op 30-11-2006 16:41 ]

[Paul]

2 dingen:

- Je rekent met mijlen om ze vervolgens om te zetten

C#:

/*
    The historical definition of a "nautical mile" is "one minute of arc 
    of a great circle of the earth." Since the earth is not a perfect 
    sphere, that definition is ambiguous. However, the internationally 
    accepted (SI) value for the length of a nautical mile is (exactly, by 
    definition) 1.852 km or exactly 1.852/1.609344 international miles 
    (that is, approximately 1.15078 miles - either "international" or 
    "U.S. statute"). Thus, the implied "official" circumference is 360 
    degrees times 60 minutes/degree times 1.852 km/minute = 40003.2 km. 
    The implied radius is the circumference divided by 2 pi:
*/
const int degrees = 360;
const int minutes = 60;
const double nauticalMile = 1.852;
const double kEarthRadiusKms = (degrees * minutes * nauticalMile) / (Math.PI * 2);

(Staat zo in de Location-class van een applicatie waar ik aan werk, ik heb het gevonden op The Code Project.

- Je doet nu die berekening voor _ieder_ item in je locatietabel, afhankelijk van de grootte van die tabel en hoever de items uit elkaar liggen kan dat nogal oplopen. Ik zou dus nog wat dingen voor de where erbij zetten: eerst alles wat in een vierkant met zijde 2*straal zit, om vervolgens die dure berekening op een veel kleiner subset los te laten.

straal in minuten op een great circle == (km / 1.852)
straal in graden op een great circel == minuten / 60
straal voor de where is dus: (km / 1.852 / 60)
Dat zou je kunnen vereenvoudigen naar (km / 0,030866666666666666666666666666667) maar dat is over een maand niet meer terug te herleiden naar de bedoeling ervan

SQL:

SELECT * FROM tblLocations WHERE 
(
    ((<latitude> - straalgraden) > sat_lat) AND 
    ((<latitude> + straalgraden) < sat_lat) AND
    ((<longitude> - straalgraden) > sat_long) AND
    ((<longitude> + straalgraden) < sat_long) AND
    (berekening van vorig jaar)
)

[Janoz]

Sowieso is die berekeneing nog behoorlijk te optimaliseren. Je doet een heleboel vergelijkingen aan beide kanten die hetzelfde zijn. Als je nu, ipv het daadwerkelijke aantal kilometers, gewoon het kwadraat hiervan neemt dan hoef je aan de andere kant ook geen wortel te gebruiken. Door alles even door te rekenen kun je de hele vergelijking terugbrengen tot iets in de trant van "<lastig, maar 1malig berekende waarde> <= (lat- sat_lat)^2 + (long-sat_long)^2". Dat gecombineerd met de testjes van Paul hierboven (waardoor middels lazy evaluation al heel snel foute waarden kunnen worden afgeschoten) moet de boel een stuk efficienter maken.