"Concave" Hülle

Hallo zusammen,

gibt es eine Möglichkeit eine “Nicht konvexe Hülle” um eine Punktwolke zu legen? Ich habe das Problem, dass ich astförmige Punktwolken habe und daraus eine Area erzeugen will, in der die Verzwigungen erhalten bleiben.

Ich suche jetzt eine Möglichkeit das ganze möglichst simpel mit wenig Rechenaufwand abzuhandeln. Hat jemand eine Idee?

Meine Momentane Idee ist um jeden Punkt einen Buffer zu legen und dann mit GeomUnion zu arbeiten. Aber das scheint mir bei 14 Mio. Punkten nicht das gelbe vom Ei zu sein.

Ich such seit einiger Zeit nach der gleichen Möglichkeit. Die Buffer-Methode hab ich getestet, da wird man bei mehr als eingen Punkten nicht wirklich glücklich, es sei denn man hat viel Zeit :wink:
Ein bisheriger Ansatz von mir war, ausgehend von einem Extrempunkt (z.b. Max. x-koordinate), der ja auf der Umrandung liegen muß, den jeweils nächsten Punkt innerhalb eines bestimmten Radiuses zu finden. Wenn mehrere Punkte zur Auswahl stehen kann der richtige über die Distanz zum Endpunkt der bis dahin generierten Linie erfolgen oder über die Winkeldifferenz zwischen den letzten erzeugten Liniensegment und dem neu zu Erzeugenden.
Soviel aus der Theorie, die das Problem bei mir gerade nicht mehr drängend ist, bin ich noch nicht zur Realisierung und Überprüfung gekommen :astonished:
Ich habe eine grobe Beschreibung dieses Vorgehen mal gesehen, und den Algorithmus im Einsatz vor Jahren mal gesehen, leider war das CSS und schlechtestens dokumentiert, weils auch ne ‘Bastelarbeit’ war…
Falls ich noch was finde, poste ichs hier :wink:

Gruß Uwe

Danke für die schnelle Antwort. Ich habe mir den Ansatz mal durch den Kopf gehen lassen. Ich bin mir noch nicht ganz sicher ob das ganze wirklich das gewünschte Ergebnis liefert. Ich muss mir aber denke ich einfach nochmal etwas Gedanken darüber.
Aber selbst wenn der Algorythmus zum richtigen Ergebnis führt bin ich mir nicht sicher ob er VIEL schneller als der Buffer-Ansatz ist. Zumindest nicht so viel schneller, als dass es den Aufwand lohnen würde.

Naja, ein bisschen mehr Aufwand als bei Konvexen Hüllen wird da schon dahinter sein. Positiv ist auf jeden Fall, das man einen definierten Anfangspunkt hat und das nicht alle Punkte bearbeitet werden müssen sondern nur die in der Nähe des Randes. Der Hauptfaktor dürfte die Selektion der im Suchradius liegenden Kandidaten sein. Eventuell könnte man den Algorithmus 4x gleichzeitig (max X,Y min X,Y) anwenden. Wie gesagt, ich kam nicht dazu das ganze praktischer zu vertiefen.
Ein ganz anderer Ansatz wäre die Auswertung der Punktdichte, was aber auch eine Bearbeitung aller Punkte einschliesst, aber auch z.B. Löcher berücksichtigen würde. Hier würde man die Punkte in einem vorgegebenen Areal zählen und entsprechend über eine feiner werdende Iteration könnte man den Umring einer Punktwolke festlegen. Hier könntest du dich über räumliche Indizierungsmethoden schlau machen, einige funktionieren so ähnlich.

Gruß Uwe