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>        /// The root QuadTreeNode        /// </summary>        QuadTreeNode<T> m_root;        /// <summary>        /// The bounds of this QuadTree        /// </summary>        OBB2D m_rectangle;        List<T> results = new LinkedList<T>();        public QuadTree(OBB2D rectangle)        {            m_rectangle = rectangle;            m_root = new QuadTreeNode<T>(m_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);        }    }Nodepublic class QuadTreeNode<T extends Entity>{    /// <summary>    /// Construct a quadtree node with the given bounds     /// </summary>    /// <param name=area></param>    public QuadTreeNode(OBB2D bounds)    {        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>    List<T> m_contents = new LinkedList<T>();    /// <summary>    /// The child nodes of the QuadTree    /// </summary>    List<QuadTreeNode<T>> m_nodes = new LinkedList<QuadTreeNode<T>>();    /// <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;        for(QuadTreeNode<T> node : m_nodes)            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)    {            for (QuadTreeNode<T> node : m_nodes)                node.SubTreeContents(results);            results.addAll(this.Contents());            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        // it's four sub-quads. Iterate through the items in this quad         // to see if they intersect.        for (T item : this.Contents())        {            if (queryArea.overlaps(item.getRect()))                results.add(item);        }        for (QuadTreeNode<T> node : m_nodes)        {            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             // the other quads            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            // quads            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        for (QuadTreeNode<T> node : m_nodes)        {            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.        this.Contents().add(item);    }    /// <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);        m_nodes.add(new QuadTreeNode<T>(                new OBB2D(m_bounds.getBoundingRect().left + quarterWidth,                         m_bounds.getBoundingRect().top + quarterHeight, halfWidth,halfHeight)));        m_nodes.add(new QuadTreeNode<T>(                new OBB2D(m_bounds.getBoundingRect().left,                        m_bounds.getBoundingRect().top + halfHeight + quarterHeight,                         halfWidth,halfHeight)));        m_nodes.add(new QuadTreeNode<T>(                new OBB2D(m_bounds.getBoundingRect().left + halfWidth + quarterWidth,                        m_bounds.getBoundingRect().top + quarterHeight, halfWidth,halfHeight)));        m_nodes.add(new QuadTreeNode<T>(                new OBB2D(m_bounds.getBoundingRect().left + halfWidth + quarterWidth,                        m_bounds.getBoundingRect().top + halfHeight + quarterHeight,                        halfWidth, halfHeight)));    }}
Not getting Log(n) performance from quadtree
java;optimization;performance;complexity