Okay, ik heb nog even het een en ander nagelopen en uitgetest.
Er zijn een aantal eenvoudige functies waarmee je gegeven een lat- of lon-coordinaat (in graden) en een afstand een nieuw lat- of lon-coordinaat kunt berekenen.
De bron en de wiskundige onderbouwing zul je maar voor lief moeten nemen (weet niet meer waar ik deze vandaan heb gehaald en mijn
geodesische kennis is op zijn zachtst gezegd roestig :p), maar dit levert redelijk nauwkeurige resultaten, zoals we zullen zien.
Deze reactie is voornamelijk bedoeld om te laten zien hoe je het omvattende vierkant bouwt. Je zou voor de gein dit deel uit het WHERE-statement van je uiteindelijke query (tijdelijk, uiteraard) kunnen weglaten om te zien in hoeverre dit de performance beïnvloedt. Uiteraard hangt dit af van het aantal aanwezige locaties en hoe groot je je zoekstraal maakt, maar als ik uit kan gaan van de paar tests die ik heb gedaan (o.a. op mijn relatief trage Raspberry Pi) heeft zo'n bounding box een aanzienlijke (positieve) invloed op de querysnelheid.
Waar mogelijk zal ik proberen wat extra toelichting te geven die deels afgeleid zijn uit het schaarse commentaar wat ik ergens in een vaag ver verleden heb toegevoegd.
Allereerst wat definities, zoals ik ze begrijp. Kan er mogelijk helemaal naast zitten, but here goes :p.
De breedtegraad (latitude) geeft de noord-zuid positie aan. Deze ligt tussen 0 en 90 graden (positief of negatief, of met de toevoeging noorderbreedte (+) of zuiderbreedte (-)).
De lengtegraad (longitude) geeft de oost-west positie aan. Kan zowel positief als negatief of met oosterlengte (+) en westerlengte (-) en ligt tussen de 0 en 180 graden.
De functie voor het berekenen van een nieuwe breedtegraad, gegeven een breedtegraad $lat en een afstand in meters ($diff positief, richting het noorden of negatief, richting het zuiden) luidt als volgt:
<?php
function diffLat($lat, $diff) {
return $lat + ($diff / 111111);
}
?>
Die 111111 is een of andere constante die meestal wel opgaat, maar blijkbaar is 111319.5 beter voor hogere breedtegraden, dus wanneer je dichter bij de polen komt, maar 111111 volstaat meestal wel. Dit waarschijnlijk vanwege, of zijdelings gerelateerd aan het feit dat de wereld geen perfecte bol is, maar meer een soort van ellips of ei.
Als je dus een nieuwe breedtegraad wilt uitrekenen die 5 km noordelijker ligt, dan doe je dat dus als volgt:
<?php
$newLat = diffLat($currentLat, 5000);
?>
De functie voor het berekenen van een nieuwe lengtegraad, gegeven een huidige lengtegraad $lon, een huidige breedtegraad (want dit bepaalt mede de nieuwe lengtegraad) $lon, en een afstand in meters ($diff positief, richting het oosten, of negatief, richting het westen) luidt als volgt:
<?php
function diffLon($lat, $lon, $diff) {
$metresPerDegreeLon = cos(deg2rad($lat)) * 111111;
return $lon + $diff / $metresPerDegreeLon;
}
?>
Waarbij cos($lat) * 111111 blijkbaar overeen komt met 1 graad; ik vertrouw de persoon die dit zei volledig op zijn/haar woord :p.
Wanneer je een nieuwe lengtegraad wilt berekenen die 7,5 km naar het westen ligt, dan doe je dat dus als volgt:
<?php
$newLon = diffLon($currentLat, $currentLon, -7500);
?>
Makkelijk toch? :p
Dan zou je een test tabelletje kunnen bouwen waar je een (grote) hoeveelheid coordinaten ingooit.
CREATE TABLE `coordinates` (
`crd_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`crd_lat` float(9,6) NOT NULL,
`crd_lon` float(10,6) NOT NULL,
PRIMARY KEY (`crd_id`),
KEY `index_lat` (`crd_lat`),
KEY `index_lon` (`crd_lon`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Zoals eerder aangegeven ligt een breedtegraad tussen de 0 en 90 graden (max 2 cijfers), dit kan een positief of negatief getal zijn (sign, 1 cijfer). Vervolgens zul je een beslissing moeten nemen over de precisie. Voor dit voorbeeld, en waarschijnlijk ook voor de meeste zoekfunctionaliteit, volstaan 6 decimalen. Wanneer je een hogere precisie nodig hebt zul je je mogelijk ook moeten bedienen van andere, nauwkeurigere meetfuncties. De breedtegraad neemt dus maximaal 9 cijfers in, waarvan 6 decimalen. Op een soortgelijke manier bepaal je de ruimte voor de lengtegraad (1 sign, 3 cijfers 0-180 graden, 6 decimalen = 10 cijfers). Vervolgens maak je indexen aan op zowel de breedtegraad-kolom alsook de lengtegraad-kolom zodat je snel op kunt zoeken of iets in de breedte of de lengte in een bepaald interval ligt. Hier was het uiteindelijk per slot van rekening om te doen.
Voor deze test neem ik het Centraal Station te Eindhoven als uitgangspunt (51.4434401, 5.479096) en vul ik de coordinates-tabel met coordinaat-paren die ongeveer op een kilometer afstand van elkaar liggen. Hierbij maak ik dankbaar gebruik van de eerder genoemde functies:
<?php
// vul in <host>, <database> et cetera de juiste gegevens in, uiteraard
$dsn = 'mysql:host=<host>;dbname=<database>;charset=utf8';
$username = '<user>';
$password = '<password>';
try {
$db = new PDO($dsn, $username, $password, array(
PDO::ATTR_ERRMODE => PDO::ERRMODE_EXCEPTION,
PDO::ATTR_EMULATE_PREPARES => true,
PDO::MYSQL_ATTR_USE_BUFFERED_QUERY => true,
PDO::ATTR_DEFAULT_FETCH_MODE => PDO::FETCH_ASSOC,
));
} catch (Exception $e) {
echo $e->getMessage();
exit;
}
try {
$db->query('TRUNCATE coordinates;'); // maak de tabel leeg
$st = $db->prepare('INSERT INTO coordinates (crd_lat, crd_lon) VALUES (?, ?)'); // creeer prepared statement
// vul de tabel
$db->beginTransaction();
for ($x = -99; $x < 100; $x++) {
for ($y = -99; $y < 100; $y++) {
$lat = diffLat(51.4434401, $y * 1000);
$lon = diffLon(51.4434401, 5.479096, $x * 1000);
$st->execute(array($lat, $lon));
}
}
$db->commit();
} catch (Exception $e) {
echo $e->getMessage();
exit;
}
?>[end]
(en ja, ik heb eindelijk een nut gevonden voor prepared statements :p)
Nu wordt het tijd om een bounding box te gaan bouwen en wat dingen te gaan testen.
Stel dat het Centraal Station tevens het uitgangspunt is voor jouw zoekopdracht, en dat je in een straal van ~12 kilometer wilt zoeken.
Hiervoor bouwen we dus eerst het vierkant om dit middelpunt heen. Hiertoe pakken we de linker onderhoek van het vierkant, en de rechter bovenhoek. Deze bevatten respectievelijk de laagste en hoogste coordinatenparen, zodat je hier makkelijk een BETWEEN op kunt toepassen. Hierbij gaan we gemakshalve uit van gevalideerde gegevens, om het verhaal niet onnodig complexer te maken.
<?php
$searchRadius = 12000; // metres
$searchLat = 51.443440;
$searchLon = 5.479096;
$precision = 6; // decimals
// bottom left Y
$y1 = round(diffLat($searchLat, -$searchRadius), $precision);
// bottom left X
$x1 = round(diffLon($searchLat, $searchLon, -$searchRadius), $precision);
// top right Y
$y2 = round(diffLat($searchLat, $searchRadius), $precision);
// top right X
$x2 = round(diffLon($searchLat, $searchLon, $searchRadius), $precision);
?>
Meestal is het geen goede gewoonte om tussentijds af te ronden, maar omdat je deze gegevens aan de database gaat voeren is dit wel verstandig om in dezelfde precisie te werken, anders begint MySQL te emmeren over truncated values in een heleboel warnings :p.
De eerste query met enkel het vierkant wordt dan dus zoiets:
<?php
$query =
"SELECT crd_id, crd_lat, crd_lon
FROM coordinates
WHERE (crd_lat BETWEEN ".$y1." AND ".$y2.")
AND (crd_lon BETWEEN ".$x1." AND ".$x2.")";
?>
Dit levert je als het goed is 576 resultaten op in enkele miliseconden.
Dan zou je de functie uit de andere thread over kunnen nemen. Deze heb ik voor mijn gebruik een beetje gepimpt zodat 'ie lekker(der) werkt met deze informatie, heb ook gelijk wat spellingsfouten eruit gehaald :p.
DROP FUNCTION IF EXISTS GetDistance;
DELIMITER $$
CREATE FUNCTION GetDistance(orgLat FLOAT(9,6), orgLong FLOAT(10,6), destLat FLOAT(9,6), destLong FLOAT(10,6)) RETURNS FLOAT DETERMINISTIC
BEGIN
RETURN 6371 *
acos(cos(radians(orgLat) ) *
cos(radians(destLat)) *
cos(radians(destLong) - radians(orgLong)) + sin(radians(orgLat))
* sin(radians(destLat)));
END$$
DELIMITER ;
Vervolgens kun je de query uitbreiden met een berekening van de straal binnen het aangepaste zoekgebied:
<?php
$query =
"SELECT crd_id, crd_lat, crd_lon, GetDistance(".$searchLat.", ".$searchLon.", crd_lat, crd_lon) AS distance
FROM coordinates
WHERE (crd_lat BETWEEN ".$y1." AND ".$y2.")
AND (crd_lon BETWEEN ".$x1." AND ".$x2.")
AND GetDistance(".$searchLat.", ".$searchLon.", crd_lat, crd_lon) < ".($searchRadius/1000);
?>
NB GetDistance werkt met kilometers, dit zou je zelf nog aan kunnen passen.
Dit levert je als het goed is 437 records op, en de query zou nog steeds supersnel moeten zijn.
Dat was het zo'n beetje, van begin tot eind.
Je gaf aan dat er geen kaartmogelijkheid wordt gevraagd, maar als je dit combineert met bijvoorbeeld Google Maps, dan kun je dit alles visueel maken, hiermee kun je makkelijker en intuitiever testen.
En het levert ook leuke plaatjes op.
