Best geeignetste spatiale Datenstruktur für Widgets

Hallo da,
ich schaue gerade rum, was wohl die beste spatiale Datenstruktur für ein Widget-System ist. Im Moment scheint mir R* + eine parallele Liste, in der man Dinge hält, die sich gerade dynamisch bewegen (weil ständige heuristische Updates des Baums wohl wenig attraktiv erscheinen), am geeignetsten, aber vielleicht kennt jemand eine Blog-Abhandlung oder soetwas zu dem Thema?

Viele Grüße

knivil

Um R* fuer Widgets bewerten zu koennen, solltest du vielleicht ein besseres Stichwort fuer google nennen. Weiterhin ist Widget ein sehr weiter Begriff, d.h. Form ist unbekannt, Kreise, Rechtecke, Dreiecke, Grenzen definiert durch implizite Funktionen, .... Auch die erwartete Anzahl ist entscheident, wahrscheinlich tuts eine einfache Liste/Array.

Nunja, mit Widgets meinte ich jetzt "Fenster" so wie eben Fenstersysteme von "modernen" Desktops halt so aussehen, bevor irgendwelche Marketingabteilungen meinen dass ihr Programm ganz anders und hyper-fesh aussehen soll. In ihrer Form gehe ich davon aus, dass sie annähernd rechteckig sind, sodass eine AABB sie recht gut überdeckt. Das erweist sich in meinen Augen ja auch für den Menschen am angenehmer als irgendwelche Donutförmigen Fenster über den ganzen Bildschirm, er will die Information ja auch "kompakt" haben.
Mein kleines Testprogramm listet mir knapp 600 Fenster auf, die gerade offen sind. Wobei ich mir nicht so sicher bin, wieviele davon Pseudo-Fenster sind. Falls welche nicht wirklich geometrisch sind, wird das bestimmt mehr als aufgewogen von den vielen Fenstern, die Windows nicht sieht, weil die drei Visual-Studio-Instanzen ihr eigenes Fenster-Management durchführen.

Nur 600? 600^2=3.6*16. Das macht überschlagsmässig 1ms pro Update wenn du Brute-Force anwendest.

Falls das wirklich nur ein Desktop mit Fenstern sein soll kann dir wohl so ziemlich alles recht sein. Wenn nicht Brute-Force, dann ein Grid, wenn das auch nicht reicht, ein Quadtree.

Ein R* wäre da nur Overkill, kann gut sein, dass seine Konstante gross genug ist, um langsamer als ein Quadtree oder ein Grid zu sein.