Return to Answer

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.

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.

There are two related items which I feel could be the cause of your problems, but I would have to see your code running to prove it. Still, it appears you may have 'stumbled' on the 'worst case scenario' for java.util.* ..... LinkedList.

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 big footprint on memory (it takes up many times more bytes of memory than the equivalent data in an ArrayList()), but, in your particular case, you are doing an even worse thing, you are calling the size() method on a LinkedList, which means the code scans the entire list every time.

So, my suggestion to you is to convert your LinkedLists to ArrayLists. ArrayList will take less space, and it has constant-time size() performance.

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. LinkedList.isEmpty() is O(1), but LinkedList.size() is O(n)

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<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)
 {
 return OrientedQuery(queryArea, new LinkedList<T>());
 }

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?