Package micycle.pgs

Class PGS_SegmentSet

java.lang.Object
micycle.pgs.PGS_SegmentSet
public class PGS_SegmentSet extends Object
Generation of random sets of non-intersecting line segments (and associated functions).

Methods in this class output segments as collections of PEdges; such collections can be converted into LINES PShapes with toPShape(edges).

Since:
1.3.0
Author:
Michael Carleton

  • Method Summary

    Modifier and Type
    Method
    Description
    static processing.core.PShape
    dissolve(Collection<micycle.pgs.commons.PEdge> segments)
    Dissolves the edges from a collection of PEdges into a set of maximal-length LineStrings in which each unique segment appears only once.
    static List<micycle.pgs.commons.PEdge>
    filterAxisAligned(List<micycle.pgs.commons.PEdge> segments, double angleDelta)
    Removes axis-aligned (horizontal and vertical) segments (within a given angle tolerance) from a collection of segments.
    static List<micycle.pgs.commons.PEdge>
    filterByAverageLength(List<micycle.pgs.commons.PEdge> segments, double fraction)
    Removes segments having a length either less than some fraction or more than 1/fraction of the mean segment length from a collection of segments.
    static List<micycle.pgs.commons.PEdge>
    filterByMinLength(List<micycle.pgs.commons.PEdge> segments, double minLength)
    Removes segments having a length less than the given length from a collection of segmensts.
    static List<micycle.pgs.commons.PEdge>
    filterNear(List<micycle.pgs.commons.PEdge> segments, double distance)
    Removes segments that are near others.
    static List<micycle.pgs.commons.PEdge>
    fromPShape(processing.core.PShape shape)
    Extracts a list of unique PEdge segments representing the given shape.
    static List<micycle.pgs.commons.PEdge>
    getPolygonInteriorSegments(List<micycle.pgs.commons.PEdge> segments, processing.core.PShape shape)
    Retains line segments from a set of line segments that are wholly contained within a given shape.
    static List<micycle.pgs.commons.PEdge>
    graphMatchedSegments(double width, double height, int n, long seed)
    Generates N non-intersecting segments via a Perfect matching algorithm applied to a triangulation populated with random points.
    static List<micycle.pgs.commons.PEdge>
    graphMatchedSegments(List<processing.core.PVector> points)
    Generates non-intersecting segments via a Perfect matching algorithm applied to a triangulation populated with the given points.
    static List<micycle.pgs.commons.PEdge>
    graphMatchedSegments(org.tinfour.common.IIncrementalTin triangulation)
    Generates non-intersecting segments via a Perfect matching algorithm applied to the given triangulation.
    static List<processing.core.PVector>
    intersections(Collection<micycle.pgs.commons.PEdge> edgesA, Collection<micycle.pgs.commons.PEdge> edgesB)
    Computes all intersection points between two collections of line segments.
    static List<micycle.pgs.commons.PEdge>
    nodedSegments(double width, double height, int n, long seed)
    Generates N non-intersecting segments via intersection and noding.
    static List<micycle.pgs.commons.PEdge>
    parallelSegments(double centerX, double centerY, double length, double spacing, double angle, int n)
    Generates a set of N straight parallel segments, centered on a given point.
    static List<micycle.pgs.commons.PEdge>
    stochasticSegments(double width, double height, int n)
    Generates a set of N random non-intersecting line segments via brute-forcing.
    static List<micycle.pgs.commons.PEdge>
    stochasticSegments(double width, double height, int n, double length)
    Generates a set of N random non-intersecting line segments of the given length via brute-forcing.
    static List<micycle.pgs.commons.PEdge>
    stochasticSegments(double width, double height, int n, double minLength, double maxLength, long seed)
    Generates a set of N random non-intersecting line segments via brute-forcing.
    static List<micycle.pgs.commons.PEdge>
    stretch(List<micycle.pgs.commons.PEdge> segments, double factor)
    Stretches each PEdge segment in the provided list by a specified factor.
    static Map<micycle.pgs.commons.PEdge,Integer>
    toBag(List<micycle.pgs.commons.PEdge> edges)
     
    static processing.core.PShape
    toPShape(Collection<micycle.pgs.commons.PEdge> segments)
    Converts a collection of PEdges into a LINES shape.
    static processing.core.PShape
    toPShape(Collection<micycle.pgs.commons.PEdge> segments, Integer strokeColor, Integer strokeCap, Integer strokeWeight)
    Converts a collection of PEdges into a LINES shape, having the (optional) styling provided.

    Methods inherited from class java.lang.Object

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

  • Method Details

    • nodedSegments

      public static List<micycle.pgs.commons.PEdge> nodedSegments(double width, double height, int n, long seed)
      Generates N non-intersecting segments via intersection and noding.

      The segments are generated within a bounding box anchored at (0, 0) having the width and height specified.

      Algorithm:

      • Generate a set of N random segments (will have many intersections)
      • Node the random segment set and split segments at intersections
      • Shrink split segments by ~30% (to increase distance between each other)
      • The split segments will be very numerous; sort by length and return the longest N segments
      Parameters:
      width - width of the bounds in which to generate segments; segment x coordinates will not be greater than this value
      height - height of the bounds in which to generate segments; segment y coordinates will not be greater than this value
      n - number of segments to generate
      seed - number used to initialize the underlying pseudorandom number generator
      Returns:
      set of N random non-intersecting line segments

    • graphMatchedSegments

      public static List<micycle.pgs.commons.PEdge> graphMatchedSegments(double width, double height, int n, long seed)
      Generates N non-intersecting segments via a Perfect matching algorithm applied to a triangulation populated with random points.

      The segments are generated within a bounding box anchored at (0, 0) having the width and height specified.

      The graphMatchedSegments methods are arguably the best approaches for random segment set generation.

      Parameters:
      width - width of the bounds in which to generate segments; segment x coordinates will not be greater than this value
      height - height of the bounds in which to generate segments; segment y coordinates will not be greater than this value
      n - number of segments to generate
      seed - number used to initialize the underlying pseudorandom number generator
      Returns:
      set of N random non-intersecting line segments

    • graphMatchedSegments

      public static List<micycle.pgs.commons.PEdge> graphMatchedSegments(List<processing.core.PVector> points)
      Generates non-intersecting segments via a Perfect matching algorithm applied to a triangulation populated with the given points.

      Generates N/2 segments, where N is the number of points in the input. If the number of points is odd, the last point is discarded.

      The graphMatchedSegments methods are arguably the best approaches for random segment set generation.

      Parameters:
      points - point set from which to compute segments
      Returns:
      set of non-intersecting line segments

    • graphMatchedSegments

      public static List<micycle.pgs.commons.PEdge> graphMatchedSegments(org.tinfour.common.IIncrementalTin triangulation)
      Generates non-intersecting segments via a Perfect matching algorithm applied to the given triangulation.

      Generates N/2 segments, where N is the number of vertices in the triangulation. If the number of points is odd, the last point is discarded.

      The graphMatchedSegments methods are arguably the best approaches for random segment set generation.

      Parameters:
      triangulation - triangulation object to use for vertices and graph connectivity
      Returns:
      set of non-intersecting line segments

    • stochasticSegments

      public static List<micycle.pgs.commons.PEdge> stochasticSegments(double width, double height, int n)
      Generates a set of N random non-intersecting line segments via brute-forcing. Plentifully fast enough for many applications.

      The segments are generated within a bounding box anchored at (0, 0) having the width and height specified.

      Parameters:
      width - width of the bounds in which to generate segments; segment x coordinates will not be greater than this value
      height - height of the bounds in which to generate segments; segment y coordinates will not be greater than this value
      n - number of segments to generate
      Returns:
      set of N random non-intersecting line segments
      See Also:

    • stochasticSegments

      public static List<micycle.pgs.commons.PEdge> stochasticSegments(double width, double height, int n, double length)
      Generates a set of N random non-intersecting line segments of the given length via brute-forcing. Plentifully fast enough for many applications.

      The segments are generated within a bounding box anchored at (0, 0) having the width and height specified.

      Parameters:
      width - width of the bounds in which to generate segments; segment x coordinates will not be greater than this value
      height - height of the bounds in which to generate segments; segment y coordinates will not be greater than this value
      n - number of segments to generate
      length - segment length (for all segments)
      Returns:
      set of N random non-intersecting line segments
      See Also:

    • stochasticSegments

      public static List<micycle.pgs.commons.PEdge> stochasticSegments(double width, double height, int n, double minLength, double maxLength, long seed)
      Generates a set of N random non-intersecting line segments via brute-forcing. Plentifully fast enough for many applications.

      The segments are generated within a bounding box anchored at (0, 0) having the width and height specified.

      Parameters:
      width - width of the bounds in which to generate segments; segment x coordinates will not be greater than this value
      height - height of the bounds in which to generate segments; segment y coordinates will not be greater than this value
      n - number of segments to generate
      minLength - minimum segment length (inclusive)
      maxLength - maximum segment length (exclusive)
      seed - number used to initialize the underlying pseudorandom number generator
      Returns:
      set of N random non-intersecting line segments

    • parallelSegments

      public static List<micycle.pgs.commons.PEdge> parallelSegments(double centerX, double centerY, double length, double spacing, double angle, int n)
      Generates a set of N straight parallel segments, centered on a given point.
      Parameters:
      centerX - the x coordinate of the center of the segments arrangment
      centerY - the y coordinate of the center of the segments arrangment
      length - length of each segment
      spacing - distance between successive segments
      angle - line angle in radians, where 0 is parallel to x-axis (horizontal)
      n - number of segments to generate. if odd then the middle segment lies on the center point; if even, then the first two segments are spaced evenly from the center point
      Returns:
      set of N parallel line segments

    • toPShape

      public static processing.core.PShape toPShape(Collection<micycle.pgs.commons.PEdge> segments)
      Converts a collection of PEdges into a LINES shape.
      Parameters:
      segments - collection of segments
      Returns:
      LINES shape representing segments

    • toPShape

      public static processing.core.PShape toPShape(Collection<micycle.pgs.commons.PEdge> segments, @Nullable Integer strokeColor, @Nullable Integer strokeCap, @Nullable Integer strokeWeight)
      Converts a collection of PEdges into a LINES shape, having the (optional) styling provided.
      Parameters:
      segments - collection of PEdge segments
      strokeColor - nullable/optional (default = Colors.PINK)
      strokeCap - nullable/optional (default = ROUND)
      strokeWeight - nullable/optional (default = 2)
      Returns:
      shape representing segments

    • toBag

      public static Map<micycle.pgs.commons.PEdge,Integer> toBag(List<micycle.pgs.commons.PEdge> edges)

    • dissolve

      public static processing.core.PShape dissolve(Collection<micycle.pgs.commons.PEdge> segments)
      Dissolves the edges from a collection of PEdges into a set of maximal-length LineStrings in which each unique segment appears only once. This method works by fusing segments that share endpoints into longer linear strings.

      This method may be preferred to toPShape() when the input segments form a linear string(s).

      Parameters:
      segments - Collection of PEdge objects to dissolve into maximal-length LineStrings
      Returns:
      A PShape object representing the dissolved LineStrings
      Since:
      1.4.0

    • intersections

      public static List<processing.core.PVector> intersections(Collection<micycle.pgs.commons.PEdge> edgesA, Collection<micycle.pgs.commons.PEdge> edgesB)
      Computes all intersection points between two collections of line segments.

      Given two collections of edges, this method finds and returns all points where a segment from the first collection intersects with a segment from the second collection, including intersection endpoints if applicable.

      Parameters:
      edgesA - the first collection of line segments to compare
      edgesB - the second collection of line segments to compare
      Returns:
      a list of PVector representing all intersection points found between the two collections of segments
      Since:
      2.1

    • fromPShape

      public static List<micycle.pgs.commons.PEdge> fromPShape(processing.core.PShape shape)
      Extracts a list of unique PEdge segments representing the given shape.

      This method iterates through all the child shapes of the input shape, creating PEdge segments for each pair of consecutive vertices.

      Parameters:
      shape - The shape from which to extract the edges. Supports holes and GROUP shapes.
      Returns:
      A list of unique PEdge segments representing the edges of the input shape and its child shapes.
      Since:
      1.4.0

    • stretch

      public static List<micycle.pgs.commons.PEdge> stretch(List<micycle.pgs.commons.PEdge> segments, double factor)
      Stretches each PEdge segment in the provided list by a specified factor. The stretch is applied by scaling the distance between the edge's vertices, while keeping the midpoint of the edge constant.
      Parameters:
      segments - The list of PEdges to be stretched.
      factor - The factor by which to stretch each PEdge. A value greater than 1 will stretch the edges, while a value between 0 and 1 will shrink them.
      Returns:
      A new List of PEdges representing the stretched edges.
      Since:
      1.4.0

    • filterByMinLength

      public static List<micycle.pgs.commons.PEdge> filterByMinLength(List<micycle.pgs.commons.PEdge> segments, double minLength)
      Removes segments having a length less than the given length from a collection of segmensts.
      Parameters:
      segments - list of segments to filter
      minLength - the minimum segment length to keep
      Returns:
      a filtered copy of input collection

    • filterByAverageLength

      public static List<micycle.pgs.commons.PEdge> filterByAverageLength(List<micycle.pgs.commons.PEdge> segments, double fraction)
      Removes segments having a length either less than some fraction or more than 1/fraction of the mean segment length from a collection of segments.

      This method can be used to homogenise a segment set.

      Parameters:
      segments - list of segments to filter
      fraction - fraction of mean length to keep segments
      Returns:
      a filtered copy of input collection

    • filterAxisAligned

      public static List<micycle.pgs.commons.PEdge> filterAxisAligned(List<micycle.pgs.commons.PEdge> segments, double angleDelta)
      Removes axis-aligned (horizontal and vertical) segments (within a given angle tolerance) from a collection of segments.
      Parameters:
      segments - list of segments to filter
      angleDelta - angle tolerance, in radians
      Returns:
      a filtered copy of the input where axis-aligned segments have been removed

    • filterNear

      public static List<micycle.pgs.commons.PEdge> filterNear(List<micycle.pgs.commons.PEdge> segments, double distance)
      Removes segments that are near others. More specifically, removes any segment that lies closer than a given threshold to a previously retained segment.

      This method uses a simple greedy, O(n²) algorithm: it iterates through the input segments in order, keeps the first segment unconditionally, and for each subsequent segment rejects it if its distance to any segment already in the output list is less than distance.

      Parameters:
      segments - the list of segments to filter.
      distance - the minimum allowed distance between any two segments in the returned list; must be non-negative.
      Returns:
      a new List containing those segments from the input (in original order) such that each pair of segments in the returned list is at least distance apart.
      Since:
      2.1

    • getPolygonInteriorSegments

      public static List<micycle.pgs.commons.PEdge> getPolygonInteriorSegments(List<micycle.pgs.commons.PEdge> segments, processing.core.PShape shape)
      Retains line segments from a set of line segments that are wholly contained within a given shape.
      Parameters:
      segments - a list of line segments to check for containment within the shape
      shape - the polygonal shape to check for interior segments
      Returns:
      a list of interior segments contained within the shape
      Since:
      1.4.0