Package micycle.trapmap

Class TrapMap

  • public class TrapMap
extends Object
    TrapMap — a Trapezoidal Map library for fast point location queries.

    TrapMap pre-processes a partitioning of the plane (given as individual line segments, or polygons), decomposing regions into simpler trapezoidal cells upon which a search structure (a directed acyclic graph) is constructed. This structure facilitates the search of the trapezoid (hence the region) containing a query point in O(log n) time. The trapezoidal map and the search structure are built via randomized incremental construction.

    Author:
    Tyler Chenhall (core algorithm), Michael Carleton (improvements)

    • Constructor Detail

      • TrapMap

        public TrapMap​(Collection<Segment> segments)
        Builds a trapezoidal map from a collection of line segments (or a planar straight-line graph).

        The collection of segments should follow this criteria:

        • Segments are non-crossing
        • Segment interiors are disjoint, but segments may meet at endpoints (to allow closed figures)

        The map structure (a partitioning of the plane into neighboring trapezoids) and the search structure (a directed graph) are both built upon object construction. Use findFaceTrapezoids() with this constructor to find the the group of trapezoids that make a single face.

        Parameters:
        segments - a list of line segments from which to build a trapezoidal map

      • TrapMap

        public TrapMap​(List<processing.core.PShape> polygons)
        Builds a trapezoidal map from a collection of polygonal shapes.

        Shapes should not overlap, however they can share edges.

        When a TrapMap is constructed from polygons, calling findFace() for a query point will return a reference to the original PShape object in which the point is contained.

        The map structure (a partitioning of the plane into neighboring trapezoids) and the search structure (a directed graph) are both built upon object construction.

        Parameters:
        polygons - a list of disjoint polygonal shapes. Shapes may share edges / touch (forming a 'Planar graph') but interiors cannot overlap. assuming non-nested/non-overlapping polygons (mesh-like, at most (if share edges)

    • Method Detail

      • findNearestTrapezoid

        public Trapezoid findNearestTrapezoid​(double x,
                                      double y)
        Locates the trapezoid which contains the query point. If the point does not lie inside any trapezoid, the nearest trapezoid to the point is returned.

        This method is identical to findContainingTrapezoid(), except for the case where the point does not lie inside any trapezoid.

        Parameters:
        x - x-coordinate of query point
        y - y-coordinate of query point
        Returns:
        the trapezoid that contains the query point (or the nearest trapezoid if none contain the point)

      • findContainingTrapezoid

        public Trapezoid findContainingTrapezoid​(double x,
                                         double y)
        Locates the trapezoid which contains the query point. If the point does not lie inside any trapezoid, null is returned.

        This method is identical to findNearestTrapezoid(), except for the case where the point does not lie inside any trapezoid.

        Parameters:
        x - x-coordinate of query point
        y - y-coordinate of query point
        Returns:
        the trapezoid that contains the query point (or NULL if none contain the point)

      • findFaceTrapezoids

        public Set<Trapezoid> findFaceTrapezoids​(double x,
                                         double y)
        Finds the group of trapezoids that make up the face that contains the query point.

        Use this method to find faces that emerge from the plane when it is paritioned using line segments (when the TrapMap has been constructed from line segments).

        Parameters:
        x - x-coordinate of query point
        y - y-coordinate of query point
        Returns:
        a set of faces that make up the face that contains the query point. The set is empty when the point is not contained in any face.

      • findContainingPolygon

        public processing.core.PShape findContainingPolygon​(double x,
                                                    double y)
        Locates the polygon which contains the query point.

        This method returns a reference to one of the polygons provided to the TrapMap(List<>) constructor (if this constructor was used); if the TrapMap was constructed from line segments, this method will always return null — use findFaceTrapezoids() instead.

        Parameters:
        x - x-coordinate of query point
        y - y-coordinate of query point
        Returns:
        polygon which contains the query point; otherwise null if no polygon contains the point

      • getAllTrapezoids

        public List<Trapezoid> getAllTrapezoids()
        Returns all the trapezoids contained in the trapezoid map.
        Returns:
        list of all trapezoids