Hemelsbrede afstand tussen 2 objecten (lat/long) opslaan

[Freemann]

Ben bezig met het opslaan van objecten in een DB en wil ook de onderlingen afstanden tussen deze objecten opslaan.

Op het moment heb ik zeg 30 objecten in mijn DB staan en heb ik 2 tabellen:
- objects
- objects_distances

in objects_distances heb ik de kolommen:
- id
- s_id
- f_id
- distance

Id is autoincrement
s_id is het eerste object ID
f_id is het tweede object ID
distance is de afstand tussen de 2 objecten

opzet is:
objects.id <1 op veel> s_id|objects_distances|f_id <1 op veel> objects.id

Nu reken ik van elk object uit wat de afstand tussen alle andere objecten is.
Helaas zorgt deze methode voor een explosie van records (als ik meerdere records in ga voeren) daar 30 records al 30*30=900 afstanden opleveren.
bij 300*300 heb ik al 90.000 records en zodra ik 1.000 records in heb gevoerd ga ik over de 1.000.000 berekende afstanden.

Iemand een idee hoe ik dit anders op kan lossen?

[Verwijderd]

Gewoon realtime berekenen?

[UltimateB]

Nogal afhankelijk wat je met de gegevens wilt, en afhankelijk welke dbms je gebruikt. Sommigen zijn beter met spatial queries dan anderen.

[Verwijderd]

Overigens klopt je berekening niet helemaal.

De afstand tussen A en B is gelijk aan de afstand tussen B en A, als je het dus handig aanpakt is het juist weer de helft van het berekende aantal.

[Dreadly]

Verwijderd schreef op vrijdag 25 juni 2010 @ 20:16:
Gewoon realtime berekenen?

Dit. Iets met X coördinaten. Als je het verste (of het middelste) punt op 0 zet kun je de afstand vanaf de 0 gebruiken om het verschil tussen alle objecten te berekenen. Voorbeeld: Object 1: 40 - Object 2: 50 -> 50-40 = 10. Je kunt de Y coördinaten ook toevoegen als je dat gebruikt.

[voodooless]

Ik denk dat de belangrijke vraag is: wat wil je met die afstanden doen? En hoeveel objecten wil je in die DB opslaan? Als dat er niet zoveel zijn is die explosie van afstanden niet zo erg.

* voodooless moet er niet aan denken om dat op zijn werk te doen met 900.000.000 individuele posities in een db

[Voutloos]

Dreadly schreef op vrijdag 25 juni 2010 @ 20:28:
[...]
Dit. Iets met X coördinaten. Als je het verste (of het middelste) punt op 0 zet kun je de afstand vanaf de 0 gebruiken om het verschil tussen alle objecten te berekenen. Voorbeeld: Object 1: 40 - Object 2: 50 -> 50-40 = 10. Je kunt de Y coördinaten ook toevoegen als je dat gebruikt.

Dit werkt niet, je kan niet altijd via een derde punt dat exact tussen 2 punten inligt, en anders wordt het zoeken naar dat punt wel je bottleneck.

Gewoon ter plekke uitrekenen, en een beetje heuristiek gebruiken om wat resultaten te filteren of goedkoper te rekenen.

[Freemann]

het zou de bedoeling moeten zijn dat als men 1 record opvraagt, ook andere records worden getoond die in een straal van 10km liggen.

Dit zou betekenen dat ik voor iedere page-request deze berekening moet maken voor alle records.

Op dit moment weet ik niet precies hoeveel objecten er in de DB (die overigens MySQL is) komen, maar dit zullen er eerder 2000 worden dan 200. Wat dus zomaar richting de 2.000.000 kan gaan.

Op dit moment heb ik een script geschreven dat recursief is en eerst alle objecten ophaalt en dan per opgehaald record alle records in de tabel afloopt om hiervoor de afstand uit te rekenen en deze op te slaan.

[matthijsln]

Freemann schreef op vrijdag 25 juni 2010 @ 21:03:
het zou de bedoeling moeten zijn dat als men 1 record opvraagt, ook andere records worden getoond die in een straal van 10km liggen.

Dit zou betekenen dat ik voor iedere page-request deze berekening moet maken voor alle records.

Totaal onnodig om dit allemaal te berekenen. Hier zijn spatial indexes voor.

[PeaceNlove]

Probeer PostgreSQL DB met PostGIS uitbreiding. Die kan dat soort ruimtelijke queries met een spatial index wel voor je regelen.

