Algoritmus gesucht: Mittelpunkt einer Landkarte mit vielen Punkten

[Chriss]

Hallo Forum,

in meinem Internet-Forum können sich die Mitglieder auf einer google-Karte eintragen, d. h. ich habe geografische Koordinaten vorliegen. Nun möchte ich für ein Treffen der Mitglieder den theoretisch günstigsten Ort berechnen, d. h. wenn alle Mitglieder zum Treffen erscheinen würden, müsste die Summe aller Anfahrtswege, sowie der durchschnittliche Weg im Vergleich am niedrigsten sein.

Mir ist bewußt, dass die beiden genannten Kriterien alleine nicht genügen (bei Annahme von nur zwei Punkten, würde für jeder Punkt die Bedingungen erfüllen), d. h. es bedarf wohl noch einer weiteren Bedingung, um ein eindeutiges Ergebnis zu bekommen.

Wie könnte ein sinnvoller Algoritmus dazu aussehen? Mir geht es nur um den Lösungsansatz.

Danke für jeden Hinweis!

Gruß,
Chriss

[LoronorZorro]

Ich weiß nicht obs funktioniert, aber ich würde jetzt von jedem Punkt aus einen Kreis ziehen mit dem gleichen Radius, und den immer größer werden lassen und dann schauen wann alle Kreise einen Schnittmenge haben und in dem Bereich müsste dann etwa der günstigste Punkt sein, bzw. denke ist sehr komplex so eine Berechnung. Das nur so ne Idee von mir.

[Chriss]

Die Lösung mit den Kreisen erschließt sich mir nicht ganz und erscheint mir auch zu aufwändig.

Man muss noch bedenken, dass sich die Koordinaten aufgrund der Erdkrümmung nicht in einer Ebene befinden und somit der Anfahrtsweg (wobei ich selbstverständlich von der Luftlinien-Entfernung ausgehe) nicht die kürzeste Verbindung von zwei Punkten ist, d. h. der kürzeste Anfahrtsweg beschreibt eine Kurve. Diese Tatsache würde ich ggf. vernachlässigen um zumindet einen Nährungswert zu erhalten. Eine Funktion zur Entfernungsberechnung von zwei Punkten unter Berücksichtigung der Erdkrümmung steht aber natürlich zur Verfügung.

Also noch jemand eine Idee? Wahrscheinlich gehört die Frage mehr in eine Mathe-Forum... Im Prinzip bräuchte ich doch nur den Mittelpunkt aller Punkte berechnen. Wie geht das?

Gruß + Danke,
Chriss

[onemorenerd]

Die Erdkrümmung solltest du wirklich vernachlässigen. Sie macht längst nicht so viel aus wie die Kurven auf den Wegen zum Treffpunkt, welche du schließlich auch nicht mit einrechnest.

Die Berechnung: Du hast n Punkte (x1,y1) ... (xn,yn), die Positionen in einem metrischen Raum darstellen.
Der Mittelpunkt davon ist (MEDIAN(x1, ..., xn), MEDIAN(y1, ..., yn)).

[Chriss]

Original geschrieben von onemorenerd
Die Erdkrümmung solltest du wirklich vernachlässigen. Sie macht längst nicht so viel aus wie die Kurven auf den Wegen zum Treffpunkt, welche du schließlich auch nicht mit einrechnest.

Ok, aber ich habe Mitglieder in der ganzen Welt und da macht die Erdkrümmung wohl schon einiges aus.

Die Berechnung: Du hast n Punkte (x1,y1) ... (xn,yn), die Positionen in einem metrischen Raum darstellen.
Der Mittelpunkt davon ist (MEDIAN(x1, ..., xn), MEDIAN(y1, ..., yn)). [/B]

So einfach ist das? Werde ich mal probieren. Danke!

Gruß,
Chriss

[tontechniker]

Ok, aber ich habe Mitglieder in der ganzen Welt und da macht die Erdkrümmung wohl schon einiges aus.

Nein, voralledem wenn du sowieso nur auf eine ebenen Karte rechnest.

[Fiete]

Original geschrieben von Chriss

[median-tip]

So einfach ist das? Werde ich mal probieren. Danke!

Gruß,
Chriss [/B]

Alsooo...median kann ich mir nicht vorstellen. beispiel anhand nur einer Koordinate: median von 1,2,3,4,5 ist: 3.
median von 1,2,3,4,8 ist: 3.
Der median teilt lediglich eine datenreihe in 2 hälften und berücksichtigt keine art von gewichtung oder so...unpassend für dieses problem.

Fiete

[Fiete]

GMT: fitcircle

das drumherum ist sicher nicht trivial, aber die obige Lösung (Link) ist wohl die beste für das problem.


GMT Home Page

Fiete

[PHP-Desaster]

