Algoritmus gesucht: Mittelpunkt einer Landkarte mit vielen Punkten

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Algoritmus gesucht: Mittelpunkt einer Landkarte mit vielen Punkten

    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

  • #2
    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.
    video2mp3.de - Kostenlos Videos von verschiedenen Videoportalen in MP3 umwandeln

    Kommentar


    • #3
      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

      Kommentar


      • #4
        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)).

        Kommentar


        • #5
          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
          Zuletzt geändert von Chriss; 15.07.2007, 14:39.

          Kommentar


          • #6
            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.
            Die Regeln | rtfm | register_globals | strings | SQL-Injections | [COLOR=silver][[/COLOR][COLOR=royalblue]–[/COLOR][COLOR=silver]][/COLOR]

            Kommentar


            • #7
              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

              Kommentar


              • #8
                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

                Kommentar


                • #9
                  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

                  Kommentar


                  • #10
                    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

                    Kommentar


                    • #11
                      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

                      Kommentar


                      • #12
                        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

                        Kommentar


                        • #13
                          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

                          Kommentar


                          • #14
                            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

                            Kommentar

                            Lädt...
                            X