[PHP] Afstand berekenen tussen coordinaten.

[Reddol]

Doel:

---

Ik wil afstanden berekenen tussen postcodes, veel postcodes.
Uiteindelijk moet ik een script hebben dat mij kan vertellen welke postcode (van degene in de db) in een straal van 10 km is bij (bijvoorbeeld) mijn eigen postcode vandaan

B.V.: Ik vul postcode in: 1234AB, ik selecteer de straal: 10KM
En alle postcodes in de database worden gechecked en degene die binnen 10km zijn worden weergegeven. Het gaat hier om minimaal 800 postcodes.

Wat heb ik:

---

Ik heb via de API van google al een bereken programma gemaakt >hier<. Hier voer je dus 2 bestaande postcodes in en klik je op bereken. De coordinaten worden gegeven en zo ook de Hemelsbrede afstand in Kilometers.

Vraag:

---

Omdat het om zoveel postcodes gaat zou ik graag willen weten wat jullie de beste manier lijkt om dit te doen.
Eerst alle coordinaten van de postcodes verzamelen en opslaan?
Postcodes indelen in groepen?

Het moet namelijk niet 10 minuten duren voordat er postcodes binnen het bereik gevonden zijn!

[Anoniem: 28333]

Na het googlen naar 'NL postcode database' kwam ik op deze site:
http://kvdb.net/projects/6pp/

Deze site crawled postcodes op internet (om geen gebruik te maken van niet gratis gegevens) en bied gratis api's en zelfs een db dump aan. Met een lokale database kun je waarschijnlijk met 1 query waarschijnlijk precies de gegevens opvragen die je wilt.

[RobertMe]

Handigste is als je bij het toevoegen van een postcode aan de DB meteen de coördinaten ervan doet opslaan (deze kun je bij Google opvragen). Vervolgens staat hier een mooi voorbeeld hoe de berekening te doen. Toen ik dit zelf niet zo ontzettend lang geleden nodig had ben ik voor de (simpele) select query gegaan, en heb ik deze iets verder geoptimaliseerd door de RADIANS( city_latitude ) en RADIANS( city_longitude ) bij de insert al op te slaan, dan hoeft deze dus niet meer elke keer door de DB berekend te worden, maar gebruik je daar de rad_lattitude en rad_longitude kolommen. COS( RADIANS(:latitude) ), RADIANS(:longitude) en SIN( RADIANS(:latitude) ) kun je vervolgens al in je code berekenen, dan hoeft de db dit niet meer te doen (met een beetje pech zal hij deze berekeningen per record opnieuw doen, terwijl de uitkomst toch nooit veranderd).

Als zelfs dat nog niet snel genoeg is zou je eerst een vierkant kunnen leggen om de circel, hieruit komt een gewone lattitude BETWEEN x AND y AND longitude BETWEEN a AND b, dit is voor de DB peanuts en dan zijn dus al heel veel postcodes weg gefilterd, waardoor nog maar een klein gedeelte over blijft waarop je vervolgens de gehele berekening kan doen. (en mocht dat nog niet snel genoeg zijn, zou je ook nog eerst alle postcodes kunnen ophalen die liggen in het vierkant wat in de circel past, en dan voor die wat liggen tussen het vierkant om de circel en het vierkant in de circel de berekening doen).

[Reptile209]

RobertMe schreef op donderdag 05 november 2009 @ 18:44:
Als zelfs dat nog niet snel genoeg is zou je eerst een vierkant kunnen leggen om de circel, hieruit komt een gewone lattitude BETWEEN x AND y AND longitude BETWEEN a AND b, dit is voor de DB peanuts en dan zijn dus al heel veel postcodes weg gefilterd, waardoor nog maar een klein gedeelte over blijft waarop je vervolgens de gehele berekening kan doen.

Of pak het gemiddelde van beide vierkanten en gebruik dat als een goede benadering. Dan zit je bij een paar PC's verkeerd, maar het gaat waarschijnlijk toch maar om een benadering van de afstand (boeit niet dat het eigenlijk 10,02 km is). Bovendien zit je nog met het verschil tussen de afstand hemelsbreed en op de weg, dat filtert elke fout wel aardig weg.

[Reddol]

