Quadtree перемещение сохраненных точек

Я использую четырехугольное дерево в качестве структуры данных для хранения точек. Так как мне нужно быстро найти все точки в определенной области.

Однако мне нужно переместить очки. В моей C ++ программе. Поскольку движение происходит со всеми точками, но для каждой точки в другом направлении, я в настоящее время уничтожаю свое квадродерево и перестраиваю его, что приводит к большому количеству размещения и удаления.

Поэтому мой вопрос: есть ли лучшая структура данных для такого рода проблем?

У меня есть следующие требования:
У меня есть n-Points.

Мне нужно быстро получить все очки в определенной области. С моим quadtree это примерно O (log (n)). Однако эта операция вызывается m раз, где m> n, поэтому речь идет о O (m * log (n)).

Мне нужно переместить все точки. На данный момент это работает около O (n * logn). Этот метод вызывается только один раз для всех m.

Однако я считаю это решение на данный момент неудовлетворительным. Поскольку я всегда разрушаю свое quadtree и перестраиваю его, что вызывает перерасход из-за распределения.

ОБНОВИТЬ:
Точки не распределены равномерно. Есть позиции, где они плотные, и некоторые позиции, где мало точек.

Вот некоторый упрощенный код. Вот код указателя, который хранится:

class Point
{
public:
Point(double x, double y):x(x),y(y){};

void movePoint(double ux, double uy);

double x;
double y;
};

вот интерфейс дерева квадов

class QuadTree
{
public:
QuadTree(double north, double west, double south, double east,
int maxItems);

//inserts a point into the tree runs in log(n)
bool put(Point* pt);
// returns all point in the rectange defined by the four variables runs in log(n)
std::vector<Point*> get(double north, double west, double south, double east);
// deletes everything in the quad tree
void clear();

private:

QuadTreeNode* top_=nullptr;

};

и здесь интерфейс QuadTreeNode с реализацией метода get и put, чтобы показать, как хранится Point.

class QuadTreeNode
{
public:

QuadTreeNode(double north, double west, double south, double east,
int maximumItems);

~QuadTreeNode();

//split the node if to much items are stored.
void split();
//returns the children of the node
QuadTreeNode* getChild(double x, double y);

bool put(Point* leaf){
if (children_ == nullptr) {
items_.push_back(leaf);

if (items_.size() > maxItems_)
split();
return true;
} else {
QuadTreeNode* node = getChild(leaf->getX(), leaf->getY());
if (node != nullptr) {
return node->put(leaf);
}
}
return false;
}

std::vector<Point*> QuadTreeNode::get(QuadRectangle rect, std::vector<Point*>& vector) {
if (children_ == nullptr) {
for (Point* pt : items_) {
if (rect.pointWithinBounds(pt->getX(),pt->getY())) {
vector.push_back(pt);
}
}
} else {
for (QuadTreeNode* child : *children_) {
if (child->bounds_.within(rect)) {
child->get(rect, vector);
}
}
}
return vector;
}

std::vector<Point*> items_;

unsigned int maxItems_;

std::array<QuadTreeNode*,4>* children_ = nullptr;

QuadRectangle bounds_;
};