Package com.esri.core.geometry
Class QuadTreeImpl
- java.lang.Object
-
- com.esri.core.geometry.QuadTreeImpl
-
- All Implemented Interfaces:
java.io.Serializable
class QuadTreeImpl extends java.lang.Object implements java.io.Serializable
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
QuadTreeImpl.Data
(package private) static class
QuadTreeImpl.QuadTreeIteratorImpl
(package private) static class
QuadTreeImpl.QuadTreeSortedIteratorImpl
-
Field Summary
Fields Modifier and Type Field Description private boolean
m_b_store_duplicates
private java.util.ArrayList<QuadTreeImpl.Data>
m_data
private Envelope2D
m_data_extent
private StridedIndexTypeCollection
m_element_nodes
private Envelope2D
m_extent
private static int
m_flushing_count
private AttributeStreamOfInt32
m_free_data
private int
m_height
private static int
m_height_bit_shift
private StridedIndexTypeCollection
m_quad_tree_nodes
private static int
m_quadrant_mask
private int
m_root
private static long
serialVersionUID
-
Constructor Summary
Constructors Constructor Description QuadTreeImpl(Envelope2D extent, int height)
Creates a Quad_tree_impl with the root having the extent of the input Envelope_2D, and height of the input height, where the root starts at height 0.QuadTreeImpl(Envelope2D extent, int height, boolean b_store_duplicates)
Creates a Quad_tree_impl with the root having the extent of the input Envelope_2D, and height of the input height, where the root starts at height 0.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private boolean
can_flush_(int quad_handle)
private boolean
can_push_down_(int quad_handle)
private int
create_child_(int parent, int quadrant)
private int
create_element_()
private int
create_element_from_duplicate_(int duplicate_element_handle)
private void
create_root_()
private void
disconnect_element_handle_(int element_handle)
long
estimateMemorySize()
private void
flush_(int height, Envelope2D extent, int quad_handle)
private void
free_element_and_box_node_(int element_handle)
private Envelope2D
get_bounding_box_value_(int data_handle)
private int
get_child_(int quad_handle, int quadrant)
private int
get_contained_sub_tree_element_count_(int quad_handle)
private int
get_data_(int element_handle)
private int
get_element_value_(int data_handle)
private int
get_first_element_(int quad_handle)
private int
get_height_(int quad_handle)
private int
get_last_element_(int quad_handle)
private int
get_local_element_count_(int quad_handle)
private int
get_next_element_(int element_handle)
private int
get_parent_(int child)
private int
get_prev_element_(int element_handle)
private int
get_quad_(int element_handle)
private int
get_quadrant_(int quad_handle)
private int
get_sub_tree_element_count_(int quad_handle)
(package private) int
getContainedSubTreeElementCount(int quad_handle)
Returns the number of elements contained in the subtree rooted at the given quad_handle.(package private) Envelope2D
getDataExtent()
Returns the extent of all elements in the quad tree.(package private) int
getElement(int element_handle)
Returns the element at the given element_handle.(package private) int
getElementAtIndex(int i)
Returns the ith unique element.(package private) int
getElementCount()
Returns the number of elements in the Quad_tree_impl.(package private) Envelope2D
getElementExtent(int element_handle)
Returns the element extent at the given element_handle.(package private) Envelope2D
getElementExtentAtIndex(int i)
Returns the extent of the ith unique element.(package private) Envelope2D
getExtent(int quad_handle)
Returns the extent of the quad at the given quad_handle.(package private) int
getHeight(int quad_handle)
Returns the height of the quad at the given quad_handle.(package private) int
getIntersectionCount(Envelope2D query, double tolerance, int max_count)
Returns the number of elements in the quad tree that intersect the qiven query.(package private) QuadTreeImpl.QuadTreeIteratorImpl
getIterator()
Gets an iterator on the Quad_tree.(package private) QuadTreeImpl.QuadTreeIteratorImpl
getIterator(Envelope2D query, double tolerance)
Gets an iterator on the Quad_tree_impl using the input Envelope_2D as the query.(package private) QuadTreeImpl.QuadTreeIteratorImpl
getIterator(Geometry query, double tolerance)
Gets an iterator on the Quad_tree_impl.(package private) int
getMaxHeight()
(package private) int
getQuad(int element_handle)
Returns the Quad_handle of the quad containing the given element_handle.(package private) Envelope2D
getQuadTreeExtent()
Returns the extent of the quad tree.(package private) QuadTreeImpl.QuadTreeSortedIteratorImpl
getSortedIterator()
Gets a sorted iterator on the Quad_tree.(package private) QuadTreeImpl.QuadTreeSortedIteratorImpl
getSortedIterator(Envelope2D query, double tolerance)
Gets a sorted iterator on the Quad_tree_impl using the input Envelope_2D as the query.(package private) QuadTreeImpl.QuadTreeSortedIteratorImpl
getSortedIterator(Geometry query, double tolerance)
Gets a sorted iterator on the Quad_tree_impl.(package private) int
getSubTreeElementCount(int quad_handle)
Returns the number of elements in the subtree rooted at the given quad_handle.private boolean
has_children_(int parent)
(package private) boolean
hasData(Envelope2D query, double tolerance)
Returns true if the quad tree has data intersecting the given query.(package private) int
insert(int element, Envelope2D bounding_box)
Inserts the element and bounding_box into the Quad_tree_impl.(package private) int
insert(int element, Envelope2D bounding_box, int hint_index)
Inserts the element and bounding_box into the Quad_tree_impl at the given quad_handle.private int
insert_(int element, Envelope2D bounding_box, int height, Envelope2D quad_extent, int quad_handle, boolean b_flushing, int flushed_element_handle)
private int
insert_at_quad_(int element, Envelope2D bounding_box, int current_height, Envelope2D current_extent, int current_quad_handle, boolean b_flushing, int quad_handle, int flushed_element_handle, int duplicate_element_handle)
private int
insert_duplicates_(int element, Envelope2D bounding_box, int height, Envelope2D quad_extent, int quad_handle, boolean b_flushing, int flushed_element_handle)
private void
readObject(java.io.ObjectInputStream stream)
private void
readObjectNoData()
(package private) void
removeElement(int element_handle)
Removes the element and bounding_box at the given element_handle.(package private) void
reset(Envelope2D extent, int height)
Resets the Quad_tree_impl to the given extent and height.private void
reset_(Envelope2D extent, int height)
private void
set_child_(int parent, int quadrant, int child)
private static void
set_child_extents_(Envelope2D current_extent, Envelope2D[] child_extents)
private void
set_contained_sub_tree_element_count_(int quad_handle, int count)
private void
set_data_(int element_handle, int data_handle)
private void
set_data_values_(int data_handle, int element, Envelope2D bounding_box)
private void
set_first_element_(int quad_handle, int head)
private void
set_height_and_quadrant_(int quad_handle, int height, int quadrant)
private void
set_last_element_(int quad_handle, int tail)
private void
set_local_element_count_(int quad_handle, int count)
private void
set_next_element_(int element_handle, int next_handle)
private void
set_parent_(int child, int parent)
private void
set_prev_element_(int element_handle, int prev_handle)
private void
set_quad_(int element_handle, int parent)
private void
set_sub_tree_element_count_(int quad_handle, int count)
private void
writeObject(java.io.ObjectOutputStream stream)
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
m_extent
private Envelope2D m_extent
-
m_data_extent
private Envelope2D m_data_extent
-
m_quad_tree_nodes
private StridedIndexTypeCollection m_quad_tree_nodes
-
m_element_nodes
private StridedIndexTypeCollection m_element_nodes
-
m_data
private transient java.util.ArrayList<QuadTreeImpl.Data> m_data
-
m_free_data
private AttributeStreamOfInt32 m_free_data
-
m_root
private int m_root
-
m_height
private int m_height
-
m_b_store_duplicates
private boolean m_b_store_duplicates
-
m_quadrant_mask
private static final int m_quadrant_mask
- See Also:
- Constant Field Values
-
m_height_bit_shift
private static final int m_height_bit_shift
- See Also:
- Constant Field Values
-
m_flushing_count
private static final int m_flushing_count
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
QuadTreeImpl
QuadTreeImpl(Envelope2D extent, int height)
Creates a Quad_tree_impl with the root having the extent of the input Envelope_2D, and height of the input height, where the root starts at height 0. \param extent The extent of the Quad_tree_impl. \param height The max height of the Quad_tree_impl.
-
QuadTreeImpl
QuadTreeImpl(Envelope2D extent, int height, boolean b_store_duplicates)
Creates a Quad_tree_impl with the root having the extent of the input Envelope_2D, and height of the input height, where the root starts at height 0. \param extent The extent of the Quad_tree_impl. \param height The max height of the Quad_tree_impl. \param b_store_duplicates Put true to place elements deeper into the quad tree at intesecting quads, duplicates will be stored. Put false to only place elements into quads that can contain it.
-
-
Method Detail
-
reset
void reset(Envelope2D extent, int height)
Resets the Quad_tree_impl to the given extent and height. \param extent The extent of the Quad_tree_impl. \param height The max height of the Quad_tree_impl.
-
insert
int insert(int element, Envelope2D bounding_box)
Inserts the element and bounding_box into the Quad_tree_impl. Note that this will invalidate any active iterator on the Quad_tree_impl. Returns an Element_handle corresponding to the element and bounding_box. \param element The element of the Geometry to be inserted. \param bounding_box The bounding_box of the Geometry to be inserted.
-
insert
int insert(int element, Envelope2D bounding_box, int hint_index)
Inserts the element and bounding_box into the Quad_tree_impl at the given quad_handle. Note that this will invalidate any active iterator on the Quad_tree_impl. Returns an Element_handle corresponding to the element and bounding_box. \param element The element of the Geometry to be inserted. \param bounding_box The bounding_box of the Geometry to be inserted. \param hint_index A handle used as a hint where to place the element. This can be a handle obtained from a previous insertion and is useful on data having strong locality such as segments of a Polygon.
-
removeElement
void removeElement(int element_handle)
Removes the element and bounding_box at the given element_handle. Note that this will invalidate any active iterator on the Quad_tree_impl. \param element_handle The handle corresponding to the element and bounding_box to be removed.
-
getElement
int getElement(int element_handle)
Returns the element at the given element_handle. \param element_handle The handle corresponding to the element to be retrieved.
-
getElementAtIndex
int getElementAtIndex(int i)
Returns the ith unique element. \param i The index corresponding to the ith unique element.
-
getElementExtent
Envelope2D getElementExtent(int element_handle)
Returns the element extent at the given element_handle. \param element_handle The handle corresponding to the element extent to be retrieved.
-
getElementExtentAtIndex
Envelope2D getElementExtentAtIndex(int i)
Returns the extent of the ith unique element. \param i The index corresponding to the ith unique element.
-
getDataExtent
Envelope2D getDataExtent()
Returns the extent of all elements in the quad tree.
-
getQuadTreeExtent
Envelope2D getQuadTreeExtent()
Returns the extent of the quad tree.
-
getHeight
int getHeight(int quad_handle)
Returns the height of the quad at the given quad_handle. \param quad_handle The handle corresponding to the quad.
-
getMaxHeight
int getMaxHeight()
-
getExtent
Envelope2D getExtent(int quad_handle)
Returns the extent of the quad at the given quad_handle. \param quad_handle The handle corresponding to the quad.
-
getQuad
int getQuad(int element_handle)
Returns the Quad_handle of the quad containing the given element_handle. \param element_handle The handle corresponding to the element.
-
getElementCount
int getElementCount()
Returns the number of elements in the Quad_tree_impl.
-
getSubTreeElementCount
int getSubTreeElementCount(int quad_handle)
Returns the number of elements in the subtree rooted at the given quad_handle. \param quad_handle The handle corresponding to the quad.
-
getContainedSubTreeElementCount
int getContainedSubTreeElementCount(int quad_handle)
Returns the number of elements contained in the subtree rooted at the given quad_handle. \param quad_handle The handle corresponding to the quad.
-
getIntersectionCount
int getIntersectionCount(Envelope2D query, double tolerance, int max_count)
Returns the number of elements in the quad tree that intersect the qiven query. Some elements may be duplicated if the quad tree stores duplicates. \param query The Envelope_2D used for the query. \param tolerance The tolerance used for the intersection tests. \param max_count If the intersection count becomes greater than or equal to the max_count, then max_count is returned.
-
hasData
boolean hasData(Envelope2D query, double tolerance)
Returns true if the quad tree has data intersecting the given query. \param query The Envelope_2D used for the query. \param tolerance The tolerance used for the intersection tests.
-
getIterator
QuadTreeImpl.QuadTreeIteratorImpl getIterator(Geometry query, double tolerance)
Gets an iterator on the Quad_tree_impl. The query will be the Envelope_2D that bounds the input Geometry. To reuse the existing iterator on the same Quad_tree_impl but with a new query, use the reset_iterator function on the Quad_tree_iterator_impl. \param query The Geometry used for the query. If the Geometry is a Line segment, then the query will be the segment. Otherwise the query will be the Envelope_2D bounding the Geometry. \param tolerance The tolerance used for the intersection tests.
-
getIterator
QuadTreeImpl.QuadTreeIteratorImpl getIterator(Envelope2D query, double tolerance)
Gets an iterator on the Quad_tree_impl using the input Envelope_2D as the query. To reuse the existing iterator on the same Quad_tree_impl but with a new query, use the reset_iterator function on the Quad_tree_iterator_impl. \param query The Envelope_2D used for the query. \param tolerance The tolerance used for the intersection tests.
-
getIterator
QuadTreeImpl.QuadTreeIteratorImpl getIterator()
Gets an iterator on the Quad_tree.
-
getSortedIterator
QuadTreeImpl.QuadTreeSortedIteratorImpl getSortedIterator(Geometry query, double tolerance)
Gets a sorted iterator on the Quad_tree_impl. The Element_handles will be returned in increasing order of their corresponding Element_types. The query will be the Envelope_2D that bounds the input Geometry. To reuse the existing iterator on the same Quad_tree_impl but with a new query, use the reset_iterator function on the Quad_tree_sorted_iterator_impl. \param query The Geometry used for the query. If the Geometry is a Line segment, then the query will be the segment. Otherwise the query will be the Envelope_2D bounding the Geometry. \param tolerance The tolerance used for the intersection tests.
-
getSortedIterator
QuadTreeImpl.QuadTreeSortedIteratorImpl getSortedIterator(Envelope2D query, double tolerance)
Gets a sorted iterator on the Quad_tree_impl using the input Envelope_2D as the query. The Element_handles will be returned in increasing order of their corresponding Element_types. To reuse the existing iterator on the same Quad_tree_impl but with a new query, use the reset_iterator function on the Quad_tree_iterator_impl. \param query The Envelope_2D used for the query. \param tolerance The tolerance used for the intersection tests.
-
getSortedIterator
QuadTreeImpl.QuadTreeSortedIteratorImpl getSortedIterator()
Gets a sorted iterator on the Quad_tree. The Element_handles will be returned in increasing order of their corresponding Element_types
-
estimateMemorySize
public long estimateMemorySize()
-
reset_
private void reset_(Envelope2D extent, int height)
-
insert_
private int insert_(int element, Envelope2D bounding_box, int height, Envelope2D quad_extent, int quad_handle, boolean b_flushing, int flushed_element_handle)
-
insert_duplicates_
private int insert_duplicates_(int element, Envelope2D bounding_box, int height, Envelope2D quad_extent, int quad_handle, boolean b_flushing, int flushed_element_handle)
-
insert_at_quad_
private int insert_at_quad_(int element, Envelope2D bounding_box, int current_height, Envelope2D current_extent, int current_quad_handle, boolean b_flushing, int quad_handle, int flushed_element_handle, int duplicate_element_handle)
-
set_child_extents_
private static void set_child_extents_(Envelope2D current_extent, Envelope2D[] child_extents)
-
disconnect_element_handle_
private void disconnect_element_handle_(int element_handle)
-
can_flush_
private boolean can_flush_(int quad_handle)
-
flush_
private void flush_(int height, Envelope2D extent, int quad_handle)
-
can_push_down_
private boolean can_push_down_(int quad_handle)
-
has_children_
private boolean has_children_(int parent)
-
create_child_
private int create_child_(int parent, int quadrant)
-
create_root_
private void create_root_()
-
create_element_
private int create_element_()
-
create_element_from_duplicate_
private int create_element_from_duplicate_(int duplicate_element_handle)
-
free_element_and_box_node_
private void free_element_and_box_node_(int element_handle)
-
get_child_
private int get_child_(int quad_handle, int quadrant)
-
set_child_
private void set_child_(int parent, int quadrant, int child)
-
get_first_element_
private int get_first_element_(int quad_handle)
-
set_first_element_
private void set_first_element_(int quad_handle, int head)
-
get_last_element_
private int get_last_element_(int quad_handle)
-
set_last_element_
private void set_last_element_(int quad_handle, int tail)
-
get_quadrant_
private int get_quadrant_(int quad_handle)
-
get_height_
private int get_height_(int quad_handle)
-
set_height_and_quadrant_
private void set_height_and_quadrant_(int quad_handle, int height, int quadrant)
-
get_local_element_count_
private int get_local_element_count_(int quad_handle)
-
set_local_element_count_
private void set_local_element_count_(int quad_handle, int count)
-
get_sub_tree_element_count_
private int get_sub_tree_element_count_(int quad_handle)
-
set_sub_tree_element_count_
private void set_sub_tree_element_count_(int quad_handle, int count)
-
get_parent_
private int get_parent_(int child)
-
set_parent_
private void set_parent_(int child, int parent)
-
get_contained_sub_tree_element_count_
private int get_contained_sub_tree_element_count_(int quad_handle)
-
set_contained_sub_tree_element_count_
private void set_contained_sub_tree_element_count_(int quad_handle, int count)
-
get_data_
private int get_data_(int element_handle)
-
set_data_
private void set_data_(int element_handle, int data_handle)
-
get_prev_element_
private int get_prev_element_(int element_handle)
-
get_next_element_
private int get_next_element_(int element_handle)
-
set_prev_element_
private void set_prev_element_(int element_handle, int prev_handle)
-
set_next_element_
private void set_next_element_(int element_handle, int next_handle)
-
get_quad_
private int get_quad_(int element_handle)
-
set_quad_
private void set_quad_(int element_handle, int parent)
-
get_element_value_
private int get_element_value_(int data_handle)
-
get_bounding_box_value_
private Envelope2D get_bounding_box_value_(int data_handle)
-
set_data_values_
private void set_data_values_(int data_handle, int element, Envelope2D bounding_box)
-
writeObject
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
- Throws:
java.io.IOException
-
readObject
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
- Throws:
java.io.IOException
java.lang.ClassNotFoundException
-
readObjectNoData
private void readObjectNoData() throws java.io.ObjectStreamException
- Throws:
java.io.ObjectStreamException
-
-