Package com.github.micycle1.geoblitz

Class SegmentVoronoiIndex

java.lang.Object
com.github.micycle1.geoblitz.SegmentVoronoiIndex
public class SegmentVoronoiIndex extends Object
Approximate nearest-line-segment spatial index built from sample points taken along each segment and using the resulting Voronoi partition.

Build the index once (from a Polygon or a List<LineSegment>) and then answer nearest-segment queries quickly. The sampling spacing controls the trade-off between accuracy and build time: smaller spacing = higher accuracy, larger spacing = faster build and lower memory use.

Queries: nearestSegment(Coordinate) returns the original LineSegment whose Voronoi cell contains the point, or null if the point lies outside the configured clip envelope. distanceToNearestSegment(Coordinate) returns the Euclidean distance to that segment (or +Inf if none).

Limitations: this is an approximate index — results near boundaries may be affected by sampling density. The index is intended for read-only concurrent queries after construction; it is not designed for incremental modification.

Author:
Michael Carleton

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final class 
    SegmentVoronoiIndex.CellRecord
    A record containing the Voronoi cell polygon and its associated segment.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final HPRtreeX<SegmentVoronoiIndex.CellRecord>
    cellIndex
    The spatial index of Voronoi cells.
    List<List<org.locationtech.jts.geom.Polygon>>
    cellsList
    List of lists of polygons representing the cells.

  • Constructor Summary

    Constructors
    Constructor
    Description
    SegmentVoronoiIndex(List<org.locationtech.jts.geom.LineSegment> segments, org.locationtech.jts.geom.Envelope clipEnvelope, double sampleSpacing)
    Constructs a SegmentVoronoiIndex from an explicit list of line segments and builds a Voronoi-based approximate nearest-segment index.
    SegmentVoronoiIndex(org.locationtech.jts.geom.Polygon polygon, double sampleSpacing)
    Constructs a SegmentVoronoiIndex from the given polygon.
    SegmentVoronoiIndex(org.locationtech.jts.geom.Polygon polygon, org.locationtech.jts.geom.Envelope clipEnvelope, double sampleSpacing)
    Constructs a SegmentVoronoiIndex from the given polygon.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    distanceToNearestSegment(org.locationtech.jts.geom.Coordinate p)
    Returns the Euclidean distance from the given point to the nearest indexed line segment as determined by the Voronoi-based index.
    org.locationtech.jts.geom.LineSegment
    nearestSegment(org.locationtech.jts.geom.Coordinate p)
    Returns the original LineSegment whose Voronoi cell contains the given point.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • cellIndex

      public final HPRtreeX<SegmentVoronoiIndex.CellRecord> cellIndex
      The spatial index of Voronoi cells.

    • cellsList

      public List<List<org.locationtech.jts.geom.Polygon>> cellsList
      List of lists of polygons representing the cells.

  • Constructor Details

    • SegmentVoronoiIndex

      public SegmentVoronoiIndex(org.locationtech.jts.geom.Polygon polygon, double sampleSpacing)
      Constructs a SegmentVoronoiIndex from the given polygon. The index is built during construction and is ready for concurrent read-only queries after the constructor returns.

      The clip envelope used to clip the Voronoi diagram is computed from the polygon's envelope and expanded by one quarter of its diameter to reduce edge effects.

      Parameters:
      polygon - the polygon whose exterior ring will be converted to line segments and used to build the index (must not be null)
      sampleSpacing - maximum spacing (in coordinate units) between sample points along segments; smaller values increase accuracy and memory/time cost, larger values make the build faster and use less memory

    • SegmentVoronoiIndex

      public SegmentVoronoiIndex(org.locationtech.jts.geom.Polygon polygon, org.locationtech.jts.geom.Envelope clipEnvelope, double sampleSpacing)
      Constructs a SegmentVoronoiIndex from the given polygon. The index is built during construction and is ready for concurrent read-only queries after the constructor returns.

      The provided clipEnvelope is used to clip the Voronoi diagram instead of deriving one from the polygon.

      Parameters:
      polygon - the polygon whose rings will be converted to line segments and used to build the index (must not be null)
      clipEnvelope - the envelope that defines the region to cover; may be null to indicate no clipping
      sampleSpacing - maximum spacing (in coordinate units) between sample points along segments; smaller values increase accuracy and memory/time cost, larger values make the build faster and use less memory

    • SegmentVoronoiIndex

      public SegmentVoronoiIndex(List<org.locationtech.jts.geom.LineSegment> segments, org.locationtech.jts.geom.Envelope clipEnvelope, double sampleSpacing)
      Constructs a SegmentVoronoiIndex from an explicit list of line segments and builds a Voronoi-based approximate nearest-segment index. The index is built during construction and is ready for concurrent read-only queries after the constructor returns.

      The supplied list of segments is copied; segments may be provided in any order. If clipEnvelope is null, no clipping envelope is applied when constructing the Voronoi diagram.

      Parameters:
      segments - the list of LineSegment objects to index (must not be null; may be empty)
      clipEnvelope - the envelope that defines the region to cover; may be null to indicate no clipping
      sampleSpacing - maximum spacing (in coordinate units) between sample points along segments; smaller values increase accuracy and memory/time cost, larger values make the build faster and use less memory

  • Method Details

    • nearestSegment

      public org.locationtech.jts.geom.LineSegment nearestSegment(org.locationtech.jts.geom.Coordinate p)
      Returns the original LineSegment whose Voronoi cell contains the given point. If the point lies outside the configured clip envelope, null is returned.

      Note: this is an approximate index built from discrete samples along the segments; results for points near cell boundaries may depend on sampling density. The method is thread-safe for concurrent readers.

      Parameters:
      p - the query coordinate (must not be null)
      Returns:
      the LineSegment whose Voronoi cell contains the point, or null if the point lies outside the clip envelope or no containing cell was found

    • distanceToNearestSegment

      public double distanceToNearestSegment(org.locationtech.jts.geom.Coordinate p)
      Returns the Euclidean distance from the given point to the nearest indexed line segment as determined by the Voronoi-based index. If no nearest segment can be determined (for example, the point is outside the clip envelope), Double.POSITIVE_INFINITY is returned.

      This method delegates to nearestSegment(Coordinate) and then computes the distance to the returned segment.

      Parameters:
      p - the query coordinate (must not be null)
      Returns:
      the Euclidean distance to the nearest indexed LineSegment, or Double.POSITIVE_INFINITY if no segment was found