сохранение центра масс многомерного целочисленного поля с удалением некоторых «ортантов»

Question

Я заинтересован в том, чтобы эффективно отслеживать центр масс большого ящика на целочисленной решетке, из которого многократно вырезаны области в форме ортантов.Я изучал литературу по вычислительной геометрии, и существует множество структур данных, которые могут быть важны, но большая часть дискуссии касается вычислений видимости (для компьютерной графики) или поиска ближайших соседей (для интеллектуального анализа данных и тому подобного).

В статье http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf, т.е.:

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

обсуждается система, которая представляет геометрические объекты с помощью "деревьев разбиения двоичного пространства", поддерживает операции над множествами и имеет интригующее упоминание (без подробностей), что центр масс объектов пересчитывается после заданных операций.Возможно, у меня есть слепое пятно, но мне не сразу понятно, как эффективно обновлять центр масс во время алгоритма слияния деревьев, и я не нашел обсуждения вычислений центра масс в статьях, которые цитируют Нейлора.Есть указатели?

Answer 1

KD-дерево - это буквально то, что вы ищете здесь, поскольку ваши срезы выровнены по оси, но в произвольных положениях.Работа с обобщениями, такими как схемы разбиения двоичного пространства, как упомянуто в статье, звучит как слой сложности, который вам не нужен, и снизит производительность.

С деревом kd вы сможете вычислять и удалятьпересечения с большими областями исчезают.Если вы сохраняете вес и центр масс для каждой области узла дерева kd внутри самого узла, вы должны иметь возможность стереть свой вклад в общий центр масс, не рассматривая дочерние узлы.

Делая это,фактически вы будете строить дерево томов, представленных в виде точечных масс.Каждый узел может быть рассчитан по его дочерним элементам по мере необходимости.