[sql/wiskunde] punten in cirkels

[Zynth]

Ik zit met een SQL/wiskunde probleempje.
Ik heb een tabel met "punten"; dus een tabel met alleen maar x- en y-waarden.
Het probleem waar ik nu mee zit is het bepalen van alle punten die binnen een straal van x van een bepaalt punt bevinden.
Bijvoorbeeld; ik wil van het punt 10,10 weten welke punten uit de database zich binnen een straal van 5 van dat punt bevinden.

Een mogelijke minder mooie oplossing is het berekenen van 8 punten op de cirkel met een straal van 5, en dan in een sql-query zetten: "alle waarden die kleiner zijn dan dit punt, kleiner zijn dan dit punt,....,groter zijn dan dat punt, grot......".
Dat is een mogelijke oplossing, maar niet echt een mooie.
Is er eigenlijk een perfecte oplossing?

[Woy]

Je kan in een query toch ook gewoon de afstand bereken. Stel je hebt p1 met x1 = 10 en y1 = 10 met een straal s1

dan doe je

SQL:

select x2, y2
from punten
where ( (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) ) < s1 * s1

Ik doe hier even de straal in het kwadraat omdat je anders nog een sqrt moet nemen en dat is zwaarder als een vermenigvuldiging.

De x1 en y1 moet je dan natuurlijk in je query invullen met een parameter o.i.d.

[ Voor 24% gewijzigd door Woy op 13-12-2005 17:14 . Reden: wat gelul over abs verwijderd ]

[.oisyn]

rwb schreef op dinsdag 13 december 2005 @ 17:10:
Ik doe hier even de straal in het kwadraat omdat je anders nog een sqrt moet nemen en dat is zwaarder als een vermenigvuldiging.

True, maar ik denk dat het in een SQL statement bijzonder weinig uit zal maken, daar memory- en disk access de grootste bottleneck is

Overigens vraag ik me af in hoeverre de database hier gebruik kan maken van indices. Als je een database hebt die geometrische objecten en queries support waarschijnlijk wel, anders zou je evt. ook nog kunnen controleren of de x binnen x1-straal en x1+straal ligt, en hetzelfde voor de y. Het RDBMS zal dan dmv de indices op x en y heel snel alle punten binnen dit vierkant kunnen pakken, en voor al die punten afzonderlijk nog eens testen of ze wel in de cirkel liggen.

[ Voor 41% gewijzigd door .oisyn op 13-12-2005 17:31 ]

[DaCoTa]

rwb schreef op dinsdag 13 december 2005 @ 17:10:
Je kan in een query toch ook gewoon de afstand bereken. Stel je hebt p1 met x1 = 10 en y1 = 10 met een straal s1

dan doe je

SQL:

select x2, y2
from punten
where ( (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) ) < s1 * s1

Ik doe hier even de straal in het kwadraat omdat je anders nog een sqrt moet nemen en dat is zwaarder als een vermenigvuldiging.

De x1 en y1 moet je dan natuurlijk in je query invullen met een parameter o.i.d.

Als je slim wilt optimalizeren, kun je er nog een where clause voor zetten met een bounding box algoritme. Die kan waarschijnlijk de selectieset al verkleinen waarbij wel gebruik van indices gemaakt kan worden.

edit:
Spuit 11 na slechts 10 minuten...

[ Voor 4% gewijzigd door DaCoTa op 13-12-2005 17:38 ]

[Skaah]

Kijk in je SQL eerst of het binnen het vierkant rondom je punt past; en daarna bereken je of het binnen de cirkel past.

[Woy]

.oisyn schreef op dinsdag 13 december 2005 @ 17:27:
[...]


True, maar ik denk dat het in een SQL statement bijzonder weinig uit zal maken, daar memory- en disk access de grootste bottleneck is

True, maar aangezien het niet complexer is om het zo te doen zie ik ook geen reden om wel een sqrt te nemen

