Zusammenfassen von POI (Clustern) - Algorithmus

hi !

ich habe eine Liste von Punkten und möchte dicht zusammenliegende Punkte zusammenfassen (clustern). Das ganze wird nicht über OpenLayers verarbeitet.

Hat einer von Euch eine Idee oder kennt einen einfachen Algorithmus wie man soetwas (mit Perl) machen könnte ?

Gruß Jan :slight_smile:

Hallo Jan,

Ich kann dir zwar nicht direkt weiterhelfen, da ich keine Erfahrungen mit Clustering habe, aber ich denke damit dir vernünftig geholfen werden kann musst du viel genauer beschreiben, was du umsetzen möchtest und was deine Anforderungen sind. Nach welchen Kriterien willst du die Cluster für die POIs erstellen? Was ist der Input (vermutlich osm xml)? Was soll der Output sein? Wofür sollen die Cluster verwendet werden? usw

Zum Einlesen ist sicherlich der Wikipedia-Artikel geeignet, der auch einige Verfahren/Algorithmen anschneidet bzw. verlinkt: http://de.wikipedia.org/wiki/Cluster_(Informatik) bzw http://de.wikipedia.org/wiki/Clusteranalyse

Grüße vom Namensvetter :wink:

hi !

es geht einfach darum das im Bereich einer Karte eine Anhäufung von POI einer Sorte existiert und damit nicht x Icons dargestellt werden soll nur ein Icon erscheinen. Das das Ziel - wie das der Renderer später macht ist etwas anderes.

Mir geht es erst einmal darum das ich eine beliebige Zahl von POI habe und der Algo jetzt schaut wo liegen in einem Bereich Punkte die einen Abstand nicht größer X haben. Wenn er eine solche Ansammlung findet wird eine alternative Koordinate ermittelt.

Mit anderen Worten Input - eine Menge von Punkten und als Ergebnis kommt eine Menge von Punkten die weiterhin bestehen bleiben und dann eine Menge von Punkten die Clusterpunkte repräsentieren.

… hilft das weiter …?

Gruß Jan :slight_smile:

Du könntest dir ja mal z.B. das hier anschauen: https://github.com/Leaflet/Leaflet.markercluster

Oder wäre das was?

http://geschichtskarten.openstreetmap.de/historische_objekte/?zoom=14&lat=49.32661&lon=7.12462&layers=B0000000FFFFFFTFFTFT

(der Klumpen in der Mitte über der “22”). Viele POIs eng beisammen, aber wenn man anklickt, erscheinen alle auf einmal, untereinander.

(Details? → Netzwolf)

Gruß,
Zecke

Nur ein paar Gedankensplitter:

  • man könnte den Schwerpunkt (Mittelwert) der Eingangspunktemenge bestimmen. (xs, ys)=(summe(xi)/n, summe(yi)/n)
  • man könnte dann alle Punkte auswählen, die von diesem Schwerpunkt nicht zu weit entfernt sind (xi-xs)^2 + (yi-ys)^2 < r^2
  • man könnte aus diesen Punkten dann einen neuen Schwerpunkt bilden.

Nahmd,

Das ist gerade kein Clustern: die Symbole werden gewissen- und skrupellos übereinandergezeichnet. Die Magie ist eine Ergänzung des Popup-Codes: der nimmt nicht naiv das oberste Icon, sondern schaut auch noch darunter nach.

Geclustert wird auf der Stolpersteinkarte, allerdings in einer strengen, systematischen und nicht verspielten Art, nicht schön, aber m.E. dem Thema angemessen.

Bei denen geht es verspielter zu.

Gruß Wolf