Circle stacking algorithm

Question

In a game I'm making I need to stack a bunch of circles of different radii so that no stacks overlap. The circles are stacked so that overlapping circles form a stack with the circle of largest radius on top. The circles are randomly placed on a continuous 2D plane. There can be circles of equal radius.

I use C++. The circles are stored in vectors. By plane i just mean that the circles have (double) x and y coordinates. Stacks are essentially vectors of circles that use the position and radius of the topmost one (which shoudl be the largest). By "no stacks overlap" i mean that after stacking the circles the stacks should not overlap.

What I've done:

1. Sort the circles by radius
2. For the first circle( the largest one) add all overlapping circles to its stack, removing them from the circle list.
3. repeat until circle list is empty.
4. sort all stacks to get the largest one on top.

Why it doesnt work (always). Sometimes 3 equal radius circles are overlapping so that two circles share one (but arent overlapping themselves). One of the circles gets the shared circle and then by chance that circle gets chosen as the top one which leads to two overlapping stacks.

I've given it much thought but all methods i can think of seem to require either very complicated loops and ifs to manually check which circles are shared and how to move them, or brute force and luck by just randomly rearranging the stacks.

Is there some general way of approaching problems like this? It would also be cool if the stacks were "optimal" in the sense that all stacks minimize their "energy" (as in the distance that they pull in nodes is minimized).

In situation 1 the center circle was chosen (assuming all three large circles had the same radius) because it minimizes the number of stacks. In situation 2 the largest circle correctly gets on top of a stack. In situation 3 everything goes as intended. In situation 4 the small circle erroneously gets on top of a stack. Also if the two other circles are equal size there should only be one stack as in situation 1. In situation 5 the wrong circle gets on top which leads to overlapping stacks.

Thanks!

A working brute force version:

    std::vector<std::vector<Symbol>::iterator >symPos; std::vector<int> cons;std::vector<Symbol> selVec; Symbol start; SymbolStack stack;
    while(symbols.size()){
        std::sort(symbols.begin(),symbols.end(),std::greater<Symbol>());
        start = symbols.front();
        for(int i = 0;i<symbols.size();i++){
            if(symbols[i].getRadius() == start.getRadius()){
                selVec.push_back(symbols[i]); cons.push_back(0); symPos.push_back(symbols.begin()+i);
            }
        }
        for(int i = 0;i<selVec.size();i++){
            for(int j = i+1;j<selVec.size();j++){
                if((selVec[i].getPos()-selVec[j].getPos()).len() < 2*(selVec[i].getRadius()+selVec[j].getRadius())){
                    cons[i]++;cons[j]++;
                }
            }
        }
        int maxCons = 0; int selected;
        for(int i = 0;i<cons.size();i++){
            if(cons[i] >= maxCons){selected = i;maxCons = cons[i];}
        }
        start = selVec[selected];
        stack.addSymbol(start); symbols.erase(symPos[selected]);
        for(auto it = symbols.begin();it!=symbols.end();){
            if((it->getPos()-start.getPos()).len() < 1.5*(it->getRadius()+start.getRadius())){
                stack.addSymbol(*it);
                it = symbols.erase(it);
            }else{
                it++;
            }
        }
        stacks.push_back(stack);
        stack.clear();
        selVec.clear();
        symPos.clear();
        cons.clear();
    }

Where Symbol is a circle object. stacks is an std::vector. Not efficient at all but it works. I'm going to try and optimize it like Nico suggested. The Symbol objects contain a vector2 position (getPos()) a radius (getRadius()). the len() method gets the length of a vector2.

Answer 1

I would split the algorithm in two parts - representative detection and stack building, where stack building basically associates every circle to a representative, forming a stack.

The last part is quite easy. Iterate each circle and associate it to the representative that results in the least energy (probably to the closest one). Use acceleration data structures like grids or kd-trees to enhance such queries.

The first part is much harder. Actually, it looks NP-hard, although I can't prove it. But let's start at the beginning.

Sorting the circles in descending order by their size is a good idea. If the first circle (with maximum radius) does not overlap a circle with the same radius, it should obviously be a representative. In this case, remove (or mark) every overlapping circle from the list. In the other case, you have to decide which of the overlapping circles (of equal radius) to choose.

In your code, you use a simple heuristic (the number of overlapping circles) to decide which circle to choose. Depending on your data and use-case, this may be a valid option. In general, this might not always result in an optimal solution (because decisions may change subsequent decisions significantly).

Another option for this is to use back-tracking. Try one decision and see how it goes out (evaluate number of representatives in the end). Then, when going back, also try other decisions. You may leave a decision branch as soon as the number of representatives exceeds the minimum number seen so far. Unfortunately, this may result in an exponential run time in the worst case. But you only have to decide in the case of overlapping equally-sized circles. If this scenario does not occur very often, back-tracking may be a good option, which guarantees you a globally optimal solution.

And keep in mind that your list is sorted. You don't have to search the entire list when you search for a circle of a specific radius. There are a few places in your code that could be improved by that fact. And, as mentioned, use acceleration structures to evaluate overlap-queries faster.