Class QuadTree


  • public class QuadTree
    extends Object
    Implementation of Quad Tree Index. Insertion algorithm implemented based on design of quad tree index in H. Samet, The Design and Analysis of Spatial Data Structures. Massachusetts: Addison Wesley Publishing Company, 1989.
    Note on future work: this class may change in incompatible way in a future Apache SIS release, or may be replaced by new API.
    • Constructor Detail

      • QuadTree

        public QuadTree​(int capacity,
                        int maxDepth)
        Creates a quad tree.
        Parameters:
        capacity - the capacity of each node in the quad tree
        max­Depth - the maximum depth of the tree
      • QuadTree

        public QuadTree()
        Creates a quad tree with 0 capacity and depth. Useful when user wants to set the capacity and depth after quad tree construction.
    • Method Detail

      • insert

        public boolean insert​(QuadTreeData data)
        Inserts the specified data into the quad tree.
        Parameters:
        data - specified data to be inserted
        Returns:
        true if the data was inserted into the quad tree; false if data cannot be inserted because the capacity of the node has been exceeded and the depth of the tree will be exceeded if we insert this data
      • queryByPointRadius

        public List<QuadTreeData> queryByPointRadius​(DirectPosition2D point,
                                                     double radiusKM)
        Performs point radius search.
        Parameters:
        point - the center of the circular region
        radius­KM - the radius in kilometers
        Returns:
        a list of QuadTreeData that are within the given radius from the point
      • queryByBoundingBox

        public List<QuadTreeData> queryByBoundingBox​(Envelope2D searchRegion)
        Performs bounding box search.
        Parameters:
        search­Region - Envelope representing the rectangular search region
        Returns:
        a list of QuadTreeData that are within the given radius from the point
      • size

        public int size()
        Returns the size of the quad tree.
        Returns:
        size of the quad tree.
      • setSize

        public void setSize​(int size)
        Sets the size of the quad tree.
        Parameters:
        size - The new quad tree size.
      • getSize

        public int getSize()
        Returns the size of the quad tree.
        Returns:
        size of quad tree
      • setNodeSize

        public void setNodeSize​(int nodeSize)
        Sets the node size of the quad tree.
        Parameters:
        node­Size - The new node size.
      • getNodeSize

        public int getNodeSize()
        Returns the node size of the quad tree.
        Returns:
        node size of the quad tree.
      • getCapacity

        public int getCapacity()
        Returns the capacity of node in the quad tree.
        Returns:
        capacity of node in the quad tree.
      • getDepth

        public int getDepth()
        Returns the maximum depth of the quad tree.
        Returns:
        maximum depth of the quad tree.
      • setCapacity

        public void setCapacity​(int capacity)
        Sets the capacity of node in the quad tree.
        Parameters:
        capacity - the capacity of node in the quad tree.
      • setDepth

        public void setDepth​(int depth)
        Sets the maximum depth of the quad tree.
        Parameters:
        depth - the maximum depth of the quad tree.