# 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<T extends Entity>
{
/// <summary>
/// </summary>

/// <summary>
/// The bounds of this QuadTree
/// </summary>
OBB2D m_rectangle;

{
m_rectangle = rectangle;
}

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

/// <summary>
/// Insert the feature into the QuadTree
/// </summary>
/// <param name="item"></param>
public void Insert(T item)
{
m_root.Insert(item);
}

/// <summary>
/// Query the QuadTree, returning the items that are in the given area
/// </summary>
/// <param name="area"></param>
/// <returns></returns>

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

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

Node

{
/// <summary>
/// Construct a quadtree node with the given bounds
/// </summary>
/// <param name="area"></param>
{
m_bounds = bounds;
}

/// <summary>
/// The area of this node
/// </summary>
OBB2D m_bounds;

/// <summary>
/// The contents of this node.
/// Note that the contents have no limit: this is not the standard way to impement a QuadTree
/// </summary>

/// <summary>
/// The child nodes of the QuadTree
/// </summary>

/// <summary>
/// Is the node empty
/// </summary>
public boolean isEmpty()
{
return m_bounds.getBoundingRect().isEmpty() || m_nodes.size() == 0;
}

/// <summary>
/// Area of the quadtree node
/// </summary>

public OBB2D getBounds()
{
return m_bounds;
}

/// <summary>
/// Total number of nodes in the this node and all SubNodes
/// </summary>
public int size()
{
int count = 0;

count += node.size();

count += this.Contents().size();

return count;

}

/// <summary>
/// Return the contents of this node and all subnodes in the true below this one.
/// </summary>
public List<T> SubTreeContents(List<T> results)
{
node.SubTreeContents(results);

return results;
}

public List<T> Contents()
{
return m_contents;
}

/// <summary>
/// Query the QuadTree for items that are in the given area
/// </summary>
/// <param name="queryArea"></pasram>
/// <returns></returns>

public List<T> OrientedQuery(OBB2D queryArea, List<T> results)
{
// this quad contains items that are not entirely contained by
// to see if they intersect.
for (T item : this.Contents())
{
if (queryArea.overlaps(item.getRect()))
}

{
if (node.isEmpty())
continue;

// Case 1: search area completely contained by sub-quad
// if a node completely contains the query area, go down that branch
// and skip the remaining nodes (break this loop)
if (node.getBounds().getBoundingRect().contains(queryArea.getBoundingRect()))
{
node.OrientedQuery(queryArea,results);
break;
}

// 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
if (queryArea.overlaps(node.getBounds()))
{
node.SubTreeContents(results);
continue;
}

// Case 3: search area intersects with sub-quad
// traverse into this quad, continue the loop to search other
if (node.getBounds().overlaps(queryArea));
{
node.OrientedQuery(queryArea,results);
}
}

return results;
}

/// <summary>
/// Insert an item to this node
/// </summary>
/// <param name="item"></param>
public void Insert(T item)
{
// if the item is not contained in this quad, there's a problem
if (!m_bounds.getBoundingRect().contains(item.getRect().getBoundingRect()))
{
return;
}

// if the subnodes are null create them. may not be sucessfull: see below
// we may be at the smallest allowed size in which case the subnodes will not be created
if (m_nodes.size() == 0)
CreateSubNodes();

// for each subnode:
// if the node contains the item, add the item to that node and return
// this recurses into the node that is just large enough to fit this item
{
if (node.getBounds().getBoundingRect().contains(item.getRect().getBoundingRect()))
{
node.Insert(item);
return;
}
}

// if we make it to here, either
// 1) none of the subnodes completely contained the item. or
// 2) we're at the smallest subnode size allowed
// add the item to this node's contents.
}

/// <summary>
/// Internal method to create the subnodes (partitions space)
/// </summary>
private void CreateSubNodes()
{
// the smallest subnode has an area
if ((m_bounds.getBoundingRect().height() * m_bounds.getBoundingRect().width()) <= 10)
return;

float halfWidth = (m_bounds.getBoundingRect().width() / 2.0f);
float halfHeight = (m_bounds.getBoundingRect().height() / 2.0f);
float quarterWidth = (halfWidth / 2.0f);
float quarterHeight = (halfHeight / 2.0f);

new OBB2D(m_bounds.getBoundingRect().left + quarterWidth,
m_bounds.getBoundingRect().top + quarterHeight, halfWidth,halfHeight)));
new OBB2D(m_bounds.getBoundingRect().left,
m_bounds.getBoundingRect().top + halfHeight + quarterHeight,
halfWidth,halfHeight)));
new OBB2D(m_bounds.getBoundingRect().left + halfWidth + quarterWidth,
m_bounds.getBoundingRect().top + quarterHeight, halfWidth,halfHeight)));
new OBB2D(m_bounds.getBoundingRect().left + halfWidth + quarterWidth,
m_bounds.getBoundingRect().top + halfHeight + quarterHeight,
halfWidth, halfHeight)));
}

}

-
Did you profile that code? What happens when the city size grows by 10x? 100x? (Without doing anything else than quadtree queries.) –  Quentin Pradet Nov 26 '13 at 15:52
What arguments does the OBB2D constructor take? –  Peter Taylor Nov 29 '13 at 14:30

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:

   List<T> results = new LinkedList<T>();


Which you 'reuse' in the method:

   public List<T> 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<T> OrientedQuery(OBB2D queryArea)
{
}


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
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?
-
LinkedList.size() is O(1). Look at the openjdk source. –  Peter Taylor Nov 29 '13 at 14:26
Well, arn't I just floozing today.... huh. Did that change 'recently' ? (off to do some research). –  rolfl Nov 29 '13 at 15:42
@PeterTaylor LinkedList.size() is O(1) in the reference implementation, but O(1) performance is not guaranteed unless it is documented. The reference implementation could even change in the future — as it did for String.substring(). Therefore, you should always prefer .isEmpty() to .size() == 0. –  200_success Nov 29 '13 at 17:20
@200_success, O(1) performance isn't documented for isEmpty() either, and in fact if you take the API doc literally then LinkedList is documented to inherit its implementation of isEmpty() from AbstractCollection, which is documented to implement isEmpty() by calling size(). I personally prefer isEmpty() to size() == 0, but that's a matter of style rather than performance guarantees. –  Peter Taylor Nov 29 '13 at 18:15
@PeterTaylor Revised my answer. Thanks for the O(1) point. I do appreciate knowing when I am wrong almost as much as knowing when I am right .... ;p –  rolfl Nov 29 '13 at 23:15

I smell a rat in CreateSubNodes.

    float quarterWidth = (halfWidth / 2.0f);
float quarterHeight = (halfHeight / 2.0f);


Why do you need quarters? The only thing that I can think of is that the OBB2D constructor takes (centre_x, centre_y, width, height) rather than the more conventional (left, top, width, height).

    m_nodes.add(new QuadTreeNode<T>(
new OBB2D(m_bounds.getBoundingRect().left + quarterWidth,
m_bounds.getBoundingRect().top + quarterHeight, halfWidth,halfHeight)));


is consistent with that hypothesis.

    m_nodes.add(new QuadTreeNode<T>(
new OBB2D(m_bounds.getBoundingRect().left,
m_bounds.getBoundingRect().top + halfHeight + quarterHeight,
halfWidth,halfHeight)));


is not. The x-coord is offset by a quarter and the y-coord by a half.

If the arguments to the constructor are centre and size then one of the four quads is misplaced, so on average something like 1/8 of the items which should go further down the quad are being stored in the current node. If the arguments to the constructor are corner and size then three of the four quads are misplaced, and on average something like 7/16 of the items is not being pushed further down.

-