[Java] Geografische afstand berekenen

[Radagast2005]

Hallo allemaal,

Ik heb een set X en Y coordinaten:
46340206 518757060
46347944 518743306

Je moet ze door 1000000 delen om de komma goed te zetten. Nu wil ik de hemelsbrede afstand tussen deze punten hebben. Op http://www.codeguru.com/C...eneral/article.php/c5115/ staat hier een uitleg over. Mijn code is dan:

Java:

public double distanceTo(Node n) {
        // procedure described on
        // http://www.codeguru.com/Cpp/Cpp/algorithms/general/article.php/c5115/
        double thisX = new Double(this.xCoord).doubleValue() / 10000000;
        double thisY = new Double(this.yCoord).doubleValue() / 10000000;
        double thatX = new Double(n.getXCoord()).doubleValue() / 10000000;
        double thatY = new Double(n.getYCoord()).doubleValue() / 10000000;

         // got this data from http://en.wikipedia.org/wiki/Earth_radius
         double earth_radius = new Double(6378).doubleValue();
        
 return (earth_radius)
         * Math.acos( Math.cos(90 - thatY) * Math.cos(90 - thisY)
         + Math.sin(90 - thatY) * Math.sin(90 - thisY)
         * Math.cos(thatX - thisX));
}

Dit geeft echter geen goed resultaat. Wie kan mij helpen?

[Tux]

http://nl.wikipedia.org/wiki/Afstand

hierin is R de straal van de bol, α de hoek in het equatoriale vlak en β de hoek loodrecht daarop, gerekend vanaf de equator.

[Icelus]

Math.cos en Math.sin verwachten een parameter in radialen.
Kijk 'ns of dat al een gewenst resultaat geeft.

[JKVA]

Ik heb de indruk dat er nog wel meer bij komt kijken, want hoe bepaal je welke kant je op meet? Dus linksom of rechtsom? Op het eerste gezicht leid ik dat niet af uit de berekening.

Bovendien, als het echt nauwkeurig moet zijn... De aarde is niet precies een bol. (wat zeg ik nu??? Gevaarlijke uitspraak )

[ Voor 11% gewijzigd door JKVA op 10-07-2006 17:32 ]

[Verwijderd]

JKVA schreef op maandag 10 juli 2006 @ 17:31:
Ik heb de indruk dat er nog wel meer bij komt kijken, want hoe bepaal je welke kant je op meet? Dus linksom of rechtsom? Op het eerste gezicht leid ik dat niet af uit de berekening.

Bovendien, als het echt nauwkeurig moet zijn... De aarde is niet precies een bol. (wat zeg ik nu??? Gevaarlijke uitspraak )

ligt er aan of je een rechtlijnige as gebruikt met 0.0 in het midden of 0.0 links onder.

[MissingDog]

JKVA schreef op maandag 10 juli 2006 @ 17:31:
Ik heb de indruk dat er nog wel meer bij komt kijken, want hoe bepaal je welke kant je op meet? Dus linksom of rechtsom? Op het eerste gezicht leid ik dat niet af uit de berekening.

Bovendien, als het echt nauwkeurig moet zijn... De aarde is niet precies een bol. (wat zeg ik nu??? Gevaarlijke uitspraak )

HK mode: De aarde is zo rond als een panne(n)koek

Wat betreft links/rechtsom is in principe dezelfde berekening, je moet alleen met de modulus van 360 graden rekening houden ivm de 0-meridiaan.

[Radagast2005]

Icelus schreef op maandag 10 juli 2006 @ 16:38:
Math.cos en Math.sin verwachten een parameter in radialen.
Kijk 'ns of dat al een gewenst resultaat geeft.

Ik heb de return veranderd naar:

Java:

 return (earth_radius)
         * Math.acos(Math.cos(Math.toRadians(90 - thatY)) * Math.cos(Math.toRadians(90 - thisY))
         + Math.sin(Math.toRadians(90 - thatY)) * Math.sin(Math.toRadians(90 - thisY))
         * Math.cos(Math.toRadians(thatX - thisX)));

En dat deed het hem. Bedankt!

[.oisyn]

Waarom in hemelsnaam werken met de Double class als je ook gewoon direct het double type kunt gebruiken

[JKVA]

Sowieso, gebruik BigDecimal.

[JKVA]