Het vierkant idee vind ik wel handig! Ik denk dat ik hiervoor ga.
Ligt een beetje aan het aantal kilometers van mijn straal.
Het andere, de berekeningen via SQL lijkt me ook goed, maar hier zal ik nog even goed naar moeten kijken. Op het 1e oog begrijp ik hem niet.
Bedankt!

edit:
6pp ga ik ook even bekijken, maar het lijkt me handig om er zo weinig mogelijk externe data bij te betrekken.

[ Voor 18% gewijzigd door Reddol op 05-11-2009 18:54 ]

[.oisyn]

Nederland is klein genoeg om het te benaderen als Euclidische geometrie, en daarbij de kromming van de aarde te negeren. Zeker gezien het feit dat postcodes an sich al geen punten zijn maar gebieden is de discrepantie die je krijgt zo goed als verwaarloosbaar. Map ze dus van te voren gewoon als x en y coordinaten in kilometers, en als afstandsfunctie gebruik je gewoon √(x² + y²). In een database als PostgreSQL is dat nog snel ook omdat hij daar gebruik kan maken van een geometrische index. Zonder een dergelijke index kun je je query idd optimaliseren door naast die afstandsfunctie in de WHERE ook gewoon te filteren op het omliggende vierkant. Voor het vierkant gebruikt ie dan de index, en de overgebleven postcodes filtert ie met de afstandsfunctie.

[ Voor 32% gewijzigd door .oisyn op 05-11-2009 19:06 ]

[Reptile209]

.oisyn schreef op donderdag 05 november 2009 @ 19:03:
[...] Map ze dus van te voren gewoon als x en y coordinaten in kilometers, en als afstandsfunctie gebruik je gewoon √(x² + y²). [...]

Dan kan je nog iets optimaliseren naar snelheid (ten koste van opslagruimte) door ook de kwadraten van x en y alvast in je database te zetten, hoef je alleen nog de som en de wortel uit te rekenen.

[RobertMe]

Het vierkant idee vind ik wel handig! Ik denk dat ik hiervoor ga.

Het andere, de berekeningen via SQL lijkt me ook goed,

Beide moet je gewoon in SQL doen, als je eerst alle data van de db gaat overhevelen naar je script en daar gaat controleren heb je al een enorme impact op je performance, dit terwijl de db dit zelf ook met gemak kan berekenen/filteren.

Zeker gezien het feit dat postcodes an sich al geen punten zijn maar gebieden is de discrepantie die je krijgt zo goed als verwaarloosbaar.

Google maakt anders wel degelijk onderscheid tussen de verschillende huisnummers (als TS de huisnummers ook beschikbaar heeft natuurlijk), en bij lange straten kan het dan dus wel degelijk uit maken.

Maar inderdaad zou je in de meeste gevallen "vals" kunnen spelen, doordat de afstand sowieso al hemelsbreed is en niet afstand over de weg etc. De oplossing van Reptile209 is dan ook zeer netjes en zou waarschijnlijk als je gaat kijken naar de snelheid en de nauwkeurigheid er het beste vanaf komen van alle 3 de manieren (pythagoras op plat vlak (niet zo ontzettend snel door de berekening en niet helemaal nauwkeurig), nauwkeurige berekening (heel nauwkeurig maar dan wel ook de langzaamste) en zijn oplossing met het gemiddelde van beide vierkanten (heel snel, maar niet zo nauwkeurig))

[Reddol]

Ik vind het mooie ideen allemaal, maar om eerlijk te zijn gaat het mij een beetje ver.
Vind het zeer moeilijk te begrijpen.

Ik heb nu gemaakt: Een Database tabel met daarin: postcode, lontitude en altitude.
Nu wil ik een functie maken in php waarbij ik dus de range kan veranderen (in km).
Hoe moet ik er dan achter komen hoeveel het verschil in coordinaten is?
Of hebben jullie misschien een stukje code voor mij?

[Reptile209]

Even voor de goede orde: de altitude is de hoogte, je bedoelt (hoop ik) dat je de longitude en de latitude hebt.

