Package micycle.pgs

Class PGS_Optimisation

java.lang.Object
micycle.pgs.PGS_Optimisation
public final class PGS_Optimisation extends Object
Solve geometric optimisation problems, such as bounding volumes, inscribed areas, optimal distances, etc.
Author:
Michael Carleton

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static enum 
    PGS_Optimisation.RectPackHeuristic
    Various packing heuristics for rectpack().

  • Method Summary

    Modifier and Type
    Method
    Description
    static processing.core.PShape
    binPack(List<processing.core.PShape> shapes, double binWidth, double binHeight, int binColumns, double spacing)
    Packs a list of irregular polygonal shapes into (potentially multiple) rectangular containers (bins), while attempting to minimise the occupied space of the packing.
    static List<processing.core.PVector>
    circleCoverage(processing.core.PShape shape, int n)
    Covers a polygon with n circles such that no circle’s center lies outside the polygon.
    static List<processing.core.PVector>
    circleCoverage(processing.core.PShape shape, int n, long seed)
    Covers a polygon with n circles such that no circle’s center lies outside the polygon.
    static processing.core.PVector
    closestPoint(processing.core.PShape shape, processing.core.PVector point)
    Returns the nearest point of the shape to the given point.
    static List<processing.core.PVector>
    closestPointPair(Collection<processing.core.PVector> points)
    Computes the closest pair of points in a set of points.
    static List<processing.core.PVector>
    closestPoints(processing.core.PShape shape, processing.core.PVector point)
    Returns the nearest point for each "island" / separate polygon in the GROUP input shape.
    static processing.core.PShape
    envelope(processing.core.PShape shape)
    Computes the shape's envelope (bounding box).
    static List<processing.core.PVector>
    farthestPointPair(Collection<processing.core.PVector> points)
    Computes the farthest pair of points (the "diametral pair") in a set of n points.
    static processing.core.PShape
    hilbertSortFaces(processing.core.PShape mesh)
    Sorts the faces/child shapes of a GROUP shape according to hilbert curve index of each face's centroid coordinate.
    static processing.core.PShape
    largestEmptyCircle(processing.core.PShape obstacles, double tolerance)
    Computes the largest empty circle that does not intersect any obstacles (up to a specified tolerance).
    static processing.core.PShape
    largestEmptyCircle(processing.core.PShape obstacles, processing.core.PShape boundary, double tolerance)
    Computes the largest empty circle that does not intersect any obstacles and lies within the specified boundary (up to a specified tolerance).
    static List<processing.core.PVector>
    largestEmptyCircles(processing.core.PShape obstacles, processing.core.PShape boundary, int n, double tolerance)
    Computes the n largest empty circles that do not intersect any obstacles (nor each other) within an optional boundary.
    static processing.core.PShape
    maximumInscribedAARectangle(processing.core.PShape shape, boolean fast)
    Finds the rectangle with a maximum area whose sides are parallel to the x-axis and y-axis ("axis-aligned"), contained/insribed within a convex shape.
    static processing.core.PShape
    maximumInscribedCircle(processing.core.PShape shape, double tolerance)
    The Maximum Inscribed Circle is determined by a point in the interior of the area which has the farthest distance from the area boundary, along with a boundary point at that distance.
    static processing.core.PShape
    maximumInscribedCircle(processing.core.PShape shape, processing.core.PVector centerPoint)
    Return the maximum circle (at a given centerpoint inside/outside the circle)
    static processing.core.PShape
    maximumInscribedRectangle(processing.core.PShape shape)
    Finds an approximate largest area rectangle (of arbitrary orientation) contained within a polygon.
    static processing.core.PShape
    maximumPerimeterSquare(processing.core.PShape shape, double tolerance)
    Finds the largest area perimeter square of the input.
    static processing.core.PShape
    minimumAreaRectangle(processing.core.PShape shape)
    Computes the minimum-area rectangle that encloses a shape.
    static processing.core.PShape
    minimumBoundingCircle(processing.core.PShape shape)
    Computes the Minimum Bounding Circle (MBC) for the points in a Geometry.
    static processing.core.PShape
    minimumBoundingEllipse(processing.core.PShape shape, double errorTolerance)
    Computes the minimum bounding ellipse that encloses a shape.
    static processing.core.PShape
    minimumBoundingTriangle(processing.core.PShape shape)
    Computes the minimum-area bounding triangle that encloses a shape.
    static processing.core.PShape
    minimumDiameter(processing.core.PShape shape)
    Computes the minimum diameter of a shape.
    static processing.core.PShape
    minimumWidthRectangle(processing.core.PShape shape)
    Computes the minimum-width bounding rectangle that encloses a shape.
    static processing.core.PShape
    rectPack(List<processing.core.PVector> rectangles, int binWidth, int binHeight, PGS_Optimisation.RectPackHeuristic heuristic)
    Packs a collection of rectangles, according to the given packing heuristic, into rectangular 2D bin(s).
    static processing.core.PVector
    solveApollonius(processing.core.PVector c1, processing.core.PVector c2, processing.core.PVector c3, int s1, int s2, int s3)
    Solves the Problem of Apollonius (finding a circle tangent to three other circles in the plane).
    static processing.core.PShape
    visibilityPolygon(processing.core.PShape obstacles, Collection<processing.core.PVector> viewPoints)
    Computes a visibility polygon / isovist, the area visible from a set of given points in space, considering occlusions caused by obstacles.
    static processing.core.PShape
    visibilityPolygon(processing.core.PShape obstacles, processing.core.PVector viewPoint)
    Computes a visibility polygon / isovist, the area visible from a given point in a space, considering occlusions caused by obstacles.

    Methods inherited from class java.lang.Object

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

  • Method Details

    • envelope

      public static processing.core.PShape envelope(processing.core.PShape shape)
      Computes the shape's envelope (bounding box). The vertices of the output PShape begin at the top-left corner of the envelope and are arranged counter-clockwise.
      Parameters:
      shape - a rectangular shape that covers/bounds the input
      Returns:
      polygonal shape having 4 coordinates

    • maximumInscribedCircle

      public static processing.core.PShape maximumInscribedCircle(processing.core.PShape shape, double tolerance)
      The Maximum Inscribed Circle is determined by a point in the interior of the area which has the farthest distance from the area boundary, along with a boundary point at that distance.
      Parameters:
      shape -
      tolerance - the distance tolerance for computing the centre point (around 1)

    • maximumInscribedCircle

      public static processing.core.PShape maximumInscribedCircle(processing.core.PShape shape, processing.core.PVector centerPoint)
      Return the maximum circle (at a given centerpoint inside/outside the circle)
      Parameters:
      shape -
      centerPoint -
      Returns:
      A circular PShape

    • maximumInscribedRectangle

      public static processing.core.PShape maximumInscribedRectangle(processing.core.PShape shape)
      Finds an approximate largest area rectangle (of arbitrary orientation) contained within a polygon.
      Parameters:
      shape -
      Returns:
      a rectangle shape
      See Also:

    • maximumInscribedAARectangle

      public static processing.core.PShape maximumInscribedAARectangle(processing.core.PShape shape, boolean fast)
      Finds the rectangle with a maximum area whose sides are parallel to the x-axis and y-axis ("axis-aligned"), contained/insribed within a convex shape.

      This method computes the MIR for convex shapes only; if a concave shape is passed in, the resulting rectangle will be computed based on its convex hull.

      This method uses a brute force algorithm to perform an exhaustive search for a solution (therefore it is slow relative to other PGS_Optimisation methods).

      Parameters:
      shape -
      fast - whether to compute MIR based on a lower resolution input. When true, processing is ~6 times faster but potentially a little inaccurate
      Returns:
      a rectangle shape
      Since:
      1.3.0
      See Also:

    • maximumPerimeterSquare

      public static processing.core.PShape maximumPerimeterSquare(processing.core.PShape shape, double tolerance)
      Finds the largest area perimeter square of the input. A perimeter square is a square whose 4 vertices each lie on the perimeter of the input shape (within the given tolerance).

      If the input is convex, the output forms a fully inscribed square; if the input is concave the output is not necessarily inscribed.

      The method does not respect holes (for now...).

      Parameters:
      shape -
      tolerance - a value of 2-5 is usually suitable
      Returns:
      shape representing the maximum square
      Since:
      1.4.0

    • minimumBoundingCircle

      public static processing.core.PShape minimumBoundingCircle(processing.core.PShape shape)
      Computes the Minimum Bounding Circle (MBC) for the points in a Geometry. The MBC is the smallest circle which covers all the vertices of the input shape (this is also known as the Smallest Enclosing Circle). This is equivalent to computing the Maximum Diameter of the input vertex set.

    • minimumWidthRectangle

      public static processing.core.PShape minimumWidthRectangle(processing.core.PShape shape)
      Computes the minimum-width bounding rectangle that encloses a shape. Unlike the envelope for a shape, the rectangle returned by this method can have any orientation (it's not axis-aligned).

      The minimum-width enclosing rectangle does not necessarily have the minimum possible area. Use minimumAreaRectangle() to compute this.

      Parameters:
      shape - The shape to compute the minimum bounding rectangle for.
      Returns:
      A PShape object representing the minimum bounding rectangle.

    • minimumAreaRectangle

      public static processing.core.PShape minimumAreaRectangle(processing.core.PShape shape)
      Computes the minimum-area rectangle that encloses a shape.

      The minimum-area enclosing rectangle does not necessarily have the minimum possible width. Use minimumBoundingRectangle() to compute this.

      Parameters:
      shape - The shape to compute the minimum-area rectangle for.
      Returns:
      A PShape object representing the minimum-area rectangle.
      Since:
      1.4.0

    • minimumBoundingEllipse

      public static processing.core.PShape minimumBoundingEllipse(processing.core.PShape shape, double errorTolerance)
      Computes the minimum bounding ellipse that encloses a shape.
      Parameters:
      shape -
      errorTolerance - Mean-squared error tolerance (this value does not correspond to a pixel distance). 0.001 to 0.01 recommended. Higher values are a looser (yet quicker) fit.
      Returns:

    • minimumBoundingTriangle

      public static processing.core.PShape minimumBoundingTriangle(processing.core.PShape shape)
      Computes the minimum-area bounding triangle that encloses a shape.
      Parameters:
      shape -
      Returns:

    • minimumDiameter

      public static processing.core.PShape minimumDiameter(processing.core.PShape shape)
      Computes the minimum diameter of a shape.

      The minimum diameter is defined to be the width of the smallest band that contains the shape, where a band is a strip of the plane defined by two parallel lines. This can be thought of as the smallest hole that the geometry can be moved through, with a single rotation.

      Parameters:
      shape -
      Returns:

    • largestEmptyCircle

      public static processing.core.PShape largestEmptyCircle(processing.core.PShape obstacles, double tolerance)
      Computes the largest empty circle that does not intersect any obstacles (up to a specified tolerance).

      Valid obstacles are point, line or polygonal shapes.

      The circle center lies within the interior of the convex hull of the obstacles.

      Parameters:
      obstacles - A PShape representing the obstacles.
      tolerance - A double representing the tolerance for the circle computation.
      Returns:
      A PShape representing the largest empty circle that does not intersect the obstacles and lies within the specified boundary.

    • largestEmptyCircle

      public static processing.core.PShape largestEmptyCircle(processing.core.PShape obstacles, @Nullable processing.core.PShape boundary, double tolerance)
      Computes the largest empty circle that does not intersect any obstacles and lies within the specified boundary (up to a specified tolerance).

      Valid obstacles are point, line or polygonal shapes.

      The circle center is the point in the interior of the boundary which has the farthest distance from the obstacles (up to the tolerance).

      Parameters:
      obstacles - A PShape representing the obstacles.
      boundary - A PShape representing the polygonal boundary, or null if there is no boundary constraint.
      tolerance - A double representing the tolerance for the circle computation.
      Returns:
      A PShape representing the largest empty circle that does not intersect the obstacles and lies within the specified boundary.

    • largestEmptyCircles

      public static List<processing.core.PVector> largestEmptyCircles(processing.core.PShape obstacles, @Nullable processing.core.PShape boundary, int n, double tolerance)
      Computes the n largest empty circles that do not intersect any obstacles (nor each other) within an optional boundary.

      The empty circles are found with a specified tolerance value, which limits the precision of the computation.

      Valid obstacles are point, line or polygonal shapes.

      Parameters:
      obstacles - PShape containing the obstacles in the 2D space
      boundary - polygonal PShape defining the boundary of the space, or null if no boundary is defined (in which case the convex hull of obstacles is used as boundary).
      n - the number of largest empty circles to find
      tolerance - the tolerance value for the computation
      Returns:
      a list of PVector objects representing the centers and radii of the found largest empty circles as PVector(x, y, r), where x and y are the center coordinates, and r is the radius
      Since:
      1.4.0

    • circleCoverage

      public static List<processing.core.PVector> circleCoverage(processing.core.PShape shape, int n)
      Covers a polygon with n circles such that no circle’s center lies outside the polygon. Circles will generally cover most of the shape and have some mutual overlap.
      Parameters:
      shape - shape to cover
      n - number of circles to generate
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.
      Since:
      1.4.0
      See Also:

    • circleCoverage

      public static List<processing.core.PVector> circleCoverage(processing.core.PShape shape, int n, long seed)
      Covers a polygon with n circles such that no circle’s center lies outside the polygon. Circles will generally cover most of the shape and have some mutual overlap.
      Parameters:
      shape - shape to cover
      n - number of circles to generate
      seed - random seed
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.
      Since:
      1.4.0
      See Also:

    • rectPack

      public static processing.core.PShape rectPack(List<processing.core.PVector> rectangles, int binWidth, int binHeight, PGS_Optimisation.RectPackHeuristic heuristic)
      Packs a collection of rectangles, according to the given packing heuristic, into rectangular 2D bin(s). Within each bin rectangles are packed flush with each other, having no overlap. Each rectangle is packed parallel to the edges of the plane.

      When packed rectangles fill one bin, any remaining rectangles will be packed into additional bin(s).

      Parameters:
      rectangles - a collection of rectangles (represented by PVectors), specifying their width (.x) and height (.y)
      binWidth - the width of each bin's area in which to pack the rectangles
      binHeight - the height of each bin's area in which to pack the rectangles
      heuristic - the packing heuristic to use. The heuristic determines rules for how every subsequent rectangle is placed
      Returns:
      a GROUP PShape, where each immediate child is a GROUP shape corresponding to a bin; the child shapes of each bin are rectangles. Bins are positioned at (0, 0).
      Since:
      1.4.0

    • binPack

      public static processing.core.PShape binPack(List<processing.core.PShape> shapes, double binWidth, double binHeight, int binColumns, double spacing)
      Packs a list of irregular polygonal shapes into (potentially multiple) rectangular containers (bins), while attempting to minimise the occupied space of the packing.

      Every bin has the dimensions given by the width and height parameters; when packed shapes fill/overflow one bin, any remaining shapes will be packed into additional bin(s). Multiple bins are arranged in a grid, having the maximum number of columns specified by the binColumns parameter.

      Bins are packed top-to-bottom vertically.

      Parameters:
      shapes - a list of PShapes to be packed within a bin(s)
      binWidth - the width of each bin/container to pack the shapes into
      binHeight - the height of each bin/container to pack the shapes into
      binColumns - the number of columns to arrange the bins into (>= 1, only applies when there are multiple bins).
      spacing - the amount of spacing between each packed shape (>= 0).
      Returns:
      a new GROUP PShape object containing the packed shapes arranged in columns
      Since:
      1.4.0

    • closestPoint

      public static processing.core.PVector closestPoint(processing.core.PShape shape, processing.core.PVector point)
      Returns the nearest point of the shape to the given point. If the shape is has multiple children/geometries (a GROUP shape), the single closest point is returned.
      Parameters:
      shape -
      point -
      Returns:
      See Also:

    • closestPoints

      public static List<processing.core.PVector> closestPoints(processing.core.PShape shape, processing.core.PVector point)
      Returns the nearest point for each "island" / separate polygon in the GROUP input shape.
      Parameters:
      shape - a GROUP shape
      point -
      Returns:
      list of closest points for each child shape. Output is identical to closestPoint(PShape, PVector) if the input shape is a single polygon
      See Also:

    • closestPointPair

      public static List<processing.core.PVector> closestPointPair(Collection<processing.core.PVector> points)
      Computes the closest pair of points in a set of points. This method runs in O(n*log(n)), rather than the naive O(n*n) brute-force approach.
      Parameters:
      points - a set of 2D points, represented by PVectors
      Returns:
      a List of PVectors containing exactly two elements which are the closest pair of points among those in the set.
      Since:
      1.1.0
      See Also:

    • farthestPointPair

      public static List<processing.core.PVector> farthestPointPair(Collection<processing.core.PVector> points)
      Computes the farthest pair of points (the "diametral pair") in a set of n points.

      This method runs in O(n*log(n)), rather than the naive O(n*n) brute-force approach. However, it must first compute the convex hull of the point set, so there is more overhead; on small datasets, the brute-force approach is likely faster).

      Parameters:
      points - a set of 2D points, represented by PVectors
      Returns:
      a List of PVectors containing exactly two elements which are the farthest pair of points among those in the set.
      Since:
      1.1.0
      See Also:

    • hilbertSortFaces

      public static processing.core.PShape hilbertSortFaces(processing.core.PShape mesh)
      Sorts the faces/child shapes of a GROUP shape according to hilbert curve index of each face's centroid coordinate. This ensures that nearby faces have a similar index in the list of children.
      Parameters:
      mesh - group shape
      Returns:
      a copy of the input shape, having the same faces/child shapes in a different order
      Since:
      1.3.0

    • solveApollonius

      public static processing.core.PVector solveApollonius(processing.core.PVector c1, processing.core.PVector c2, processing.core.PVector c3, int s1, int s2, int s3)
      Solves the Problem of Apollonius (finding a circle tangent to three other circles in the plane). Circles are represented by PVectors, where the z coordinate is interpreted as radius.
      Parameters:
      c1 - One of the circles in the problem
      c2 - One of the circles in the problem
      c3 - One of the circles in the problem
      s1 - An indication if the solution should be externally or internally tangent (+1/-1) to c1
      s2 - An indication if the solution should be externally or internally tangent (+1/-1) to c2
      s3 - An indication if the solution should be externally or internally tangent (+1/-1) to c3
      Returns:
      The circle (as a PVector) that is tangent to c1, c2 and c3.

    • visibilityPolygon

      public static processing.core.PShape visibilityPolygon(processing.core.PShape obstacles, processing.core.PVector viewPoint)
      Computes a visibility polygon / isovist, the area visible from a given point in a space, considering occlusions caused by obstacles. In this case, obstacles comprise the line segments of input shape.
      Parameters:
      obstacles - shape representing obstacles, which may have any manner of polygon and line geometries.
      viewPoint - view point from which to compute visibility. If the input if polygonal, the viewpoint may lie outside the polygon.
      Returns:
      a polygonal shape representing the visibility polygon.
      Since:
      1.4.0
      See Also:

    • visibilityPolygon

      public static processing.core.PShape visibilityPolygon(processing.core.PShape obstacles, Collection<processing.core.PVector> viewPoints)
      Computes a visibility polygon / isovist, the area visible from a set of given points in space, considering occlusions caused by obstacles. In this case, obstacles comprise the line segments of input shape.
      Parameters:
      obstacles - shape representing obstacles, which may have any manner of polygon and line geometries.
      viewPoints - viewpoints from which to compute visibility. If the input if polygonal, viewpoints may lie outside the polygon.
      Returns:
      a polygonal shape representing the visibility polygon (possibly a GROUP shape of disjoint visibility polygons).
      Since:
      1.4.0
      See Also: