Not getting Log(n) performance from quadtree

Here is my QuadTree class and node.

The problem is really with Querying.

In my game, I have a city which can have n * n streets (randomly generated).
And each street has buildings.

What I do is put all buildings and roads in a quadtree and render the result. The problem is as the city gets bigger, I lose lots of FPS. But QuadTree is supposed to be O(log n) so increasing the city size from 15 15 to 30 30 should not have that much impact on FPS.

In fact, doing bounding box check on each street individually against camera rect is much faster than quadtree right now.

Is there anything here that might benefit from optimization?

I'm mostly interested in optimizing OrientedQuery function. Inserting is pretty fast.

Thanks

```
public class QuadTree
{
///
/// The root QuadTreeNode
///
QuadTreeNode m_root;

///
/// The bounds of this QuadTree
///
OBB2D m_rectangle;
List results = new LinkedList();

public QuadTree(OBB2D rectangle)
{
m_rectangle = rectangle;
m_root = new QuadTreeNode(m_rectangle);
}

///
/// Get the count of items in the QuadTree
///
public int size()
{
return m_root.size();
}

///
/// Insert the feature into the QuadTree
///
///
public void Insert(T item)
{
m_root.Insert(item);
}

///
/// Query the QuadTree, returning the items that are in the given area
///
///
///

private List OrientedQuery(OBB2D area, List results)
{
return m_root.OrientedQuery(area,results);
}

public List OrientedQuery(OBB2D queryArea)
{
results.clear();
return OrientedQuery(queryArea, results);
}
}

Node

public class QuadTreeNode
{
///
/// Construct a quadtree node with the give

Unless you really need fast performance for head-insert, or iterator.add()/remove(), then LinkedList is almost always the wrong choice for a program.

Certainly, LinkedList has a bigger footprint on memory (it takes up many times more bytes of memory than the equivalent data in an ArrayList()).

So, my suggestion to you is to convert your LinkedLists to ArrayLists. ArrayList will take less space.

If you feel you really need to use a LinkedList, then you can do that, but, please use list.isEmpty() instead of list.size() == 0. This is generally a good thing to do.

Previously I suggested that the performance problems may be because of O(n) performance of LinkedList.size(). In the past I have fallen victim to a problem with size() == 0 instead of using isEmpty() and now, when I see it, I 'react'. In this case, it was premature, so I have edited out that part of my answer.

After that failed knee-jerk response, and after looking more carefully at your code, I have one suggestion, one potential bug, and a couple of questions...

The suggestion:

In your QuadTree class you keep an instance array:

List results = new LinkedList();

Which you 'reuse' in the method:

public List OrientedQuery(OBB2D queryArea)
    {
        results.clear();
        return OrientedQuery(queryArea, results);
    }

This is a problem because it is possible that you may be holding on to memory for much longer than you need. There is no advantage to doing what you do. The code could simply be:

public List OrientedQuery(OBB2D queryArea)
    {
        return OrientedQuery(queryArea, new LinkedList());
    }

The potential bug:

You have three 'Case' sections in the OrientedQuery. One for if the node fully-contains the search area, the second for if the query-area fully-contains the node, and the third is if there's an overlap, not a full-contains condition.

The Second Case has a bug:

// Case 2: Sub-quad completely contained by search area 
        // if the query area completely contains a sub-quad,
        // just add all the contents of that quad and it's children 
        // to the result set. You need to continue the loop to test 
        // the other quads
        if (queryArea.overlaps(node.getBounds()))
        {
            node.SubTreeContents(results);
            continue;
        }

The if condition should surely be if (queryArea.contains(...)) ... rather than if (queryArea.overlaps(node.getBounds())) ...

As it stands, it is possible that you are returning many nodes that should not otherwise be returned. This is potentially the source of your performance problem.

Questions:

I have scoured the code have presented here, and cannot otherwise find where your code performance may regress. This leads me to believe that the performance issue is in one of the methods you call that is not presented in this question.

Places where I thing it would be useful to inspect are:

• OBB2D.getBoundingRect() - presume this is a constant-time operation.

• queryArea.overlaps(...) and queryArea.contains(...). What do these methods look like?

StackExchange Code Review Q#18334, answer score: 2