Package org.apache.sis.index.tree
Class QuadTree
- Object
-
- 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.
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
getCapacity()
Returns the capacity of node in the quad tree.int
getDepth()
Returns the maximum depth of the quad tree.int
getNodeSize()
Returns the node size of the quad tree.int
getSize()
Returns the size of the quad tree.boolean
insert(QuadTreeData data)
Inserts the specified data into the quad tree.List<QuadTreeData>
queryByBoundingBox(Envelope2D searchRegion)
Performs bounding box search.List<QuadTreeData>
queryByPointRadius(DirectPosition2D point, double radiusKM)
Performs point radius search.void
setCapacity(int capacity)
Sets the capacity of node in the quad tree.void
setDepth(int depth)
Sets the maximum depth of the quad tree.void
setNodeSize(int nodeSize)
Sets the node size of the quad tree.void
setSize(int size)
Sets the size of the quad tree.int
size()
Returns the size of the quad tree.
-
-
-
Constructor Detail
-
QuadTree
public QuadTree(int capacity, int maxDepth)
Creates a quad tree.- Parameters:
capacity
- the capacity of each node in the quad treemaxDepth
- 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 regionradiusKM
- 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:
searchRegion
- 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:
nodeSize
- 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.
-
-