Punkte gruppieren

[claudia]

Hallo

ich habe mehrere tausend Punkte in einer MySQL-Datenbank (Laengen- und Breitengrade), die ich auf einer Weltkarte (Google Maps) darstellen will. Dabei sollen, wenn es mehr als eine bestimmte Anzahl Punkte in einem bestimmten Umkreis gibt, diese Orte zu einem zusammengefasst werden.
Es gibt fuer Google Maps ein Javascript, das Punkte clustern kann, allerdings skaliert das nicht sehr gut wenn man viele Punkte hat, da dann das Laden der Punkte schon zu lange dauert. Ausserdem kann man dann den Text des Clusters nicht gut anpassen.
Ich wuerde daher gern das Clustern schon auf Serverseite uebernehmen, da ich dann die noetigen XML-Dateien mit den Punkt-Information einfach nachts per Cronjob erstellen kann. Als Skriptspache verwende ich PHP.
Leider habe ich im Moment keinerlei Ansatz, wie ich das anfangen soll. An sich will ich die Zentren eines Voronoi-Diagramms berechnen, weiss aber nicht, wie ich das anfangen kann oder ob es nicht eine ganz anderen Ansatz gibt.

Bin fuer jegliche Hinweise dankbar

Claudia

[Stefan Eickhoff]

Hallo Claudia,

hier findest Du vielleicht was passendes:
< http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html>

Viele Grüße

Stefan

[Frank (no reg)]

Hallo,

mit Voronoi hast du doch schon mal ein gutes Stichwort. Ein bisschen mehr Suche über Wikipedia und Google hätte dich auf den Fortune's Algorithmus gebracht ...

Aber sicherlich keine triviale Aufgabe sondern eine recht interessante. :)

Gruss, Frank

[claudia]

Hallo Frank

ich bin mir nicht sicher ob ich das richtig verstande habe, aber meines Erachtens berechnet dieser Algorithmus auch nur ein Voronoi-Diagramm, wofuer die Zentren schon vorgegeben sein muessen. Ich will aber gerade die Zentren berechnen.
Beispiel:
Angenommen Frankfurt waere eine kreisrunde Stadt und alle Punkte, die in Frankfurt liegen, waeren gleich verteilt. In dem Fall muesste die Stadtmitte von Frankfurt als Ergebnis rauskommen, selbst wenn dort gar kein Punkt ist.
Dann gibt es auch noch eine Ansammlung von Punkten in Offenbach. Bei einem grossen Clusterradius werden diese dafuer sorgen, dass sich der Clusterpunkt fuer Frankfurt etwas in Richtung Offenbach verschiebt, bei einem geringen Clusterradius gibt es zwei Clusterpunkte, einen fuer Frankfurt und einen fuer Offenbach.

Leider faellt es mir schwer, das algorithmisch genauer zu formulieren...

Herzlichen Dank fuer jeden Tip

Claudia

[Frank (no reg)]

Soweit ich das in aller schnelle überflogen habe, ist dieser Algorithmus ein Sweeping Line Algorithmus von oben nach unten für eine Ebene mit Punkten. Jeder Punkt ist dabei ein Zentrum, genau. Und wenn ich so jetzt dieses Posting von dir nochmal lese, dann suchst du weniger nach Voronoi oder Thiessen-Polygon, sondern nach was anderem. (war aber auch nicht so ganz so einfach zu verstehen)

Das Frankfurter Problem würdest/könntest/solltest du dann einfach damit lösen, dass du Frankfurt Stadtmitte als Koordinatenpaar mitführst (aber im Normalfall nicht mit ausgibst).

Also kennst du das Polygon und möchtest dazu das Zentrum haben? Oder du kennst gar nichts, weder das Zentrum, noch das Polygon. Dann solltest du eine der beiden Unbekannten eliminieren.

Wenn du technisch beschreiben kannst, was ein Gebiet (eine Ebene begrenzt durch existente / virtuelle Koordinatenpaare) ausmacht und wie du die Mengen darin gewichtest. Wie ich schon andeutete, du kannst imaginäre Punkte, z.b. auf Stadt / Kreis / Region / Land / Staat / Kontinent Level definieren und dafür jeweils noch Einschränkungen für maximale Entfernung, Min-/Max-Anzahl von Koordinatenpaaren um ein Zentrum herum setzen. Aus der Gewichtung der Mengen und der Strecke zwischen den Punkten kannst du dann evt. schon eine "Verschiebung" des Ergebnisses ableiten. Die Gewichtung bekommst du mittels GROUP BY, COUNT() und WHERE aus deinen gespeicherten Daten.

Aber andere Frage: Muss es denn wirklich so kompliziert werden? Das Verhältnis Nutzen zu Aufwand ist dann ggf nicht mehr wirklich sinnvoll.

Ciao, Frank

[Daniel Thoma]

Hallo claudia,

Was Du suchst, sind wohl Cluster-Algorithmen.
Einen Überblick gibt es da: < http://de.wikipedia.org/wiki/Clusteranalyse>
Die hierarchischen Verfahren und der k-means-Algorithmus sind relativ einfach zu implementieren.
Evtl. muss man sich ein Bisschen etwas überlegen, um nicht zu viele Distanzen ausrechnen zu müssen. Ich würde das aber einfach mal naiv implementieren und ausprobieren, ob das reicht.

Grüße

Daniel