[voodooless]

Het kan ook veel makkelijker door een simpele bounding box te gebruiken om een preselectie te maken. Hiervoor kun je normale indexen gebruiken.

Neem gewoon de aftand van 10 km in X en Y richting om het punt heen. Dan krijg je een min_lat, max_lat en min_long,max_long. Hierbinnen kun je dan van alle records de echte afstanden berekenen t.o.v het punt, en alles van meer dan 10 km laten afvallen. Dat kun je prima in SQL doen.

[ Voor 3% gewijzigd door voodooless op 25-06-2010 21:52 ]

[Freemann]

pfffff dacht ff een relatief eenvoudige vraag te stellen

Had nog nooit van Spatial indexen/query's gehoord, bounding box .....

ga dit ff laten bezinken en me inlezen in de de Spatials

Iemand nog suggesties voor leuk/interessant leesvoer?

[mithras]

In principe moet je met kromming van aarde rekening houden maar dat zijn zulke belachelijk ingewikkelde berekeningen voor een database dat je eenvoudiger met een bounding box kan werken.

Mocht de straal écht belangrijk zijn kan je altijd eerst alles binnen de bouning box ophalen en dat resultatenset alsnog een keertje simpel filteren.

[Verwijderd]

Daarnaast hoef je de afstand dus helemaal niet exact te weten. Je wil gewoon een sortering maken op basis van afstand met daarbij een globale max.

Hiervoor kun je dus idd een bounding box gebruiken om die globale max goed te krijgen, daarna kun je gewoon sorteren met een hele quick and dirty berekening. Immers gaat het alleen om dichterbij vs verderweg zonder dat de exacte afstand boeiend is.
Normaal is het voor dit soort toepassingen toch niet belangrijk dat het op de cm nauwkeurig is, dus een vrij globale match is prima.

[voodooless]

Klopt, een beetje Pythagoras doet wonderen

[Verwijderd]

voodooless schreef op vrijdag 25 juni 2010 @ 22:20:
Klopt, een beetje Pythagoras doet wonderen

Nee juist niet

Pythagoras is de wortel van de som van het verschil op de X-as tot de 2e macht en het verschil op de Y-as tot de 2e macht. Daar zitten 2 zaken in die niet handig zijn, namelijk worteltrekken en machtsverheffen (wat eigenlijk hetzelfde is maar het gaat ff om het idee).

Voor een sortering op basis van afstand heb je alleen het verschil op de X-as plus het verschil op de Y-as nodig. Dit geeft namelijk exact dezelfde volgorde, zonder deze lastigere berekeningen.

[Voutloos]

Nee, het kwadrateren maakt wel uit. Worteltrekken kan je wel achterwege laten voor enkel volgorde.

[Freemann]

heb het volgende gevonden en dat ben ik nu aan het toepassen:
http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

heb een index gemaakt, de functie toegevoegd en de geometry Point kolom loc toegevoegd.

Echter krijg ik nu een onverklaarbare foutmelding:

#1054 - Unknown column 'sdistances' in 'where clause'

op query

SQL:

SELECT orig.id, distance( orig.loc, dest.loc ) AS `sdistances`
FROM gobjectens orig, gobjectens dest
WHERE sdistances <10
ORDER BY sdistances
LIMIT 10 

zie pagina 29/29

heb de volgende site gebruikt om de kolom en index aan te maken:
http://maisonbisson.com/blog/post/12147/working-with-spatial-data-in-mysql/

Wie kan de bovenstaande foutmelding verklaren (zal vast wel weer iets heel simpels zijn maar kom er op deze tijd van de avond ff niet meer uit....)?

[P_de_B]

Freemann schreef op vrijdag 25 juni 2010 @ 23:31:
#1054 - Unknown column 'sdistances' in 'where clause'

Je kunt blijkbaar niet naar een alias refereren in de WHERE clausule.

Je moet dus gewoon WHERE distance( orig.loc, dest.loc ) < 10 doen.

[ Voor 61% gewijzigd door P_de_B op 25-06-2010 23:33 ]

[voodooless]

Los daarvan doet dit nog steeds een full table scan om uit te vinden wat het dichtste bij is. Ik zou hier toch echt van een bounding box gebruik maken om het zoeken sneller te maken. Daar gaat immers ook die hele presentatie over waar je naar linkt

[Kettingspanner]