Wat ik zou doen (zonder verder gehinderd te worden door kennis van de do's en don'ts van de Google API) is het volgende. Kies een referentiepunt, bijvoorbeeld Londen (ligt mooi buiten je doelrange, hoewel je foutmarge kleiner wordt als je dichter bij het te gebruiken grid - NL - zit). Bereken met google voor iedere postcode de afstand (x en y in km, dit zijn je nieuwe coordinaten) tot je referentie. Als je nu twee punten wil vergelijken (= onderlinge afstand berekenen) kan je gewoon met Pythagoras aan de slag op basis van het verschil in x en y. Of je berekent de hoeken van je vierkant en kijkt welke x en y coordinaten daarbinnen vallen.

Probeer dit maar eens op een A4-tje met twee willekeurige stippen, 't is niet zo moeilijk als dat het klinkt!

Stukken code kado geven, doen we niet aan. Daar leer je niks van .

[Reddol]

Ik heb het inderdaad over de Latitude sorry.

Bedankt voor je uitleg, ik ga het uit proberen te voeren en laat het nog weten!

[.oisyn]

Reptile209 schreef op donderdag 05 november 2009 @ 19:09:
[...]

Dan kan je nog iets optimaliseren naar snelheid (ten koste van opslagruimte) door ook de kwadraten van x en y alvast in je database te zetten, hoef je alleen nog de som en de wortel uit te rekenen.

Ten eerste bedoelde ik natuurlijk ∆x en ∆y, je wilt immers de afstand tussen twee postcodes, dus die preprocessing gaat al niet. Bovendien kun je dat amper een optimalisatie noemen - de data access zal veel duurder zijn dan die ene berekening. Al helemaal als je de hoeveelheid data per rij groter maakt.
.edit: hmm nu ik dit typ begin ik me af te vragen of het überhaupt nut gaat hebben om deze versimpeling te doen, al is de nauwkeurige berekening wel heel wat ingewikkelder, maar natuurlijk nog steeds niets om over na te denken bij zo weinig db records.

RobertMe schreef op donderdag 05 november 2009 @ 19:20:
Google maakt anders wel degelijk onderscheid tussen de verschillende huisnummers (als TS de huisnummers ook beschikbaar heeft natuurlijk), en bij lange straten kan het dan dus wel degelijk uit maken.

Mijn punt is juist dat het hier niet gaat om huisnummers, het gaat om afstand tussen postcodes. Die afstand is feitelijk afhankelijk van huisnummers, maar als die niet hebt, zit je sowieso met een afwijking. Dat maakt de afwijking die je door mijn berekening krijgt zo goed als verwaarloosbaar.

[ Voor 39% gewijzigd door .oisyn op 05-11-2009 22:54 ]

[Fish]

hoewel ik ze nooit gebruikr heb zoe je het kunnen proberen met geospacial queries
e.g.
http://www.oracle.com/tec...t_9i/9iR2_spatial_ds.html
https://www.ngdc.noaa.gov...le_Oracle_Spatial_Queries


800 postcodes is natuurlijk peanuts zelfs met een hele slechte berekening

[ Voor 35% gewijzigd door Fish op 05-11-2009 21:29 ]

[.oisyn]

.oisyn schreef op donderdag 05 november 2009 @ 21:13:
Mijn punt is juist dat het hier niet gaat om huisnummers, het gaat om afstand tussen postcodes. Die afstand is feitelijk afhankelijk van huisnummers, maar als die niet hebt, zit je sowieso met een afwijking. Dat maakt de afwijking die je door mijn berekening krijgt zo goed als verwaarloosbaar.

Ik heb het even berekend. Ik heb de extreme lat/lon coordinaten bepaald met Google maps en kom dus hierop.
De correcte afstandsformule geeft een afstand van 408.307km van zuidwest (x1y1 op de kaart) naar noordoost (x2y2). Simpelweg de stelling van pythagoras op breedte en hoogte, waarbij die breedte en hoogte zijn bepaald door de volle lengte en breedte te nemen in het midden van resp. longitude en latitude, geeft een afstand van 408.408km. Een afwijking van ongeveer 101 meter, zeg maar de lengte van een straat. En dat is dus in het vrijwel extreemste geval. Pythagoras lijkt me voor afstandsmeting tussen postcodes binnen Nederland dus Good Enough™

.edit: hmm wacht, ik maak een denkfout, zie volgende post van mij.

