Package com.esri.core.geometry

Class QuadTreeImpl

  • All Implemented Interfaces:
    java.io.Serializable
    class QuadTreeImpl
extends java.lang.Object
implements java.io.Serializable

    • 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.

      • 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