Package com.esri.core.geometry
Class QuadTreeImpl
java.lang.Object
com.esri.core.geometry.QuadTreeImpl
- All Implemented Interfaces:
Serializable
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static final class
(package private) static final class
(package private) static final class
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate boolean
private ArrayList
<QuadTreeImpl.Data> private Envelope2D
private StridedIndexTypeCollection
private Envelope2D
private static final int
private AttributeStreamOfInt32
private int
private static final int
private StridedIndexTypeCollection
private static final int
private int
private static final long
-
Constructor Summary
ConstructorsConstructorDescriptionQuadTreeImpl
(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
Modifier and TypeMethodDescriptionprivate boolean
can_flush_
(int quad_handle) private boolean
can_push_down_
(int quad_handle) private int
create_child_
(int parent, int quadrant) private int
private int
create_element_from_duplicate_
(int duplicate_element_handle) private void
private void
disconnect_element_handle_
(int element_handle) long
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
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
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
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
(package private) int
getQuad
(int element_handle) Returns the Quad_handle of the quad containing the given element_handle.(package private) Envelope2D
Returns the extent of the quad tree.(package private) QuadTreeImpl.QuadTreeSortedIteratorImpl
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
(ObjectInputStream stream) private void
(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
(ObjectOutputStream stream)
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
m_extent
-
m_data_extent
-
m_quad_tree_nodes
-
m_element_nodes
-
m_data
-
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:
-
m_height_bit_shift
private static final int m_height_bit_shift- See Also:
-
m_flushing_count
private static final int m_flushing_count- See Also:
-
-
Constructor Details
-
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 Details
-
reset
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
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
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
Returns the element extent at the given element_handle. \param element_handle The handle corresponding to the element extent to be retrieved. -
getElementExtentAtIndex
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
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
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
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
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
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
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
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_
-
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_
-
disconnect_element_handle_
private void disconnect_element_handle_(int element_handle) -
can_flush_
private boolean can_flush_(int quad_handle) -
flush_
-
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_
-
set_data_values_
-
writeObject
- Throws:
IOException
-
readObject
- Throws:
IOException
ClassNotFoundException
-
readObjectNoData
- Throws:
ObjectStreamException
-