Package com.github.micycle1.geoblitz

Class HPRtreeX<T>

java.lang.Object
com.github.micycle1.geoblitz.HPRtreeX<T>
Type Parameters:
T - the type of the items stored in the tree
public class HPRtreeX<T> extends Object
Improves the original JTS HPRTree implementation with eXtended features:
  • Generics support so the tree can store arbitrary user objects of type T.
  • Support for an early-exit item visitor to terminate spatial queries as soon as a condition is satisfied.
  • Efficient nearest-neighbor search using a best-first traversal with bounding-box pruning.
  • Efficient range query search.

Thread-safety notes:

  • build() is idempotent and uses internal synchronization so it is safe to call concurrently; the index will be prepared once.
  • After the index is built, read/query operations are safe (no modifications are performed). However, concurrent calls that attempt to insert after a build will throw an exception.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static interface 
    HPRtreeX.DistanceToItem<T>
    Functional interface used to compute the distance between a query coordinate and an item stored in the tree.
    static interface 
    HPRtreeX.ItemVisitor<T>
    Visitor interface used by query(Envelope, ItemVisitor) to process items that intersect a query envelope.

  • Constructor Summary

    Constructors
    Constructor
    Description
    HPRtreeX()
    Creates a new index using the default node capacity.
    HPRtreeX(int nodeCapacity)
    Creates a new index with the specified node capacity.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    build()
    Builds the internal spatial index structures from the items that have been inserted.
    org.locationtech.jts.geom.Envelope[]
    getBounds()
    Returns the extents (minimum bounding rectangles) of the internal index nodes.
    void
    insert(org.locationtech.jts.geom.Envelope itemEnv, T item)
    Inserts an item with its bounding envelope into the tree's insertion buffer.
    List<T>
    items()
     
    T
    nearestNeighbor(org.locationtech.jts.geom.Coordinate q, HPRtreeX.DistanceToItem<T> distFn)
    Finds and returns the item nearest to the query point q, according to the user-supplied distance function distFn.
    List<T>
    query(org.locationtech.jts.geom.Envelope searchEnv)
    Returns a list of items whose envelopes intersect the supplied search envelope.
    void
    query(org.locationtech.jts.geom.Envelope searchEnv, HPRtreeX.ItemVisitor<T> visitor)
    Visits all items whose envelopes intersect the supplied searchEnv, invoking the provided visitor for each matching item.
    List<T>
    rangeQuery(org.locationtech.jts.geom.Coordinate q, double maxDistance, HPRtreeX.DistanceToItem<T> distFn)
    Finds and returns all items whose distance to the query point q is less than or equal to the supplied maxDistance, according to the user-supplied distance function distFn.
    int
    size()
    Returns the number of items that have been inserted into this tree.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • HPRtreeX

      public HPRtreeX()
      Creates a new index using the default node capacity.

      The default node capacity is DEFAULT_NODE_CAPACITY. Newly created trees are initially empty and buffer inserted items in memory until the tree is built (explicitly by calling build() or implicitly when performing a query).

    • HPRtreeX

      public HPRtreeX(int nodeCapacity)
      Creates a new index with the specified node capacity.
      Parameters:
      nodeCapacity - the number of children stored per internal node (controls tree fanout and memory layout). Must be > 0. Larger values generally produce shallower trees but increase the per-node scan cost.

  • Method Details

    • size

      public int size()
      Returns the number of items that have been inserted into this tree.

      This count includes items that have been added but not yet bulk-loaded into the internal arrays (i.e. before build() is called).

      Returns:
      the number of inserted items

    • insert

      public void insert(org.locationtech.jts.geom.Envelope itemEnv, T item)
      Inserts an item with its bounding envelope into the tree's insertion buffer.

      Items may be inserted only until the index is built. Calling this method after build() has been invoked will throw an IllegalStateException.

      Parameters:
      itemEnv - the axis-aligned bounding envelope of the item (must not be null)
      item - the item to store
      Throws:
      IllegalStateException - if called after the tree has been built

    • query

      public List<T> query(org.locationtech.jts.geom.Envelope searchEnv)
      Returns a list of items whose envelopes intersect the supplied search envelope.

      The returned list contains all items that intersect searchEnv. The order of items in the returned list follows the internal node/item ordering (Hilbert-ordered blocks), but is not otherwise guaranteed.

      Calling this method will build the index if it has not already been built.

      Parameters:
      searchEnv - the query envelope
      Returns:
      a list of matching items; an empty list if no items intersect searchEnv

    • query

      public void query(org.locationtech.jts.geom.Envelope searchEnv, HPRtreeX.ItemVisitor<T> visitor)
      Visits all items whose envelopes intersect the supplied searchEnv, invoking the provided visitor for each matching item.

      Visiting order follows the internal node traversal order. The visitor may return false to request early termination of the traversal; in that case no further items will be visited.

      This method will build the index if it has not already been built.

      Parameters:
      searchEnv - the envelope to search
      visitor - a callback invoked for each matching item; returning false signals that the traversal should stop immediately

    • items

      public List<T> items()

    • build

      public void build()
      Builds the internal spatial index structures from the items that have been inserted.

      This method is idempotent and thread-safe: if multiple threads call build() concurrently the index will be prepared only once. Building performs sorting (Hilbert encoding) and allocates internal arrays; it can be relatively expensive for large datasets. If the tree contains no more than nodeCapacity items, no internal node structures are created and queries will operate by linear scan.

    • getBounds

      public org.locationtech.jts.geom.Envelope[] getBounds()
      Returns the extents (minimum bounding rectangles) of the internal index nodes.

      The returned array contains one Envelope per internal node in the index. The ordering corresponds to the internal node ordering used by this tree (i.e. the same index offsets used by queries and nearest-neighbor traversal). Each Envelope in the returned array is a newly created object and may be freely modified by the caller.

      Returns:
      an array of internal node envelopes, or an empty array if the index contains no internal nodes

    • nearestNeighbor

      public T nearestNeighbor(org.locationtech.jts.geom.Coordinate q, HPRtreeX.DistanceToItem<T> distFn)
      Finds and returns the item nearest to the query point q, according to the user-supplied distance function distFn.

      The HPRtreeX.DistanceToItem callback is used to compute the distance from the query coordinate to a stored item. The implementation performs a best-first traversal of the tree using bounding-box minimum-distance pruning; only items and nodes that can beat the current best distance are explored. If the index has no internal layers the search degenerates to a linear scan of all items.

      Notes and guarantees:

      • If the tree contains no items, null is returned.
      • distFn.distance should return a non-negative scalar; correctness of pruning assumes that the function is consistent with geometric distance ordering.
      • The returned object is the single item for which distFn.distance(q, item) is minimal (ties broken by traversal order).
      Parameters:
      q - the query coordinate
      distFn - a callback that computes the distance between q and an item
      Returns:
      the nearest item according to distFn, or null if the tree is empty

    • rangeQuery

      public List<T> rangeQuery(org.locationtech.jts.geom.Coordinate q, double maxDistance, HPRtreeX.DistanceToItem<T> distFn)
      Finds and returns all items whose distance to the query point q is less than or equal to the supplied maxDistance, according to the user-supplied distance function distFn.

      The HPRtreeX.DistanceToItem callback is used to compute the distance from the query coordinate to a stored item. The implementation performs a depth-first traversal of the tree using bounding-box minimum-distance pruning: only items and nodes whose minimum possible distance to q is ≤ maxDistance are explored. If the index has no internal layers the search degenerates to a linear scan of all items.

      Notes and guarantees:

      • If the tree contains no items, an empty list is returned.
      • If maxDistance is negative or NaN, an empty list is returned.
      • distFn.distance should return a non-negative scalar; correctness of pruning assumes that the function is consistent with geometric distance ordering.
      • All items for which distFn.distance(q, item) <= maxDistance will be returned (no false negatives); items with distance > maxDistance will not be returned (no false positives).
      • The returned list is not sorted by distance; its iteration order follows the traversal order used by the algorithm.
      Parameters:
      q - the query coordinate
      maxDistance - the inclusive distance threshold; must be non-negative to return any items
      distFn - a callback that computes the distance between q and an item
      Returns:
      a list of items whose distance to q is less than or equal to maxDistance; an empty list if none match or if the tree is empty or maxDistance is negative/NaN
      See Also: