php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Scripts > BRAINSTORMING PHP/SQL/HTML/JS/CSS
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


BRAINSTORMING PHP/SQL/HTML/JS/CSS Ihr habt eine Idee, aber keinen genauen Ansatz? Diskutiert mit anderen Usern des Forums über eure Gedankengänge um evtl. hilfreiche Ideen zu bekommen!
Normale Fragen bitte weiterhin in die entsprechenden Foren!

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 15-07-2007, 00:58
Chriss
 Registrierter Benutzer
Links : Onlinestatus : Chriss ist offline
Registriert seit: Oct 2001
Beiträge: 89
Chriss ist zur Zeit noch ein unbeschriebenes Blatt
Standard 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
Mit Zitat antworten
  #2 (permalink)  
Alt 15-07-2007, 03:43
LoronorZorro
 Registrierter Benutzer
Links : Onlinestatus : LoronorZorro ist offline
Registriert seit: Aug 2005
Ort: Aschaffenburg
Beiträge: 90
LoronorZorro ist zur Zeit noch ein unbeschriebenes Blatt
LoronorZorro eine Nachricht über ICQ schicken
Standard

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.
Mit Zitat antworten
  #3 (permalink)  
Alt 15-07-2007, 12:07
Chriss
 Registrierter Benutzer
Links : Onlinestatus : Chriss ist offline
Registriert seit: Oct 2001
Beiträge: 89
Chriss ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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
Mit Zitat antworten
  #4 (permalink)  
Alt 15-07-2007, 13:04
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

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)).
Mit Zitat antworten
  #5 (permalink)  
Alt 15-07-2007, 13:31
Chriss
 Registrierter Benutzer
Links : Onlinestatus : Chriss ist offline
Registriert seit: Oct 2001
Beiträge: 89
Chriss ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Zitat:
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.

Zitat:
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

Geändert von Chriss (15-07-2007 um 14:39 Uhr)
Mit Zitat antworten
  #6 (permalink)  
Alt 15-07-2007, 14:17
tontechniker
 PHP Senior
Links : Onlinestatus : tontechniker ist offline
Registriert seit: Jul 2005
Beiträge: 1.972
tontechniker ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Zitat:
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 | []
Mit Zitat antworten
  #7 (permalink)  
Alt 17-10-2007, 01:27
Fiete
 Newbie
Links : Onlinestatus : Fiete ist offline
Registriert seit: Oct 2007
Ort: Berlin
Beiträge: 5
Fiete ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Zitat:
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
Mit Zitat antworten
  #8 (permalink)  
Alt 17-10-2007, 01:36
Fiete
 Newbie
Links : Onlinestatus : Fiete ist offline
Registriert seit: Oct 2007
Ort: Berlin
Beiträge: 5
Fiete ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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
Mit Zitat antworten
  #9 (permalink)  
Alt 17-10-2007, 09:22
PHP-Desaster
 PHP Expert
Links : Onlinestatus : PHP-Desaster ist offline
Registriert seit: Mar 2006
Beiträge: 3.105
PHP-Desaster befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
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
Mit Zitat antworten
  #10 (permalink)  
Alt 17-10-2007, 14:43
Fiete
 Newbie
Links : Onlinestatus : Fiete ist offline
Registriert seit: Oct 2007
Ort: Berlin
Beiträge: 5
Fiete ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Zitat:
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
Mit Zitat antworten
  #11 (permalink)  
Alt 17-10-2007, 15:10
Fiete
 Newbie
Links : Onlinestatus : Fiete ist offline
Registriert seit: Oct 2007
Ort: Berlin
Beiträge: 5
Fiete ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Zitat:
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
Mit Zitat antworten
  #12 (permalink)  
Alt 21-04-2008, 08:35
uruloki
 Newbie
Links : Onlinestatus : uruloki ist offline
Registriert seit: Apr 2008
Beiträge: 2
uruloki ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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
Mit Zitat antworten
  #13 (permalink)  
Alt 21-04-2008, 09:07
Fiete
 Newbie
Links : Onlinestatus : Fiete ist offline
Registriert seit: Oct 2007
Ort: Berlin
Beiträge: 5
Fiete ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Zitat:
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
Mit Zitat antworten
  #14 (permalink)  
Alt 21-04-2008, 09:47
uruloki
 Newbie
Links : Onlinestatus : uruloki ist offline
Registriert seit: Apr 2008
Beiträge: 2
uruloki ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni

Wissensbestand in Unternehmen
Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Berni


 

Aktuelle PHP Scripte

PHP Server Monitor

PHP Server Monitor ist ein Skript, das prüft, ob Ihre Websites und Server betriebsbereit sind.

11.09.2018 Berni | Kategorie: PHP/ Security
PHP WEB STATISTIK ansehen PHP WEB STATISTIK

Die PHP Web Statistik bietet Ihnen ein einfach zu konfigurierendes Script zur Aufzeichnung und grafischen und textuellen Auswertung der Besuchern Ihrer Webseite. Folgende zeitlichen Module sind verfügbar: Jahr, Monat, Tag, Wochentag, Stunde Folgende son

28.08.2018 phpwebstat | Kategorie: PHP/ Counter
Affilinator - Affilinet XML Produktlisten Skript

Die Affilinator Affilinet XML Edition ist ein vollautomatisches Skript zum einlesen und darstellen der Affili.net (Partnerprogramm Netzwerk) Produktlisten und Produktdaten. Im Grunde gibt der Webmaster seine Affilinet PartnerID ein und hat dann unmittelb

27.08.2018 freefrank@ | Kategorie: PHP/ Partnerprogramme
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 21:08 Uhr.