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