Package micycle.pgs.commons

Class VisibilityPolygon

java.lang.Object
micycle.pgs.commons.VisibilityPolygon
public class VisibilityPolygon extends Object
This class computes an isovist, which is the volume of space visible from a specific point in space, based on a given set of original segments.

The code in this class is adapted from Byron Knoll's javascript library, available at https://github.com/byronknoll/visibility-polygon-js

  • Sort all vertices based on their angle to the observer.
  • Iterate (angle sweep) through the sorted vertices.
  • For each vertex:
    • Imagine a ray projecting outwards from the observer towards that vertex.
    • Compute the closest "active" line segment to construct the visibility polygon.
    • The closest active line segment must be computed in O(log n) time for each vertex.
    • Use a special type of heap to keep track of all active line segments arranged by distance to the observer.
    • The closest line segment is at the root of the heap.
    • New segments can be inserted in O(log n) time.
    • Inactive line segments can be removed in O(log n) time.
    • Maintain a consistent distance ordering by removing inactive line segments from the heap.
    • The heap used in this class contains an additional map structure from element value to heap index, so elements can be found in O(1) time.
    • Once an element is found, swap in the last element in the tree and propagate it either up or down (which takes O(log n) time) to maintain heap correctness.
Author:
Nicolas Fortin of Ifsttar UMRAE, Small changes by Michael Carleton

  • Constructor Summary

    Constructors
    Constructor
    Description
    VisibilityPolygon()
     
    VisibilityPolygon(double maxDistance)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addGeometry(org.locationtech.jts.geom.Geometry geometry)
    Explode geometry and add occlusion segments in isovist
    void
    addLineString(org.locationtech.jts.geom.LineString lineString)
     
    void
    addSegment(org.locationtech.jts.geom.Coordinate p0, org.locationtech.jts.geom.Coordinate p1)
    Add an occlusion segment to the isovist.
    void
    fixSegments()
     
    double
    getEpsilon()
     
    org.locationtech.jts.geom.Geometry
    getIsovist(Collection<org.locationtech.jts.geom.Coordinate> viewPoints, boolean addEnvelope)
    Returns a polygonal geometry that represents the isovist for a collection of view points.
    org.locationtech.jts.geom.Polygon
    getIsovist(org.locationtech.jts.geom.Coordinate viewPoint, boolean addEnvelope)
    Computes an isovist, the area of the input visible from a given point in space.
    void
    setEpsilon(double epsilon)
     
    void
    setNumPoints(int numPoints)
     

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • VisibilityPolygon

      public VisibilityPolygon(double maxDistance)
      Parameters:
      maxDistance - maximum distance (from the view point) constraint for the visibility polygon

    • VisibilityPolygon

      public VisibilityPolygon()

  • Method Details

    • getIsovist

      public org.locationtech.jts.geom.Geometry getIsovist(Collection<org.locationtech.jts.geom.Coordinate> viewPoints, boolean addEnvelope)
      Returns a polygonal geometry that represents the isovist for a collection of view points. An isovist is the set of all points visible from a given point in a space, considering occlusions caused by the environment.
      Parameters:
      viewPoints - the collection of view points from which the isovist is computed.
      addEnvelope - a boolean flag indicating whether to include a circle bounding box in the resulting geometry.
      Returns:
      a polygonal geometry representing the isovist. The geometry returned may be a single polygon or a multipolygon comprising multiple disjoint polygons.

    • getIsovist

      public org.locationtech.jts.geom.Polygon getIsovist(org.locationtech.jts.geom.Coordinate viewPoint, boolean addEnvelope)
      Computes an isovist, the area of the input visible from a given point in space.
      Parameters:
      viewPoint - View coordinate
      addEnvelope - If true add circle bounding box. This function does not work properly if the view point is not enclosed by segments
      Returns:
      visibility polygon

    • fixSegments

      public void fixSegments()

    • setNumPoints

      public void setNumPoints(int numPoints)
      Parameters:
      numPoints - Number of points of the bounding circle polygon. Default = 96.

    • getEpsilon

      public double getEpsilon()

    • setEpsilon

      public void setEpsilon(double epsilon)

    • addGeometry

      public void addGeometry(org.locationtech.jts.geom.Geometry geometry)
      Explode geometry and add occlusion segments in isovist
      Parameters:
      geometry - Geometry collection, LineString or Polygon instance

    • addLineString

      public void addLineString(org.locationtech.jts.geom.LineString lineString)

    • addSegment

      public void addSegment(org.locationtech.jts.geom.Coordinate p0, org.locationtech.jts.geom.Coordinate p1)
      Add an occlusion segment to the isovist.
      Parameters:
      p0 - segment origin
      p1 - segment destination