Ik weet niet wat je gaat berekenen, maar als je langere afstanden gaat berekenen kan je dat niet doen met pythagoras. Ze moet grootcircel nemen. Dat is de namelijk de kortste afstand op een bolvormig voorwerp.

Afhankelijk waar je de coordinaten vandaan haalt, (WGS 84 of andere kaartprojecties) zal je misschien ook moeten corrigeren voor zaken als vergrotende breedte... Berekeningen op navigatie/plattegronden kan best ingewikkeld zijn.

[Verwijderd]

Voutloos schreef op vrijdag 25 juni 2010 @ 22:50:
Nee, het kwadrateren maakt wel uit. Worteltrekken kan je wel achterwege laten voor enkel volgorde.

Kun je een voorbeeld geven van input waarden waarbij dit inderdaad een ander resultaat geeft (qua volgorde), wel kwadrateren vs niet kwadrateren?

[Voutloos]

Stel: Tussen A en B zit enkel een verschil van 2 in 1 as, en tussen A en C een verschil van 1 in beide richtingen. Jij weet dan niet hoe je moet sorteren, terwijl er toch een fors verschil is.

[Skinkie]

Google maar op ST_length_spheroid

[giMoz]

Tis idd afhankelijk van de database die je gebruikt.
Oracle heeft standaard spatial in zich (vanaf versie 9)
MSSql heeft vanaf 2008 dat ook.
Progress heeft de PostGIS extensie.

deze drie kunnen dus afstanden berekenen incl rekening houden met krommingen e.d. (Mits spatial reference goed staat)
Als je echt lat/long op gaat slaan (dus GPS (wgs84) coordinaten) kan je daar geen pythagoras op los laten omdat het in graden of uren/minuten zijn, dan heb je wel een spatial db nodig.

mocht het alleen over data in nederland gaan kan je opslaan in RD coordinaten, dat zijn gewoon getallen met elk coordinaat een meter, en dat is zo'n relatief klein stelsel dat de kromming van de aarde er geen invloed op heeft, dus daarop kan je wel pythagorassen.

[mhaket]

Wat is overigens het probleem met 2.000.000 records? Dit is peanuts voor een DB.

[voodooless]

giMoz schreef op maandag 28 juni 2010 @ 08:33:
Als je echt lat/long op gaat slaan (dus GPS (wgs84) coordinaten) kan je daar geen pythagoras op los laten omdat het in graden of uren/minuten zijn, dan heb je wel een spatial db nodig.

Als het alleen maar gaat om volgorde, dan kun je dat prima doen. En zoals eerder gezegd: worteltrekken kun je achterwegen laten.

Wil je exacte afstanden weten, heb je natuurlijk nog steeds geen spatial DB nodig. Met een beetje rekenen kom je er ook, zoals al meerdere mensen en diverse voorbeelden hebben aangetoond.

mhaket schreef op maandag 28 juni 2010 @ 09:12:
Wat is overigens het probleem met 2.000.000 records? Dit is peanuts voor een DB.

Ik denk dat het grootste bezwaar hiervan zal zijn dat je die hele benden zal moeten bijhouden. Als je van je locaties een positie aanpast, moet je daarvoor alle afstanden die gerelateerd zijn aan deze positie aanpassen. Dat is een update van duizenden records. Op zich kan dat wel, maar zal een behoorlijke performance penalty zijn. Als je dit soort dingen niet vaak doet, hoeft dat natuurlijk geen deal breaker te zijn.

[ Voor 33% gewijzigd door voodooless op 28-06-2010 09:22 ]

[giMoz]

voodooless schreef op maandag 28 juni 2010 @ 09:19:
Als het alleen maar gaat om volgorde, dan kun je dat prima doen. En zoals eerder gezegd: worteltrekken kun je achterwegen laten.

Wil je exacte afstanden weten, heb je natuurlijk nog steeds geen spatial DB nodig. Met een beetje rekenen kom je er ook, zoals al meerdere mensen en diverse voorbeelden hebben aangetoond.

Als je lat/long op slaat (wgs84) dan kan je juist niet pythagorassen, om 2 redenen:
1. het is geen getal
2. het houdt rekening met de kromming van de aarde, en dan zou je bij berekeningen die wat dichter bij de noordpool of zuidpool liggen ongewenste resultaten krijgen. (en europa zou al dicht genoeg bij de pool liggen om niet meer goed uit te komen)

[HuHu]

P_de_B schreef op vrijdag 25 juni 2010 @ 23:33:
[...]

