Beibehaltung des Massenschwerpunkts einer mehrdimensionalen Integer-Box mit entfernten "Orthants"

Question

Ich bin daran interessiert, effizient den Massenmittelpunkt einer großen Box auf dem Integer-Gitter zu verfolgen, aus dem orthonome Regionen wiederholt herausgeschnitten werden. Ich habe in der Computergestützten Geometrie-Literatur herumgestochert, und es gibt eine Vielzahl von Datenstrukturen, die relevant sein könnten, aber die meiste Diskussion dreht sich um Sichtbarkeitsberechnungen (für Computergrafik) oder Nearest Neighbour-Finding (für Data Mining und ähnliches).

Das Papier http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf, das heißt:

Naylor, Bruce F. Interactive Solid Geometry via Partitioning Trees, 
     Proc. Graphics Interface '92, 1992, pp 11-18. 

beschreibt ein System, das geometrische Objekte von "Binary Space Partitioning Bäume" repräsentiert, unterstützt Set-Operationen, und hat eine faszinierende Erwähnung (ohne Details), dass das Zentrum von Die Masse der Objekte wird nach den gesetzten Operationen neu berechnet. Vielleicht habe ich einen blinden Fleck, aber es ist mir nicht sofort klar, wie man das Zentrum der Masse während des Baumverschmelzungsalgorithmus effizient aktualisiert, und ich habe keine Diskussion von Massenmittelberechnungen in Papieren gefunden, die den Naylor zitieren. Irgendwelche Zeiger?

Answer 1

Ein k-d-Baum ist im wahrsten Sinne des Wortes das, wonach Sie suchen, da Ihre Schnitte von Natur aus achsversetzt sind, aber an beliebigen Positionen. Der Umgang mit Verallgemeinerungen, wie zum Beispiel in der Veröffentlichung erwähnten binären Raumpartitionierungsschemen, klingt wie eine Schicht von Komplexität, die Sie nicht brauchen, und wird die Leistung reduzieren.

Mit einem k-d-Baum können Sie Schnittpunkte berechnen und entfernen, wobei große Bereiche verschwinden. Wenn Sie das Gewicht und den Massenschwerpunkt für jeden Knotenbereich eines k-d-Baumknotens innerhalb des Knotens selbst speichern, sollten Sie in der Lage sein, seinen Beitrag zum gesamten Massenmittelpunkt zu löschen, ohne die Kindknoten berücksichtigen zu müssen.

Dadurch erstellen Sie effektiv einen Baum von Volumina, die als Punktmassen dargestellt werden. Jeder Knoten kann nach Bedarf von seinen Kindern berechnet werden.