[ Voor 7% gewijzigd door .oisyn op 05-11-2009 22:39 ]

[JefSnare]

offtopic:
Werden dit soort onderwerpen nou maar behandeld op het MBO en HBO, dan had je een stuk meer aan de "lessen".
^{*Leert veel van GoT}

[Reddol]

Pythagoras gaat het dus worden!
En ik heb het al gezegd, voor mij maakt een afwijking van een paar 100 meter niet zoveel uit!
Ik zit meer met het probleem van het aantal postcodes dat gechecked moet worden:
Er staan zo'n 800 (groeiende) postcodes in de Database en de postcode waar je vanuit gaat is steeds anders.
Nu moet dus (volgens mij) met alle bovenstaande uitleg nog steeds elke keer ALLE postcodes gechecked worden, kost dit dan niet veel tijd? of zal dat maar enkele secondes duren? (Ik heb werkelijk waar geen idee hoe snel zo'n sql query is).

[Onbekend]

.oisyn schreef op donderdag 05 november 2009 @ 19:03:
Nederland is klein genoeg om het te benaderen als Euclidische geometrie, en daarbij de kromming van de aarde te negeren.

Dat valt nog vies tegen.
Voor een klein testproject had ik de afstanden nodig tussen een aantal verschillende grote Nederlandse steden.
Mijn berekende afstanden (de eenvoudige berekening) weken soms flink af t.o. de werkelijke afstanden, en dat had echt met de kromming van de Aarde te maken.

[Confusion]

Gebruik gewoon een tabel waarin je de 800*799 afstanden voorberekend hebt staan. Al zijn het er 1000*999: daar draait een beetje DB zijn hand niet voor om. Er staat weinig data in, dus echt veel geheugen neemt het ook niet in. Het is onnodig om die gegevens telkens voor iedere query opnieuw te berekenen.

[ Voor 68% gewijzigd door Confusion op 05-11-2009 22:48 ]

[.oisyn]

Wacht, ik maak een denkfout. Ik pak de diagonaal van Nederland, maar dat is allerminst met meest extreme geval. Door de kromming van de aarde en onze aard van latitude en longitude, komt het erop neer dat de "breedte" in het zuiden breder is dan de "breedte" in het noorden (de lengte is wel overal gelijk). Bij een diagonaal heft de afwijking in het noorden de afwijking in het zuiden juist zo goed als op. Bij een zo laag mogelijke latitude krijg je er een echte breedte uit van 255.502km, terwijl je volgens pythagoras dan de door mij bepaalde breedte zou krijgen: 263.889km. Oftewel, een afwijking van bijna 8.4km. In het noorden is het verschil iets minder groot: 272.119km, dus een afwijking van ~8.2km.

Dit is echter wel te corrigeren door als x-coordinaat volgens de door mij gestelde mapping te vermenigvuldigen met het y coordinaat én 8.3/311.705. Feitelijk vormen de coordinaten van de mapping dan geen rechthoek maar een trapezium (hij is in het noorden smaller dan in het zuiden)

[ Voor 23% gewijzigd door .oisyn op 05-11-2009 22:53 ]

[Voutloos]

Reddol schreef op donderdag 05 november 2009 @ 22:34:
Pythagoras gaat het dus worden!
En ik heb het al gezegd, voor mij maakt een afwijking van een paar 100 meter niet zoveel uit!
Ik zit meer met het probleem van het aantal postcodes dat gechecked moet worden:
Er staan zo'n 800 (groeiende) postcodes in de Database en de postcode waar je vanuit gaat is steeds anders.
Nu moet dus (volgens mij) met alle bovenstaande uitleg nog steeds elke keer ALLE postcodes gechecked worden, kost dit dan niet veel tijd? of zal dat maar enkele secondes duren? (Ik heb werkelijk waar geen idee hoe snel zo'n sql query is).

Enkele seconden? Zelfs al draai je je DB op de allereerste gameboy zou je je met zo'n tijd moeten schamen.

Confusion schreef op donderdag 05 november 2009 @ 22:44:
Gebruik gewoon een tabel waarin je de 800*799 afstanden voorberekend hebt staan. Al zijn het er 1000*999: daar draait een beetje DB zijn hand niet voor om. Er staat weinig data in, dus echt veel geheugen neemt het ook niet in. Het is onnodig om die gegevens telkens voor iedere query opnieuw te berekenen.

Het is onnodig om een gegevens van te voren berekenen als het on-the-flyu al verwaarloosbaar is.

[ Voor 25% gewijzigd door Voutloos op 05-11-2009 22:51 ]

[.oisyn]

Reddol schreef op donderdag 05 november 2009 @ 22:34:
Nu moet dus (volgens mij) met alle bovenstaande uitleg nog steeds elke keer ALLE postcodes gechecked worden, kost dit dan niet veel tijd? of zal dat maar enkele secondes duren? (Ik heb werkelijk waar geen idee hoe snel zo'n sql query is).

Niet als je een index hebt op lon en lat en je tevens filtert op het voorgestelde vierkant. Echter stellen een paar honderd records natuurlijk echt geen reet voor.

[HendrikN]

Verdiep je eens in MyGIS (de spatiale extensie van MySQL), daar zijn dit soort functies ingebakken.

[Confusion]

Voutloos schreef op donderdag 05 november 2009 @ 22:45:
Het is onnodig om een gegevens van te voren berekenen als het on-the-flyu al verwaarloosbaar is.

Reken maar dat een site als Funda die voorgegenereerde tabel heeft staan. Maakt je query nog simpeler ook.

[UltimateB]

In MySQL kan je ook afstandberekeningen doen. Je kan een punt opslaan als geometry en dan de distance laten berekenen. Hiermee kan je dus vanaf een bepaald punt heel gemakkelijk alle punten sorteren op distance of alles ophalen binnen de distance.

Door een index op de geometry kolom is dit ook nog eens vrij snel

http://dev.mysql.com/doc/...es.html#function_distance

Voor het geocoderen, als je gaat geocoderen via google houd er dan rekening mee dat postcodes lang niet altijd goed terug komen. Heb even geen voorbeeld bij de hand maar bij sommige postcodes vind hij bijvoorbeeld straten. Daarbij lijkt het erop dat het alleen op 4 cijfers achter de komma mogelijk is.

[Voutloos]

Confusion schreef op donderdag 05 november 2009 @ 22:53:
[...]

Reken maar dat een site als Funda die voorgegenereerde tabel heeft staan. Maakt je query nog simpeler ook.

Op mijn werk heb ik in dezelfde context ook zulke tabellen, maar bij de door ts genoemde aantallen (desnoods met groei het tienvoudige) is het denken over deze optimalisatie nog altijd zonde van de tijd.

[Reddol]

Is het trouwens wel toegestaan om mijn code hier te pasten en te kijken of ik in de goede richting zit?
Ik heb het namelijk (volgens mij) voor elkaar!
http://nl-noob.nl/google/testfunction.php
Postcode moet je ff intypen: 2986RA (daar zijn de overige op gebaseerd, dichtbij)
En de range kan je zelf bepalen. In de database staan 7 postcodes met long en lat

[Onbekend]

Hoe werkt dat dan?
Ik krijg allerlei vreemde resultaten. Een aantal met "Niet" en een paar met 0 km. Moeten die nog berekend worden?

[ Voor 106% gewijzigd door Onbekend op 05-11-2009 23:24 ]

[Megamind]

Ik heb zelf eens MySQL query die postcodes kan bereken.

Ik heb dan ook een postcode DB met Lat + Lon coordinaten erachter hangen.

code:

SELECT
    `dealerid`,
    `name`,
    `cleanname`,
    ROUND(
        (1.609344 *
            (3958 *
                PI() *
                SQRT(
                    POW(
                        (' . $Lat . ' - `zipcodes`.`lat`) , 2
                    )
                    +
                    COS(' . $Lat . ' / 57.29578 )
                    *
                    COS(`zipcodes`.`lat` / 57.29578 )
                    *
                    POW(
                        (' . $Lng . ' - `zipcodes`.`lng`) , 2
                    )
                ) / 180
            )
        )
    ) AS `distance`
FROM
    `dealers`
LEFT JOIN
    `zipcodes`
ON
    `zipcodes`.`zipcode` = `dealers`.`zipcode`
ORDER BY
    `distance` ASC
LIMIT
    0, 20

[Reddol]

Een aantal met Niet klopt, deze zijn buiten het 'bereik'
en met 0 kilometer ben ik nog niet tegen gekomen.. Wat vul je in?

p.s.: Site werkt even niet goed. Ik kom er niet uit. Kijk morgen avond weer verder.

[ Voor 25% gewijzigd door Reddol op 06-11-2009 00:17 ]

[Confusion]

Voutloos schreef op donderdag 05 november 2009 @ 23:00:
Op mijn werk heb ik in dezelfde context ook zulke tabellen, maar bij de door ts genoemde aantallen (desnoods met groei het tienvoudige) is het denken over deze optimalisatie nog altijd zonde van de tijd.

Ik bedoelde het ook eigenlijk in eerste instantie niets als performance optimalisatie, maar als een begrijpelijkheids optimalisatie. In plaats van

SQL:

select 
   zipcodes2.zipcode 
from 
   zipcodes join zipcodes as zipcodes2 on (zipcodes.id = zipcodes2.id) 
where 
   distance_calculation(zipcodes.x, zipcodes.y, zipcodes2.x, zipcodes2.y) < 10 
and 
   zipcodes.zipcode = ?

(vul naar wens longitude/lattitude oid in voor x/y) krijg je

SQL:

select 
   zipcode_distances.to 
from 
   zipcodes join zipcode_distances on (zipcodes.zipcode = zipcode_distances.from) 
where 
   zipcode_distances.distance < 10 
and 
   zipcodes.zipcode = ?

Maar nu ik het zo neerschrijf valt het verschil eigenlijk wel mee: ik had meer iets zoals in de post van Megamind voor ogen toen ik dat schreef.

[Voutloos]

Dat scheelt inderdaad niet veel/genoeg, zeker als je naar het totaalplaatje kijkt, want je maakt natuurlijk ergens anders het bijhouden van de tabel complexer.

[Cartman!]

Wat voor je DB wat sneller is als je niet alle combinaties wilt voorberekenen is gewoon van die cirkel een vierkant maken en een zooi WHERE's gebruiken, de exacte afstand kun je in php uitrekenen en de gevallen die wel in t vierkant maar buiten de cirkel vallen strip je er dan uit. Eventueel kun je nog met een vierkant binnenin de cirkel werken om alleen nog maar randgevallen in php te hoeven berekenen. In mijn applicatie was dat veel sneller dan die afstand in mysql te berekenen.

Hoe je die vierkanten kunt maken is gewoon basis wiskunde dus daar moet je wel uit komen denk ik.

[Enfer]

De afstand kun je ook in de database berekenen als je de coordinaten eenmaal hebt. Dat kan aan de hand v.d haversine formule: Wikipedia: Haversine formula

[Megamind]

Enfer schreef op vrijdag 06 november 2009 @ 13:33:
De afstand kun je ook in de database berekenen als je de coordinaten eenmaal hebt. Dat kan aan de hand v.d haversine formule: Wikipedia: Haversine formula

Welke precies hetzelfde is als mijn post

[Enfer]

Megamind schreef op vrijdag 06 november 2009 @ 13:35:
[...]

Welke precies hetzelfde is als mijn post

Alleen weet jij de precieze benaming even niet aan te geven, vandaar mijn aanvulling

BWT, mijn postgres variant:

SQL:

select (6371 * 2 * atan2( sqrt(  sin( radians($3-$1) /2 ) * sin( radians($3-$1) / 2 ) + cos( radians($1) ) * cos( radians($3) ) * 
sin( radians($4-$2) / 2 ) * sin( radians($4-$2) /2 ) ), sqrt( 1- sin( radians($3-$1) /2 ) *
 sin( radians($3-$1) / 2 ) + cos( radians($1) ) * cos( radians($3) ) * sin( radians($4-$2) / 2 ) * sin( radians($4-$2) /2 ) ) ) ) * 1000

[ Voor 44% gewijzigd door Enfer op 06-11-2009 13:40 ]

[Megamind]

Enfer schreef op vrijdag 06 november 2009 @ 13:37:
[...]

Alleen weet jij de precieze benaming even niet aan te geven, vandaar mijn aanvulling

Eerlijk gezegd had ik nog nooit van deze formule gehoord.

Ik heb namelijk navigatie op school gehad, maar daar praatte ze gewoon over grootcirkel of loxodroom navigatie

[Cartman!]

Die formule in je db op al je records kan als je niet zoveel records hebt wellicht goed werken, anders pak ik liever de methode die ik net beschreef.

[Reddol]

Megamind, jouw code aangepast en gebruikt.
En het werkt perfect! Is inderdaad goed snel.
Voor mij is het probleem opgelost, wat betreft jullie discussie weet ik het nog niet

[Woy]

Cartman! schreef op vrijdag 06 november 2009 @ 13:49:
Die formule in je db op al je records kan als je niet zoveel records hebt wellicht goed werken, anders pak ik liever de methode die ik net beschreef.

Je kan het natuurlijk beide opnemen in je query, waar je de complete formule in een UDF o.i.d. zet. De optimizer zal er dan (als het goed is) vanzelf voor kiezen om eerst alle records te fileren aan de hand van je eenvoudige vergelijkingen. Alleen voor de resulterende rows moet dan de complete formule uitgevoerd worden.

[Cartman!]

Dat is een mogelijkheid, echter check je dan een hoop teveel. Daarom gebruik ik nog een binnen-viekant om enkel twijfelgevallen maar echt te berekenen. Kwestie van benchmarken denk ik of dat nog nodig is.

[Woy]

Cartman! schreef op vrijdag 06 november 2009 @ 15:14:
Dat is een mogelijkheid, echter check je dan een hoop teveel. Daarom gebruik ik nog een binnen-viekant om enkel twijfelgevallen maar echt te berekenen. Kwestie van benchmarken denk ik of dat nog nodig is.

Hoezo check je dan teveel? Ik stel juist voor om zowel "Het vierkant" als de "Volledige Formule" in de query te verwerken. De volledige formule zal alleen uitgevoerd worden als een record door de vierkant test komt. Dat is in de veronderstelling dat een optimizer ziet dat de vierkant test veel eenvoudiger is dan de volledige formule.

[.oisyn]

Zoals ik al zei, met een index op je lat en lon is die vierkant test nog rap ook. Dus dat is gewoon
WHERE lat BETWEEN y1 AND y2 AND lon BETWEEN x1 AND x2 AND HaversineFormula(...)

[ Voor 37% gewijzigd door .oisyn op 06-11-2009 15:55 ]

[Cartman!]

Woy schreef op vrijdag 06 november 2009 @ 15:51:
[...]

Hoezo check je dan teveel? Ik stel juist voor om zowel "Het vierkant" als de "Volledige Formule" in de query te verwerken. De volledige formule zal alleen uitgevoerd worden als een record door de vierkant test komt. Dat is in de veronderstelling dat een optimizer ziet dat de vierkant test veel eenvoudiger is dan de volledige formule.

Alle records die ook binnen het binnenste vierkant vallen reken je nu ook uit via de database terwijl dat eigenlijk overbodig is want je weet al zeker dat die punten binnen de cirkel vallen. Wellicht komt mn idee met de 2 vierkanten niet goed door maar dat scheelt een hoop 'duur' rekenwerk voor je database.

[Megamind]

Je hebt wel een goed punt.

Ik heb namelijk voor mijn database alle postcodes op 4 cijfers en 1 letter afgeknipt. Zo werd de database ingekrimpt van ~300.000 naar 30.000 records. Met mijn query door 300k records zoeken is niet supertraag, maar het is ook niet flitsend snel.

[Reddol]

Nja, als het met 30.000 postcodes goed snel werkt op jouw manier zit ik wel goed
Ik heb er op dit moment +- 800, zal natuurlijk later uitgebreid worden, maar geen idee naar hoeveel.
Ik heb iig veel geleerd van jullie ! Thnx!

Nogmaals over het vierkant: Hoe kan je nu uitrekenen wat de straal is in aantal coordinaten?
Dus de BETWEEN y1 AND y2, of lees ik hier nu geheel overheen?

[Reptile209]

Als je wil werken met een vierkant dat tussen de vierkanten 'om' en 'in' de cirkel ligt, is het makkelijk uit te rekenen:
1. Cirkel met straal 10 km.
2. Buitenste vierkant is dan 20x20 km
3. De halve diagonaal van het binnenste vierkant is gelijk aan de straal van de cirkel: dia = 10 km
4. Pythagoras voor de halve zijde (a) van het binnenste vierkant: dia² = a² + a² = 2a², dus a = √(dia²/2) = (√0,5) x dia
5. Je binnenste vierkant meet dan 2a, ofwel 14,14 x 14,14 km.
6. Middelen van beide vierkanten geeft 17,07 x 17,07 km

Je gaat dan coordinaten zoeken tussen (x-17,07, y-17,07) en (x+17,07 en y+17,07).

[.oisyn]

Ik denk dat het Arjenlodder er meer om ging dat ie lat1, lon1, lat2 en lon2 moet berekenen voor het vierkant

lat1 en lat2 zijn trouwens simpel, de hoek in radialen is gewoon het aantal kilometers delen door de radius van de aarde (het handige van radialen is namelijk dat de lengte van de cirkelboog bij een hoek van x radialen en straal 1 gelijk is aan x). Om lon1 en lon2 te bepalen kun je het beste uitgaan van lat2 (degene die ten noorden ligt van je punt), want daar zijn de longitudinale cirkelbogen het kleinst. Feitelijk wil je gewoon weten wat de radius is van de cirkelboog op dat punt; dat is r∙cos(lat2), met r de straal van de aarde. De longitudinale hoek is dan aantal kilometers delen door de zojuist uitgerekende radius.

Oftewel, stel je wilt alle postcodes weten binnen straal x van punt p. De lengte en breedte van het omliggende vierkant zijn dan 2x. Dit geeft:
r = 6378.1 (straal van de aarde)
lat1 = p_lat - x/r
lat2 = p_lat + x/r
lon1 = p_lon - x/(r∙cos(lat2))
lon2 = p_lon + x/(r∙cos(lat2))

[ Voor 6% gewijzigd door .oisyn op 06-11-2009 17:53 ]

[dwilmer]

Over de snelheid: Ik ben nu ook zoiets aan het doen, maar dan in Javascript, met behulp van de Google API en Google Maps. Een test met 500 punten (random gegenereerd in PHP, later moet het uit de database komen), met custom markers, geeft alle markers weer in enkele seconden. Een DB-engine is veel sneller, staat op een server waarvan je mag aannemen dat-ie iets sneller is dan mijn laptopje, en hoeft niet alles in een Google Map te gooien. Kortom: dat gaat retesnel.

EDIT: @.oisyn: lengte- en breedtegraden zijn meestal in graden (Bijvoorbeeld Nederland: 52 NB, 5WL). Zoals jij ermee werkt staan ze in radialen, een verschil van een factor 3.141592.../180

[ Voor 16% gewijzigd door dwilmer op 06-11-2009 21:30 ]

[.oisyn]

Ik zeg toch ook dat ze in radialen zijn? Je wilt ze sowieso in radialen hebben voor de berekening van de afstand. De hoek in graden is meer iets voor de presentatielaag.

[Anoniem: 60780]

Onbekend schreef op donderdag 05 november 2009 @ 22:43:
[...]

Dat valt nog vies tegen.
Voor een klein testproject had ik de afstanden nodig tussen een aantal verschillende grote Nederlandse steden.
Mijn berekende afstanden (de eenvoudige berekening) weken soms flink af t.o. de werkelijke afstanden, en dat had echt met de kromming van de Aarde te maken.

Dat valt helemaal niet vies tegen, hoor

Rekensom:

Aannames

• De aarde heeft bolvorm (vanwege makkelijk rekenen).
• R = straal aarde = 6370 km
• booglengte van 400 km (ruwweg van Zuid-Limburg tot ergens in Groningen).

Te berekenen: koorde k behorende bij cirkelboog van 400 km op een cirkel met straal R.

De hoekafstand α van deze cirkelboog is 400 / 6370 rad.

1/2 k = R * sin(α/2) (sinusregel)

k = 2R * sin(α/2)

k = 399,934 km

M.a.w. als je de bolling van de aarde over een gebied als Nederland verwaarloost, ontstaat in het ergste geval een fout in afstanden van 66 m. Dus kun je in dit geval Nederland prima benaderen met euclidische geometrie!