Overigens vraag ik me af in hoeverre de database hier gebruik kan maken van indices. Als je een database hebt die geometrische objecten en queries support waarschijnlijk wel, anders zou je evt. ook nog kunnen controleren of de x binnen x1-straal en x1+straal ligt, en hetzelfde voor de y. Het RDBMS zal dan dmv de indices op x en y heel snel alle punten binnen dit vierkant kunnen pakken, en voor al die punten afzonderlijk nog eens testen of ze wel in de cirkel liggen.

Als je een grote puntenset hebt en je performance wordt een probleem is dat denk idd de beste oplossing. In de meeste gevallen is het niet echt handig om veel rekenwerk in een query op te nemen.

[Werkbouwtuig]

Wiskundig gezien zijn de vergelijking voor een cirkel met een middelpunt op (10,10) en een straal 5

x=10+r*cos(phi)
y=10+r*sin(phi)

waarbij phi van 0 tot 2 pi loopt.

Hoe dat in SQL moet, mag je zelf even verder kijken, dat wee ik zo snel niet!

[.oisyn]

Wiskundigen zullen een cirkel over het algemeen definieren als x²+y² = r², met r de straal en x en y de coordinaten relatief aan de oorsprong van de cirkel. Dat rekent namelijk wat makkelijker dan "ingewikkelde" trigonometrische functies.

[Woy]

Werkbouwtuig schreef op dinsdag 13 december 2005 @ 17:53:
Wiskundig gezien zijn de vergelijking voor een cirkel met een middelpunt op (10,10) en een straal 5

x=10+r*cos(phi)
y=10+r*sin(phi)

waarbij phi van 0 tot 2 pi loopt.

Hoe dat in SQL moet, mag je zelf even verder kijken, dat wee ik zo snel niet!

Zo kan je inderdaad alle punten op de buitenrand van de cirkel definieren. Dat is hier echter niet nodig aangezien je alleen wilt controleren of de afstand tussen 2 punten groter is als de straal van de cirkel. En dat kan zoals al eerder aangegeven is gewoon met x^2 + y^2 = r^2

[Verwijderd]

dus r = Wortel(x² + y²)

en dan moet r kleiner zijn dan 5 lijk me,,

correct me if i'm wrong ( zo leer k ook weer wat )

[Soultaker]

Skaah schreef op dinsdag 13 december 2005 @ 17:45:
Kijk in je SQL eerst of het binnen het vierkant rondom je punt past; en daarna bereken je of het binnen de cirkel past.

Dit lijkt mij ook het handigst; dan heb je nog eens wat aan eventuele indices op de coördinaten.

[Woy]

Verwijderd schreef op dinsdag 13 december 2005 @ 18:09:
dus r = Wortel(x² + y²)
en dan moet r kleiner zijn dan 5 lijk me,,
correct me if i'm wrong ( zo leer k ook weer wat )

Dat klopt maar het is dus handiger om i.p.v
r = wortel( x_diff² + y_diff² )
r² = x_diff² + y_diff²
te controleren aangezien je dan geen wortel hoeft te trekken.

Verder is het zoals al gezegd gewoon het handigst om de punten in een vierkant te selecteren aangezien je dan het aantal punten wel sterk reduceert maar wel gewoon gebruik kan blijven maken van de kracht van een RDBMS. De exacte berekening kun je dan gewoon in je applicatie doen aangezien die veel sneller is met rekeken.

[Soultaker]

Oh, je RDBMS kan dat zelf ook wel, maar het ging er meer om dat als je 'WHERE x*x+y*y<r*r' schrijft de RDBMS waarschijnlijk niet weet hoe 'ie z'n index moet gebruiken en maar alles matcht.

Je kunt dan waarschijnlijk beter een iets ingewikkeldere WHERE-clause schrijven: 'WHERE x>-r && x<r && y>-r && y<r && x*x+y*y<r*r'. Als 'r' een constante is zal nu zeker een index op x en/of y gebruikt worden.

[Zynth]

Hartelijk bedankt allemaal voor de, meestal, vrij intelligente antwoorden
Hier kan ik een boel mee denk ik. Zoals je misschien al hebt geraden is het uiteindelijk bedoelt om los te laten op GPS coordinaten.
Als je 2 gps-coordinaten hebt, kan je daar met een rekensom de afstand tussen uitrekenen.
http://home.planet.nl/~hklein/afstand/cairo.htm

