Why is quadtree slower than brute force?

Question

C++ / C#

Hello. I have a need to define for each unit all the units that it sees. Initially, I used the usual brute force (I took each unit in order and checked). However, this method leads to a huge amount of necessary calculations. For 10,000 units (and I have exactly so much) you need to check the visibility of other units 100,000,000 times.

In order to reduce the calculation time (and on average it took 15 seconds per pass), I decided to use a quadtree. However, after its implementation, the time per pass doubled, and is already 35-40 seconds, the reason for which is unclear to me. Can you tell me how you can speed up the query method (and it is it that takes almost all the time for calculations). Please describe your proposals in more detail in advance, because for me this topic is still a mystery and I do not fully understand how it works. Here is my code:

class Rectangle {
public:
    float X;
    float Y;
    float W;
    float H;
    Rectangle(float x = 0, float y = 0, float w = 0, float h = 0) {
        X = x;
        Y = y;
        W = w;
        H = h;
    }

    bool Contains(Unit unit) {
        return (
            unit.Position.X >= X - W &&
            unit.Position.X < X + W &&
            unit.Position.Y >= Y - H &&
            unit.Position.Y < Y + H
            );
    }

    bool Intersects(Rectangle range) {
        return !(
            range.X - range.W > X + W ||
            range.X + range.W <X - W ||
            range.Y - range.H > Y + H ||
            range.Y + range.H < Y - H
            );
    }
};
static vector<int> s;
class QuadTree {
     int Capacity;

public:
     Rectangle Boundary;
     vector<Unit> Points;
     bool Divided;

     QuadTree* NorthWest;
     QuadTree* NorthEast;
     QuadTree* SouthWest;
     QuadTree* SouthEast;

    QuadTree(Rectangle boundary, int capacity) {
        Boundary = boundary;
        Capacity = capacity;
        Divided = false;
    }

    void subdivide() {
        auto x = Boundary.X;
        auto y = Boundary.Y;
        auto w = Boundary.W;
        auto h = Boundary.H;
        auto ne = Rectangle(x + w / 2, y - h / 2, w / 2, h / 2);
        NorthEast = new QuadTree(ne, Capacity);
        auto nw = Rectangle(x - w / 2, y - h / 2, w / 2, h / 2);
        NorthWest = new QuadTree(nw, Capacity);
        auto se = Rectangle(x + w / 2, y + h / 2, w / 2, h / 2);
        SouthEast = new QuadTree(se, Capacity);
        auto sw = Rectangle(x - w / 2, y + h / 2, w / 2, h / 2);
        SouthWest = new QuadTree(sw, Capacity);
        Divided = true;
    }

    bool insert(Unit unit) {
        if (!Boundary.Contains(unit)) {
            return false;
        }

        if (Points.size() < Capacity) {
            Points.push_back(unit);
            return true;
        }
        else {
            if (NorthWest == nullptr) {
                subdivide();
            }
            if (NorthWest->insert(unit)) {
                return true;
            }
            else if (NorthEast->insert(unit)) {
                return true;
            }
            else if (SouthWest->insert(unit)) {
                return true;
            }
            else if (SouthEast->insert(unit)) {
                return true;
            }
        }
    }

    vector<Unit> query(Rectangle range) {
        vector<Unit> found;
        if (!Boundary.Intersects(range)) {
            return found;
        }
        else {
            for (size_t i = 0; i < Points.size();i++) {
                if (range.Contains(Points[i])) {
                    found.push_back(Points[i]);
                }
            }
            if (NorthWest == nullptr) {
                return found;
            }
            if (Divided) {
                vector <Unit> NWfound = NorthWest->query(range);
                found.insert(found.end(), NWfound.begin(), NWfound.end());

                vector <Unit> NEfound = NorthEast->query(range);
                found.insert(found.end(), NEfound.begin(), NEfound.end());

                vector <Unit> SWfound = SouthWest->query(range);
                found.insert(found.end(), SWfound.begin(), SWfound.end());

                vector <Unit> SEfound = SouthEast->query(range);
                found.insert(found.end(), SEfound.begin(), SEfound.end());
            }
        }
        return found;
    }
};

Rectangle boundry = Rectangle(0,0, 10, 10);
QuadTree quadTree = QuadTree(boundry, 10);

The call itself goes like this:

void Controller(int start,int end) {
    for (size_t i = start; i < end; i++)
    {
        Rectangle range = Rectangle(unit[i].Position.X, unit[i].Position.Y, 5, 5);
        vector<Unit> unitInRangeView = quadTree.query(range);//Все юниты,которые находятся в радиусе обзора юнита

        int CountSeeUnit = 0;
        for (size_t j = 0; j < unitInRangeView.size(); j++)
        {
            if (CheckView(unit[i], unitInRangeView[j].Position)) {
                CountSeeUnit++;
            }
        }
        printf("Unit Number %i sees %i unit(s) \n", i, CountSeeUnit);
    }
}

Materials that I used when writing this code:
https://youtu.be/OJxEcs0w_kE
https://github.com/CodingTrain/website/tree/main/C...
https://ru.wikipedia.org/wiki /quadtree#ps...

Answer 1

Perhaps the time is being eaten up by recursion. You are reassembling the found array many times from the pieces. This can be cured by making found an accumulator parameter in the recursion.

Answer 2

This quadtree (aka kd-tree) does not work well for the query "find all points") if the points in it lie in a heap and almost all fall into the answer. In this case, as in the naive solution, you will check almost all points, but at the same time you will spend several times more time on overhead - checking for empty sheets and traversing the tree.
Also, your tree, if the points are heaped together, creates a lot of empty vertices. Imagine that all points lie very close to the lower left corner. You will split the square into 4 parts, but 3 of them are empty. You repeat this operation until the squares are quite small and split the dots into several groups.
The first optimization is not to add points one at a time, but to process them as a group. If there are too many points in the current vertex, you need to find the median point horizontally, and within each group the median point vertically. And you will have 4 rectangles in place of the original, but they will not be aligned as 4 quarters of a square. But they will always divide in half.
The second optimization - if you see that the bounding rect of the current vertex lies entirely in the query - you just need to return all the points.
But there is another structure that will work better in your example, although it takes up more memory in log n.
You need a binary search tree segment tree (you can use std::set).
Get a segment tree by OX, where each vertex will be an OY-ordered set of all points falling into this segment by X.
When querying, you split the segment by X of the query into Log n segments-vertices in the segment tree (these are the vertices that need to be taken into the query on the link above) Further, in each of these Logn sets, you can get iterators of the beginning and end of all points in your query through lower_boundary and upper_boundary .
That is, you can get all the points in O(log n). True, some processing of them will already be O (n) in the worst case - the whole asymptotics will deteriorate. But if you only need their number, then you can find the distance between two iterators for a constant and you don’t need to copy the points anywhere into the vector.
But even if you need to bypass all the points in the rectangle, then here you can also speed up a bit - you do not copy the points into a vector. So you return a vector of pairs of iterators at the beginning and end in different sets. And, if you need to go around the points - go around with two nested loops - one for the vector of pairs of iterators, and the second for the iterators themselves.
Also, optimization, if your lower_bound turned out to be equal to upper_bound, then you don’t need to put this pair of iterators (empty interval) into the response array.
Another bonus of this structure is that you can quickly remove / add / change points and everything remains balanced. But, unlike a kd tree, it takes log n times more memory and the search operation always takes O(log n + answer), which can be slightly slower than the best case kd tree, where you can immediately end the search if it's obvious that there is nothing in the answer. But in the worst case, it will work faster.