I am interested in effectively tracking the center of mass of a large box on an integer lattice, from which areas of an ortho-shaped form are repeatedly cut. I pondered in the literature on computational geometry, and there were many different data structures, but in most cases we are talking about computing visibility (for computer graphics) or finding nearby neighbors (for data mining, etc.).
Document
http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf , i.e.:
Naylor, Bruce F. Interactive Solid Geometry via Partitioning Trees,
Proc. Graphics Interface '92, 1992, pp 11-18.
discusses a system that represents geometric objects using "trees of binary separation of space", supports dialing operations and has an intriguing mention (without details) that the center of mass of objects is recalculated after given operations. I may have a blind spot, but it does not immediately seem to me how to efficiently update the center of mass during the tree merge algorithm, and I did not find a discussion of the center of mass computing in the articles citing Naylor. Any pointers?
source
share