Je kunt blijkbaar niet naar een alias refereren in de WHERE clausule.

Je moet dus gewoon WHERE distance( orig.loc, dest.loc ) < 10 doen.

Daarvoor is de HAVING.

[voodooless]

giMoz schreef op maandag 28 juni 2010 @ 14:33:
Als je lat/long op slaat (wgs84) dan kan je juist niet pythagorassen, om 2 redenen:
1. het is geen getal

Hoezo geen getal: neem gewoon decimale graden (met een paar getallen achter de komma).

2. het houdt rekening met de kromming van de aarde, en dan zou je bij berekeningen die wat dichter bij de noordpool of zuidpool liggen ongewenste resultaten krijgen. (en europa zou al dicht genoeg bij de pool liggen om niet meer goed uit te komen)

Dat maakt niet uit als je alleen geïnteresseerd bent in de volgorde.

Het wordt wel anders als je afstanden van totaal verschillende punten wil vergelijken. We hebben het hier echter over de afstand t.o.v van een referentie punt.

[Janoz]

giMoz schreef op maandag 28 juni 2010 @ 14:33:
[...]


Als je lat/long op slaat (wgs84) dan kan je juist niet pythagorassen, om 2 redenen:
1. het is geen getal
2. het houdt rekening met de kromming van de aarde, en dan zou je bij berekeningen die wat dichter bij de noordpool of zuidpool liggen ongewenste resultaten krijgen. (en europa zou al dicht genoeg bij de pool liggen om niet meer goed uit te komen)

1 lat is een getal en long is ook een getal

2 een boundingbox (wat eigenlijk meer neerkomt op een trapezium achtige vorm) gaat eigenlijk pas echt problemen opleveren als je je daadwerkelijk op de pool bevindt. In alle gevallen is het een erg simpele manier om alvast een eerste filtering op je data te doen. Op de resultaten die je vervolgens terug krijgt kun je duurdere afstandsberekeningen loslaten.

[giMoz]

op een beetje afstand van de evenaar wordt die trapezium al heel erg schuin (dat gaat harder dan je denkt als je in europa zit)
Ook als je het in native spatial opslaat kan je er een spatial index op leggen die de eerste filtering vor je doet, dan hoef je je daar ook geen zorgen meer over te maken.

Maar alles valt of staat met het de vraag waar je zit, als je alleen maar NL data hebt zou ik voor RD coordinaten gaan, dan kan je gewoon lekker pythagorassen. En is het een stuk behapbaarder.

[Woy]

HuHu schreef op maandag 28 juni 2010 @ 14:38:
[...]

Daarvoor is de HAVING.

Volgens mij is distance geen aggregate functie, en dus moet je dat ook niet in de HAVING doen.

[BCC]

PeaceNlove schreef op vrijdag 25 juni 2010 @ 21:21:
Probeer PostgreSQL DB met PostGIS uitbreiding. Die kan dat soort ruimtelijke queries met een spatial index wel voor je regelen.

Dat is inderdaad echt perfect voor dit soort zaken. Kun je direct uit de databse SVGs tekenen.

[Voutloos]

In mysql mag het

A HAVING clause can refer to any column or alias named in a select_expr in the SELECT list or in outer subqueries, and to aggregate functions. However, the SQL standard requires that HAVING must reference only columns in the GROUP BY clause or columns used in aggregate functions. To accommodate both standard SQL and the MySQL-specific behavior of being able to refer columns in the SELECT list, MySQL 5.0.2 and up allows HAVING to refer to columns in the SELECT list, columns in the GROUP BY clause, columns in outer subqueries, and to aggregate functions.

[Woy]

Voutloos schreef op dinsdag 29 juni 2010 @ 09:15:
In mysql mag het

[...]

Maar dat zegt niet dat je het dan maar moet doen

[Verwijderd]

Je kan wel de afstand tussen twee punten opslaan, zelfs in twee componenten (noordwaards en oostwaards), maar geen relatieve latitude en longitude.

Even een gedachteexperimentje ter verduidelijking:
- Ik ga van noord-Afrika naar Mexico, ik ga dus niet noordelijk, maar wel westwaards. Stel nou dat ik daarmee 180 graden afleg.
- Ik ga van noord-Rusland naar Groenland, ik ga dus niet noordelijk, maar wel westwaards. Stel nou dat ik daarmee 180 graden afleg.

