public final class PGS_Optimisation extends Object
Modifier and Type | Class and Description |
---|---|
static class |
PGS_Optimisation.RectPackHeuristic |
Modifier and Type | Method and 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.
|
public static processing.core.PShape envelope(processing.core.PShape shape)
shape
- a rectangular shape that covers/bounds the inputpublic static processing.core.PShape maximumInscribedCircle(processing.core.PShape shape, double tolerance)
shape
- tolerance
- the distance tolerance for computing the centre point
(around 1)public static processing.core.PShape maximumInscribedCircle(processing.core.PShape shape, processing.core.PVector centerPoint)
shape
- centerPoint
- public static processing.core.PShape maximumInscribedRectangle(processing.core.PShape shape)
shape
- maximumInscribedAARectangle() - the largest axis-aligned rectangle
public static processing.core.PShape maximumInscribedAARectangle(processing.core.PShape shape, boolean fast)
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).
shape
- fast
- whether to compute MIR based on a lower resolution input. When
true, processing is ~6 times faster but potentially a little
inaccuratemaximumInscribedRectangle() -- the
largest rectangle of arbitrary orientation
public static processing.core.PShape maximumPerimeterSquare(processing.core.PShape shape, double 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...).
shape
- tolerance
- a value of 2-5 is usually suitablepublic static processing.core.PShape minimumBoundingCircle(processing.core.PShape shape)
public static processing.core.PShape minimumWidthRectangle(processing.core.PShape shape)
The minimum-width enclosing rectangle does not necessarily have the minimum
possible area. Use minimumAreaRectangle()
to compute this.
shape
- The shape to compute the minimum bounding rectangle for.public static processing.core.PShape minimumAreaRectangle(processing.core.PShape shape)
The minimum-area enclosing rectangle does not necessarily have the minimum
possible width. Use minimumBoundingRectangle()
to compute this.
shape
- The shape to compute the minimum-area rectangle for.public static processing.core.PShape minimumBoundingEllipse(processing.core.PShape shape, double errorTolerance)
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.public static processing.core.PShape minimumBoundingTriangle(processing.core.PShape shape)
shape
- public static processing.core.PShape minimumDiameter(processing.core.PShape 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.
shape
- public static processing.core.PShape largestEmptyCircle(processing.core.PShape obstacles, double tolerance)
Valid obstacles are point, line or polygonal shapes.
The circle center lies within the interior of the convex hull of the obstacles.
obstacles
- A PShape representing the obstacles.tolerance
- A double representing the tolerance for the circle
computation.public static processing.core.PShape largestEmptyCircle(processing.core.PShape obstacles, @Nullable processing.core.PShape boundary, double 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).
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.public static List<processing.core.PVector> largestEmptyCircles(processing.core.PShape obstacles, @Nullable processing.core.PShape boundary, int n, double tolerance)
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.
obstacles
- PShape containing the obstacles in the 2D spaceboundary
- 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 findtolerance
- the tolerance value for the computationPVector
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 radiuspublic static List<processing.core.PVector> circleCoverage(processing.core.PShape shape, int n)
shape
- shape to covern
- number of circles to generatecircleCoverage(PShape, int, long)
public static List<processing.core.PVector> circleCoverage(processing.core.PShape shape, int n, long seed)
shape
- shape to covern
- number of circles to generateseed
- random seedcircleCoverage(PShape, int)
public static processing.core.PShape rectPack(List<processing.core.PVector> rectangles, int binWidth, int binHeight, PGS_Optimisation.RectPackHeuristic heuristic)
When packed rectangles fill one bin, any remaining rectangles will be packed into additional bin(s).
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
rectanglesbinHeight
- the height of each bin's area in which to pack the
rectanglesheuristic
- the packing heuristic to use. The heuristic determines
rules for how every subsequent rectangle is placedpublic static processing.core.PShape binPack(List<processing.core.PShape> shapes, double binWidth, double binHeight, int binColumns, double spacing)
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.
shapes
- a list of PShapes to be packed within a bin(s)binWidth
- the width of each bin/container to pack the shapes intobinHeight
- the height of each bin/container to pack the shapes intobinColumns
- 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).public static processing.core.PVector closestPoint(processing.core.PShape shape, processing.core.PVector point)
shape
- point
- closestPoints(PShape, PVector)
public static List<processing.core.PVector> closestPoints(processing.core.PShape shape, processing.core.PVector point)
shape
- a GROUP shapepoint
- closestPoint(PShape, PVector)
if the input shape is a single
polygonclosestPoint(PShape, PVector)
public static List<processing.core.PVector> closestPointPair(Collection<processing.core.PVector> points)
points
- a set of 2D points, represented by PVectorsfarthestPointPair(Collection)
public static List<processing.core.PVector> farthestPointPair(Collection<processing.core.PVector> 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).
points
- a set of 2D points, represented by PVectorsclosestPointPair(Collection)
,
closestPoints(PShape, PVector)
public static processing.core.PShape hilbertSortFaces(processing.core.PShape mesh)
mesh
- group shapepublic static processing.core.PVector solveApollonius(processing.core.PVector c1, processing.core.PVector c2, processing.core.PVector c3, int s1, int s2, int s3)
c1
- One of the circles in the problemc2
- One of the circles in the problemc3
- One of the circles in the problems1
- An indication if the solution should be externally or internally
tangent (+1/-1) to c1s2
- An indication if the solution should be externally or internally
tangent (+1/-1) to c2s3
- An indication if the solution should be externally or internally
tangent (+1/-1) to c3public static processing.core.PShape visibilityPolygon(processing.core.PShape obstacles, processing.core.PVector viewPoint)
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.visibilityPolygon(PShape, Collection)
public static processing.core.PShape visibilityPolygon(processing.core.PShape obstacles, Collection<processing.core.PVector> viewPoints)
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.visibilityPolygon(PShape, PVector)
Copyright © 2023. All rights reserved.