Zusammenfassen von Objekten zu Gruppen mit ConvexHull

Hallo,

ich suche verzweifelt nach einer Möglichkeit eine ConvexHull solang zu erweitern, bis z.B eine bestimmte menge an Objekten enthalten sind und diese dann so wieder, gruppiert, auszugeben.

Problem :
Eine ConvexHull (wäre jetzt mein Ansatz) soll solang erweitert werden, bis eine bestimmte Anzahl an Geometrien erreicht wurde (jede Geometrie hat eine Wertigkeit) wobei die ConvexHull natürlich immer minimal sein soll.

/Alle Objekte sollen jetzt mal fiktiv geometrisch nebeneinander liegen.
Obj1 hat die Wertigkeit 2
Obj2 hat die Wertigkeit 3
Obj3 hat die Wertigkeit 2

ConvexHull soll solang Objekte aufnehmen, bis z.B die Wertigkeit 5 erreicht / überschritten wurde.
Also geht es los -> Obj1 wird eingeschlossen sowie Obj2, wonach abgebrochen wird, da die Wertigkeit erreicht wurde und im Idealfall wären Obj1 und Obj2 die Rückgabewerte.

Ist dieses überhaupt möglich? Könnte ich eine “Bedienung” für ConvexHull erstellen?

Kennt jemand eine andere Methodik um Objekte möglichst gleichmäßig auf minimale Flächen zu verteilen?

Dreckige anderer Ansatz: Alle Objekte mit Allen anderen Objekten jeweils in ConvexHull stecken und dann ermitteln, welche Summe der Flächeninhalte der kleinste war.
Problem -> Zeitaufwendig / Speicherintensiv und einfach irgendwie der falsche Ansatz :wink: Bei 100 Objekten müssten das 100^100 Variationen sein. Mit kleinen Optimierungen bekommt man dann sicherlich ein gutes Stück weg, aber für eine Geometrische anfrage doch etwas heavy.

Über Hilfe wäre ich dankbar!

Ich hab zwar nicht ganz verstanden, was du meinst :confused: :slight_smile: aber ich versuchs mal:
Also eine ConvexHull wird gebildet als der minimale Umfang um die übergebene Geometrie wie z.B. ein Multipolygon. Du müsstest die Summation deiner Wertigkeit schon vorher lösen und dann das Ergebnis an ConvexHull übergeben. Daraus könntest du wiederum die Fläche des Ergebnisspolygons berechnen und das jeweils kleinste wählen.
Du könntest auch alles in einer Funktion unterbringen, aber der Teufel dürfte so oder so in der Gruppierung der Objekt nach Wertigkeit und der Prüfung auf minimale Fläche liegen.
Wenn ich das jetzt richtig interpretiert habe :wink:
Gruß Uwe

Hi Uwe,

das ist soweit richtig. Ich brauch halt die “minimalen” ConvexHull’s, die sich ergeben könnten. Sprich, ich wollte die Aufgabe des Groupierens der Datenbank überlassen. Das Problem ist nicht wirklich Trivial und mir ist klar, dass man “normalerweise” ConvexHull’s nicht so einsetzt, jedoch wäre das die einzige Bedingung logisch noch in eine Datenbank übergeben könnte.

Wäre es möglich, eine Vielzahl an ConvexHull’s mit Area nach Größe zu sortieren um so das Minimum zu ermitteln?

Das sollte problemlos auch ohne sortieren etwa so gehen:

select min(area(convexhull(geometry)))

evtl hönntest du auch was konstruieren mit boundingboxen(so mal als Idee), wie ich neulich hier gelernt habe, scheint der Algorithmus recht schnell zu sein :wink:

Moin
Uwe

Also ohne vorheriges Sortieren geht es wahrscheinlich nicht, da es ja Beliebig viele Variationen gibt ( anzahl_an_objekten^anzahl_an_objekten ) die man dann der ConvexHull geben müsste.

Normal müsste die (sowie ich diese Interpretiert habe) ja so oder so immer die minimale Fläche ausgeben, welches die Geometrien umspannt. Ich bräuchte das natürlich als eine Art “where” Bedingung, weshalb ich das ganze nun noch mal anders angehen werde (wie genau weiß ich auch noch nicht, aber es wird auf jedenfall “spannend” bis “unmöglich” :wink: )