MissingDog schreef op maandag 10 juli 2006 @ 17:36:
[...]
HK mode: De aarde is zo rond als een panne(n)koek

Maar dan dus wederom geen perfect rond gebakken panne(n)koek.
http://en.wikipedia.org/wiki/Earth_radius

De straal is dus bij de evenaar groter.

Misschien is het gezeur, maar ik ken de context van de TS niet. Misschien is het van belang...

[Radagast2005]

.oisyn schreef op maandag 10 juli 2006 @ 18:10:
Waarom in hemelsnaam werken met de Double class als je ook gewoon direct het double type kunt gebruiken

De input variabelen zijn Strings. Die moet ik dus eerst naar doubles omzetten. Ik kan denk ik geen double xCoord = input geven waarbij input een String is.

JKVA schreef op maandag 10 juli 2006 @ 18:19:
Sowieso, gebruik BigDecimal.

Hmm ik zit de Java API te lezen en dat ziet er ook handig uit. Wat is qua finctionaliteit het verschil tussen een double en BigDecimal?
Al die sinusfuncties vragen om een double als input. BigDecimal en Double extenden allebei Number, dus volgens mij zijn ze niet geheel door elkaar te gebruiken?

JKVA schreef op maandag 10 juli 2006 @ 18:24:
[...]

Maar dan dus wederom geen perfect rond gebakken panne(n)koek.
http://en.wikipedia.org/wiki/Earth_radius

De straal is dus bij de evenaar groter.

Misschien is het gezeur, maar ik ken de context van de TS niet. Misschien is het van belang...

Ik ben een master-thesis aan het schrijven over kortste paden problemen. Ik heb een graaf van 1,3 miljoen punten waar ik de X,Y coordinaten van heb. Ik moet dus de onderliggende afstand weten. De punten beperken zich tot Nederland, dus dat de straal op sommige plekken verschilt doet niet veel ter zake. Op een gebied zo groot als Nederland ondervind je daar geen problemen van. Sterker nog, je kan je afvragen of de kromming van de aarde significant van invloed is, maar ik wil het goed doen .

[ Voor 35% gewijzigd door Radagast2005 op 10-07-2006 21:21 ]

[DroogKloot]

Radagast2005 schreef:
[...]

De input variabelen zijn Strings. Die moet ik dus eerst naar doubles omzetten. Ik kan denk ik geen double xCoord = input geven waarbij input een String is.

Java:

double d = Double.parseDouble("inputStr");

[Tux]

Radagast2005 schreef op maandag 10 juli 2006 @ 21:18:
Sterker nog, je kan je afvragen of de kromming van de aarde significant van invloed is, maar ik wil het goed doen .

Als een afstand over het aardoppervlak 200km bedraagt, zal de afwijking door de afstand in een rechte lijn te meten 8.19m zijn

code:

c^2 = a^2 + b^2 - 2 * a * b * cos y