Original geschrieben von Fiete
Alsooo...median kann ich mir nicht vorstellen. beispiel anhand nur einer Koordinate: median von 1,2,3,4,5 ist: 3.
median von 1,2,3,4,8 ist: 3.
Der median teilt lediglich eine datenreihe in 2 hälften und berücksichtigt keine art von gewichtung oder so...unpassend für dieses problem.

Fiete

Aber der Median ist bei vielen Werten unanfälliger für Ausreißer!
Folgende Reihe:
1000mal der Wert 1000, 1mal 1000000.
Durchschnittswert: 1998,002
Median: 1000

[Fiete]

Original geschrieben von PHP-Desaster
Aber der Median ist bei vielen Werten unanfälliger für Ausreißer!
Folgende Reihe:
1000mal der Wert 1000, 1mal 1000000.
Durchschnittswert: 1998,002
Median: 1000

Ich propagiere nicht den Durchschnittswert. Die Summe der Anfahrtswege ist zu minimieren. Und da sind Ausreißer nicht zu ignorieren. es ist sogar noch schlimmer: wenn 10 mann an einem Ort wohnen (Punkthaufen), muss dieser Ort stärker ins Gewicht fallen...dass berücksichtigt die fitCircle-methode auch nicht.

Der zu minimierende Anfahrtsweg ist ja als Formel in Abhängigkeit von den Koordinaten des Treffpunktes gegeben und zu berechnen.
Ob man da das Minimum rechnerisch bestimmen kann (DGL?) oder per Butforce mit Raster alle Punkte "innerhalb" der Punktmenge kurzerhand ausrechnet..weiss ich einfach nicht. Bin da kein Mathematiker...befürchte aber, man kann sowas berechnen, nur ich kann es nicht (mehr).

Fiete

[Fiete]

Original geschrieben von Fiete
Ich propagiere nicht den Durchschnittswert. Die Summe der Anfahrtswege ist zu minimieren. Und da sind Ausreißer nicht zu ignorieren. es ist sogar noch schlimmer: wenn 10 mann an einem Ort wohnen (Punkthaufen), muss dieser Ort stärker ins Gewicht fallen...dass berücksichtigt die fitCircle-methode auch nicht.

Der zu minimierende Anfahrtsweg ist ja als Formel in Abhängigkeit von den Koordinaten des Treffpunktes gegeben und zu berechnen.
Ob man da das Minimum rechnerisch bestimmen kann (DGL?) oder per Butforce mit Raster alle Punkte "innerhalb" der Punktmenge kurzerhand ausrechnet..weiss ich einfach nicht. Bin da kein Mathematiker...befürchte aber, man kann sowas berechnen, nur ich kann es nicht (mehr).

Fiete

Jetzt hats angefangen mich zu wurmen:
Extrema eine Funktion mit 2 Unbekanten. Keine Nebenbedingung.
Partielle Ableitungen bilden und (beide) = 0 setzen -> liefert die Extrema der Funktion. Art des Kriteriums ist noch extra zu bestimmen. (Hesse-Kriterium)

So, Rest ist Fleissarbeit. ;-) Die ich für eine begrenzte Anzahl von Punkten mal machen werde - Freundeskreistreff bei jetzt 6 verschiedenen Wohnorten in Deutschland. Überschaubar...

Fiete

[uruloki]

Hat sich hier eigentlich was ergeben? Ich suche jetzt schon ziemlich lange nach einem Programm, dass eben diese Berechnung machen kann.

Wenn es da was gibt wäre ich überglücklich da mal reinschauen zu dürfen. Wenn nicht muss ich wohl weitersuchen oder nen Programm entwickeln

mfg
Uruloki

[Fiete]

Original geschrieben von uruloki
Hat sich hier eigentlich was ergeben? Ich suche jetzt schon ziemlich lange nach einem Programm, dass eben diese Berechnung machen kann.

Wenn es da was gibt wäre ich überglücklich da mal reinschauen zu dürfen. Wenn nicht muss ich wohl weitersuchen oder nen Programm entwickeln

mfg
Uruloki

Hi, ich habe es mit Excel und einem Raster über Deutschland mit 500m Seitenlänge gemacht und meinen geographischen Mittelpunkt berechnet (Summe aller Entfernungen zu dem Punkt minimal).

Und als der Punkt feststand, meinte der Großteil der Freunde, dass es ihnen wichtiger wäre, *Anfahrtszeiten* zu optimieren, denn Anfahrtswege...und sie 100km mehr Autobahn fahren würden als 2h Landstrasse....und damit war ich raus mit meiner schönen Rechnung..;_)

Fiete

[uruloki]

Blödköppe^^

wenn du die Datei noch findest hätte ich die gerne.

dann kann ich ja meine exceltabelle löschen. wollte auch sowas probieren *g*

mfg
uruloki