Je ziet, de relatieve latitude/logitude zijn hetzelfde in beide situaties, toch garandeer ik je dat de eerste situatie een veel langere afstand, wellicht zelfs tien keer zoveel afstand afleg als in de tweede.

Bedenk dus goed wat je feitelijk wilt, want relatieve lat/long is een redelijk inhoudsloos stukje data, je kan er alleen iets mee als je ook van ten minste één van de twee locaties de absolute lat/long alleen een absolute latitude is genoeg weet.

edit: de eerste situatie is zelfs maar 130 graden, voor 180 graden moet je in Thailand .i.p.v. Afrika zitten, dan is de afstand dus misschien wel 20 keer zo groot als situatie 2.

Op deze website staan formules om vanuit een set van twee latidutes en longitudes de afstand te berekenen:

Haversine formula:

R = earth’s radius (mean radius = 6,371km)
Δlat = lat2− lat1
Δlong = long2− long1
a = sin²(Δlat/2) + cos(lat1).cos(lat2).sin²(Δlong/2)
c = 2.atan2(√a, √(1−a))
d = R.c

Nou alleen nog in een query persen Dat moet in feite kunnen, als je SQL interface tenminste de gebruikte operators ondersteund (kwadraat, sinus, cosinus, arctangens2 en wortel).

Aan jou de keuze of je dit wel wilt doen in je query taal, of dat je op aanvraag dit in een scriptingtaal uitrekend tussen twee punten.

Je hoeft (als je dit in een tabel gaat opslaan) bij ieder nieuw punt maar 1 berekening met ieder ander punt uit te voeren, dus bij het toevoegen vna entry 7 zul je 6 distance entries moeten toevoegen, bij entry 300 299. Het loopt dus vrij hard op, maar voor een PC geen probleem (zolang het geen miljoenen zijn).

[ Voor 44% gewijzigd door Verwijderd op 29-06-2010 10:04 ]

[Laurent]

Er zijn ook wel hapklare SQL statements te vinden om berekeningen van long/lat te laten plaatsvinden, natuurlijk na het toepassen van de bounding box.

Pythagoras doen op long/lat coordinaten is niet tof. Hiervoor kun je beter een verkaarting gebruiken van de coordinaten, bijvooreeld de Lambert verkaarting (of de Nederlandse verkaarting, waarvan ik even niet op de naam kom). Hiervan zijn opnieuw hapklare versies te vinden op Wikipedia (zie vooral de referenties).

[UltimateB]

Als je Postgres (+Postgis) kan gebruiken, doe dat, die ondersteund alles native en kan ook geo indexes combineren met andere indexes, MySQL kan dit helaas niet, hier ga je geheid tegenaan lopen als je wat dieper doorgaat.

Als je dus alleen maar punten wilt gebruiken is het misschien zelfs aan te raden om in plaats van een geometry veld een lat en long veld te gebruiken, puur voor de snelheid, dan kan je het namelijk gemakkelijk met andere zaken zoals wellicht een status (online/offline) en categorieen combineren.

Maar toch maar even een voorbeeld met MySQL en geometry

Een tabel met een spatial index:

SQL:

CREATE TABLE `points` (
    `id` INT(10) NOT NULL DEFAULT '0',
    `geo` GEOMETRY NOT NULL,
    PRIMARY KEY (`id`),
    SPATIAL INDEX `geo` (`geo`(32))
)
ENGINE=MyISAM
ROW_FORMAT=DEFAULT

Records erin:

SQL:

INSERT INTO points (id, geo) VALUES ('', GEOMFROMTEXT("POINT(52.4 4.6)"))

Records eruit:

SQL:

SELECT *, ASTEXT(geo) AS wktvalue, X(geo) AS lat, Y(geo) AS lng
FROM points
WHERE MBRCONTAINS(GEOMFROMTEXT("LINESTRING(52 5, 54 4)"), geo) 
AND (6371 * ACOS(COS(RADIANS(52)) # 52 = lat
 * COS(RADIANS(X(geo))) 
 * COS(RADIANS(Y(geo)) - RADIANS(5)) # 5 = long
 + SIN(RADIANS(52)) # 52 = lat
 * SIN(RADIANS(X(geo))))) < 50 # ruwe afstand in km

Deze afstandberekening is niet extreen precies, maar ik neem aan dat dat niet echt nodig is. Haversine formula.

Als je dit wilt doen met lat / long dan kan zal je het geometry veld moeten vervangen en de bounding box dus iets anders moeten doen, maar daar zou je wel uit moeten komen.