200 - sqrt(2 * 6378^2 - 2 * 6378^2 * cos(360/((2 * pi * 6378)/200))

[Radagast2005]

DroogKloot schreef op maandag 10 juli 2006 @ 21:34:
[...]

Java:

double d = Double.parseDouble("inputStr");

Dank je, ik leer elke dag nieuwe Java dingen. vandaag gemiddeld wat meer .

Tux schreef op maandag 10 juli 2006 @ 21:50:
[...]


Als een afstand over het aardoppervlak 200km bedraagt, zal de afwijking door de afstand in een rechte lijn te meten 8.19m zijn

code:

c^2 = a^2 + b^2 - 2 * a * b * cos y

200 - sqrt(2 * 6378^2 - 2 * 6378^2 * cos(360/((2 * pi * 6378)/200))

Het gaat om het idee zullen we maar zeggen

[momania]

Radagast2005 schreef op maandag 10 juli 2006 @ 21:18:
[...]
Wat is qua finctionaliteit het verschil tussen een double en BigDecimal?

[google=java,double,BigDecimal]
lees en huiver.. vooral de double vs. BigDecimal zijn interessant voor je denk ik aangezien je hier aan het rekenen bent met doubles.

[.oisyn]

Radagast2005 schreef op maandag 10 juli 2006 @ 21:18:
[...]

De input variabelen zijn Strings.

Ah, dat kon ik natuurlijk niet zien (maar idd, gebruik Double.parseDouble() ), maar de radius van de aarde die je gebruikt is natuurlijk géén String

[Radagast2005]

.oisyn schreef op maandag 10 juli 2006 @ 22:43:
[...]

Ah, dat kon ik natuurlijk niet zien (maar idd, gebruik Double.parseDouble() ), maar de radius van de aarde die je gebruikt is natuurlijk géén String

Oh ja dat was idd wel een bullshit statement . Iets teveel gecopy paste

[Radagast2005]

momania schreef op maandag 10 juli 2006 @ 21:57:
[...]

[google=java,double,BigDecimal]
lees en huiver.. vooral de double vs. BigDecimal zijn interessant voor je denk ik aangezien je hier aan het rekenen bent met doubles.

Zoals ik eerder al poste vragen al die sin en cos functies doubles als input. Het lijkt me dan onhandig om eerst een BigDecimal aan te maken en deze meteen daarna te casten naar een double. Het enige directe rekenwerk met die doubles is het delen door 1000000 om het decimaalteken goed te zetten.

[Verwijderd]

In Nederland gebruiken we sowieso verschillende coördinaten-stelsel, misschien is het handig om te vermelden om welk stelsel het gaat. In Nederland is RD (het Rijksdriekhoek-stelsel) een veel gebruikte.

Het kan nogal schelen voor je afstandsberekening

[4VAlien]

Radagast2005 schreef op maandag 10 juli 2006 @ 21:18:
[...]

[...]

Ik ben een master-thesis aan het schrijven over kortste paden problemen. Ik heb een graaf van 1,3 miljoen punten waar ik de X,Y coordinaten van heb. Ik moet dus de onderliggende afstand weten. De punten beperken zich tot Nederland, dus dat de straal op sommige plekken verschilt doet niet veel ter zake. Op een gebied zo groot als Nederland ondervind je daar geen problemen van. Sterker nog, je kan je afvragen of de kromming van de aarde significant van invloed is, maar ik wil het goed doen .

Word het kortste paden probleem niet gedomineerd door het algoritme wat je daarvoor gebruikt (waardoor dit dus triviaal is)? Ik bedoel, dit probleem is niet zozeer een probleem van fysieke afstanden als wel de methode om de kortste route te bepalen.

[JKVA]

Radagast2005 schreef op maandag 10 juli 2006 @ 22:54:
[...]


Zoals ik eerder al poste vragen al die sin en cos functies doubles als input. Het lijkt me dan onhandig om eerst een BigDecimal aan te maken en deze meteen daarna te casten naar een double. Het enige directe rekenwerk met die doubles is het delen door 1000000 om het decimaalteken goed te zetten.

Voor precies rekenwerk moet je absoluut geen BigDecimals gebruiken. Die kan namelijk zelfs bij de kleinste en meest eenvoudige berekeningen al afwijkingen gaan vertonen. Ik merk dat de BigDecimal klasse geen cos en sin kent, maar hier staat een library daarvoor:
http://www.mathematik.hu-...h/HUMath/Numerik/Big.html

[-FoX-]

BigDecimal is voornamelijk handig voor financiële berekeningen e.d. te maken, maar als het echt op geografisch/wiskundig niveau moet gebeuren zou ik toch echt double's gebruiken.

[MicroWhale]

4VAlien schreef op maandag 10 juli 2006 @ 23:05:
[...]


Word het kortste paden probleem niet gedomineerd door het algoritme wat je daarvoor gebruikt (waardoor dit dus triviaal is)? Ik bedoel, dit probleem is niet zozeer een probleem van fysieke afstanden als wel de methode om de kortste route te bepalen.

inderdaad. dit zou het rekenwerk in grote mate kunnen inperken waardoor je je op het probleem zelf, het kortste paden probleem, kan storten. In feite werk je dus op een platte graaf, waarvan de afstanden onderling door middel van pythagoras berekend kunnen worden. Zeker als je werkt met het metrische rijksdriehoeksstelsel.

[Radagast2005]

4VAlien schreef op maandag 10 juli 2006 @ 23:05:
[...]


Word het kortste paden probleem niet gedomineerd door het algoritme wat je daarvoor gebruikt (waardoor dit dus triviaal is)? Ik bedoel, dit probleem is niet zozeer een probleem van fysieke afstanden als wel de methode om de kortste route te bepalen.

Logos schreef op dinsdag 11 juli 2006 @ 08:50:
[...]
inderdaad. dit zou het rekenwerk in grote mate kunnen inperken waardoor je je op het probleem zelf, het kortste paden probleem, kan storten. In feite werk je dus op een platte graaf, waarvan de afstanden onderling door middel van pythagoras berekend kunnen worden. Zeker als je werkt met het metrische rijksdriehoeksstelsel.

Inderdaad werk je eigenlijk op een platte graaf. Het leuke is dat ik data heb van Nederland, dus dan kan je het net wat echter maken. De algoritmes moeten wel in staat zijn de afstand tussen twee punten te kunnen zien of uitrekenen. Het maakt voor het probleem niet uit hoe je die afstand uitrekent, als de "fout" maar steeds overal hetzelfde blijft. Voor de aardigheid wil ik de data en de berekeningen erbij zo echt mogelijk houden.

Het was inderdaad een keuze om de afstand op runtime uit te rekenen. Als ik het vooraf uitreken krijg je allerlei problemen om te onthouden tussen welke 2 punten je de afstand hebt uitgerekend. Denken jullie dat op moderne computers de afstand uitrekenen zoals nu gedaan wordt significant bijdraagt aan de runtime?

[MicroWhale]

Het ligt er een beetje aan tussen hoeveel punten je deze berekeningen gaat doen.
Als het gaat om 10-100 berekeningen dan is het te verwaarlozen, maar ga je alle 1.3miljoen punten gebruiken, tsja... dan is het zeker de moeite waard om wat tijdswinst te pakken door alleen maar integer berekeningen te gebruiken.

Wat voor onderzoek is het precies? of kun je dat niet zeggen. (ik werk namelijk bij een cartografisch bedrijf en ik denk dat mijn collega's wel benieuwd zijn naar de uitslag van je onderzoek).

[Radagast2005]

Logos schreef op dinsdag 11 juli 2006 @ 15:05:
Het ligt er een beetje aan tussen hoeveel punten je deze berekeningen gaat doen.
Als het gaat om 10-100 berekeningen dan is het te verwaarlozen, maar ga je alle 1.3miljoen punten gebruiken, tsja... dan is het zeker de moeite waard om wat tijdswinst te pakken door alleen maar integer berekeningen te gebruiken.

Wat voor onderzoek is het precies? of kun je dat niet zeggen. (ik werk namelijk bij een cartografisch bedrijf en ik denk dat mijn collega's wel benieuwd zijn naar de uitslag van je onderzoek).

Ik schrijf een master thesis over datastructuren en heuristieken voor kortste pad problemen. Bij welk bedrijf werk je? Mail me anders .

Edit (toevoeging): je weet van te voren niet welke punten je tegen gaat komen, dus je weet niet hoeveel berekeningen je moet doen.

[ Voor 9% gewijzigd door Radagast2005 op 11-07-2006 16:37 ]

[MicroWhale]

ik zou je graag willen mailen, maar kan je adres nergens vinden.

[Radagast2005]

Logos schreef op woensdag 12 juli 2006 @ 11:24:
ik zou je graag willen mailen, maar kan je adres nergens vinden.

edwin apenstaartje student.eur.nl

[jvhaarst]

Hier staat wat code:
http://jehiah.com/archive...-searching-using-latlongs

[Hydra]

Verwijderd schreef op maandag 10 juli 2006 @ 23:01:
In Nederland gebruiken we sowieso verschillende coördinaten-stelsel, misschien is het handig om te vermelden om welk stelsel het gaat. In Nederland is RD (het Rijksdriekhoek-stelsel) een veel gebruikte.

Het kan nogal schelen voor je afstandsberekening

Nogal. Een pitfall waar ik ook ingevallen ben. Omdat de TS aangeeft dat hij moet delen zou het me niet verbazen dat dit hier ook het geval is. Het RD stelsel werkt met X/Y afstanden ten opzichte van parijs. De afstandsberekening is gewoon pythagoras (de afwijking van de bolling van de aarde is binnen nederland niet significant).

[Radagast2005]

Nah ik heb inmiddels besloten dat ik het rekenwerk van onderlinge afstanden ga doen om het moment dat ik de data inlees. Bij dit soort onderzoeken is vooral online berekentijd interessant, en data inlezen etc. kan offline.