dit lijkt op zich heel simpel te vertalen te zijn naar jullie formule:
als je een gps-locatie weet, en een straal in kilometers, dan weet je ook dus de maximale en minimale gps-coordinaten en de straal in gps-eenheden, en kan je dus de formule gebruiken.
Het probleem is dat de x en y as qua gps niet dezelfde schaalverdeling hebben
Een straal werkt dus niet, want bijvoorbeeld 10 gps-eenheden naar rechts is niet evenveel kilometers als 10 gps-eenheden naar boven...

[jvhaarst]

Heb je al eens naar dit verhaal gekeken ?
De voorbeelden in dat verhaal sluiten hopelijk aan bij wat je wil, en anders heb je een goede zoekterm voor Google

[MSalters]

GPS coordinaten zijn toch geen orthogonale coordinaten? Dat maakt de cirkel een heel stuk lastiger, long/lat is geen x/y, en dat is meer dan een schaalverdelingsprobleem.

[Confusion]

MSalters schreef op dinsdag 13 december 2005 @ 21:22:
GPS coordinaten zijn toch geen orthogonale coordinaten?

Dat ligt eraan hoe je ze uitdrukt. Bolcoordinaten zijn volgens mij wel orthogonaal (maar ik heb nu even geen zin om dat te controleren ). Maargoed, ik weet niet of je handige algoritmen voor data in die coordinaten kan schrijven en hoe handig dat combineert met een cirkel op de bol waarbinnen je wilt zoeken.

[phYzar]

Zynth schreef op dinsdag 13 december 2005 @ 20:18:
dit lijkt op zich heel simpel te vertalen te zijn naar jullie formule:
als je een gps-locatie weet, en een straal in kilometers, dan weet je ook dus de maximale en minimale gps-coordinaten en de straal in gps-eenheden, en kan je dus de formule gebruiken.
Het probleem is dat de x en y as qua gps niet dezelfde schaalverdeling hebben
Een straal werkt dus niet, want bijvoorbeeld 10 gps-eenheden naar rechts is niet evenveel kilometers als 10 gps-eenheden naar boven...

Als het alleen om locaties in Nederland gaat zou je je coördinaten kunnen omrekenen/uitdrukken in rijksdriehoeksnet. Dat is een coördinatenstelsel met correctie (voor Nederland) op het standaard wgs84 formaat en werkt met een x & y in meters...

[Woy]

Soultaker schreef op dinsdag 13 december 2005 @ 19:30:
Oh, je RDBMS kan dat zelf ook wel, maar het ging er meer om dat als je 'WHERE x*x+y*y<r*r' schrijft de RDBMS waarschijnlijk niet weet hoe 'ie z'n index moet gebruiken en maar alles matcht.

Dat is precies wat ik bedoelde met de kracht van een RDMBS. In mijn eerste post gaf ik idd al een simpele oplossing voor het probleem. Alleen dat is zeker niet de meest optimale

Maar ook met GPS kan je toch wel redlijk makkelijk de maximale waarden bepalen om een select te doen op je Database. Dat je daar alsnog te veel records van terug krijgt is helemaal geen probleem omdat je toch wel het grootste deel van de punten er meteen uit filterd. De exacte berekening kan je dan gewoon in je applicatie doen. Zolang je geen extreem grote load/database krijgt is het denk best werkbaar

[ Voor 8% gewijzigd door Woy op 14-12-2005 11:05 ]

[Verwijderd]

phYzar schreef op dinsdag 13 december 2005 @ 23:51:
[...]

Als het alleen om locaties in Nederland gaat zou je je coördinaten kunnen omrekenen/uitdrukken in rijksdriehoeksnet. Dat is een coördinatenstelsel met correctie (voor Nederland) op het standaard wgs84 formaat en werkt met een x & y in meters...

Iets algemener: Wgs84 is een vorm van UMT coordinaten waarmee je de aarde "plat" maakt. Welke variant je het beste kan gebruiken is dan afhankelijk van welk deel van de aarde je interesseert maar fundamenteel is de berekening overal hetzelfde.