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 processing.core.PShape	centroidSortFaces(processing.core.PShape mesh)	Returns a new, flattened PShape containing the child faces of mesh sorted by the x and then y coordinates of their centroids.
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(Collection<processing.core.PVector> points, processing.core.PVector point)	Finds the closest point in the collection to a specified point.
static processing.core.PVector	closestPoint(processing.core.PShape shape, processing.core.PVector point)	Returns the nearest point along the edges of the given shape to the specified query 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.PVector	closestVertex(processing.core.PShape shape, processing.core.PVector queryPoint)	Returns the closest vertex of a shape to a query point.
static processing.core.PVector	convexMaximumInscribedCircle(processing.core.PShape shape)	Computes the exact largest inscribed circle for a convex polygonal shape.
static processing.core.PShape	envelope(processing.core.PShape shape)	Deprecated. since 2.1; use boundingBox(PShape) instead.
static processing.core.PVector	farthestPoint(Collection<processing.core.PVector> points, processing.core.PVector point)	Finds the farthest point in the collection from a specified point.
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.PVector	farthestVertex(processing.core.PShape shape, processing.core.PVector queryPoint)	Returns the farthest vertex of a shape from a query point.
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)	Computes the maximum inscribed circle within a given shape.
static processing.core.PShape	maximumInscribedCircle(processing.core.PShape shape, double tolerance)	Computes the maximum inscribed circle within a given shape, using a specified tolerance.
static processing.core.PShape	maximumInscribedCircle(processing.core.PShape shape, double tolerance, processing.core.PVector result)	Computes the maximum inscribed circle (MIC) within a given shape, using the specified accuracy, and optionally outputs the center and radius.
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	maximumInscribedTriangle(processing.core.PShape shape)	Finds an approximate largest area triangle (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) that encloses all vertices of the provided shape.
static processing.core.PShape	minimumBoundingCircle(processing.core.PShape shape, processing.core.PVector result)	Computes the minimum bounding circle (MBC) for the given shape, and optionally returns the center and radius.
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	minimumWidthAnnulus(processing.core.PShape shape)	Computes the minimum-width annulus (the donut-like region between two concentric circles with minimal width that encloses the vertices of the given PShape).
static processing.core.PShape	minimumWidthRectangle(processing.core.PShape shape)	Computes the minimum-width bounding rectangle that encloses a shape.
static processing.core.PShape	radialSortFaces(processing.core.PShape mesh, processing.core.PVector centre, double offset)	Sorts the faces (children) of a mesh radially around a given centre, then applies a circular rotation to the order based on the offset parameter.
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	spiralSortFaces(processing.core.PShape mesh, processing.core.PShape startFace)	Reorders the faces of a mesh into an anti-clockwise “spiral” (breadth-first rings) starting from a given face, then returns a new, flattened PShape containing exactly those faces in spiral order.
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

@Deprecated
public static processing.core.PShape envelope(processing.core.PShape shape)

Deprecated.

since 2.1; use boundingBox(PShape) instead.

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)

Computes the maximum inscribed circle within a given shape.

The Maximum Inscribed Circle (MIC) is defined as the largest possible circle that can be completely contained within the area of the input shape. It is determined by locating a point inside the shape that has the greatest distance from the shape's boundary (i.e., the center of the MIC), and returning a circle centered at this point with a radius equal to that distance.

This method automatically selects a reasonable tolerance value for computing the center point of the MIC, balancing precision and computational efficiency.

Parameters:

shape - the PShape representing the area within which to compute the MIC

Returns:

a PShape instance representing the maximum inscribed circle

Since:

2.1

maximumInscribedCircle

public static processing.core.PShape maximumInscribedCircle(processing.core.PShape shape,
 double tolerance)

Computes the maximum inscribed circle within a given shape, using a specified tolerance.

The Maximum Inscribed Circle (MIC) is the largest possible circle that can be fully contained within the area of the input shape. The center of the MIC is the point in the interior that is farthest from the shape's boundary, and the radius is the distance from this center point to the closest boundary point.

Parameters:

shape - the PShape representing the area within which to compute the maximum inscribed circle; typically a simple polygon or multipolygon

tolerance - the distance tolerance or resolution for approximation; must be non-negative. Lower values yield a more accurate result but increase computation time (e.g., 0.5 or 1 is common).

Returns:

a PShape representing the maximum inscribed circle within the input shape

See Also:

• maximumInscribedCircle(PShape, double, PVector)

maximumInscribedCircle

public static processing.core.PShape maximumInscribedCircle(processing.core.PShape shape,
 double tolerance,
 @Nullable
 processing.core.PVector result)

Computes the maximum inscribed circle (MIC) within a given shape, using the specified accuracy, and optionally outputs the center and radius.

The maximum inscribed circle is the largest possible circle completely contained within the input shape. If a non-null result vector is provided, its x and y values will be set to the coordinates of the circle's center, and z will be set to its radius.

The returned PShape is a polygonal approximation of the inscribed circle.

Parameters:

shape - the PShape to analyze

tolerance - the resolution (smaller values increase accuracy but reduce performance)

result - if not null, will receive center (x, y) and radius (z) of the MIC

Returns:

a PShape representing the maximum inscribed circle within the input shape

Since:

2.1

See Also:

• maximumInscribedCircle(PShape, double)

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

convexMaximumInscribedCircle

public static processing.core.PVector convexMaximumInscribedCircle(processing.core.PShape shape)

Computes the exact largest inscribed circle for a convex polygonal shape.

This method is preferred and faster when the caller knows the shape is convex; use it instead of maximumInscribedCircle() for convex inputs.

Parameters:

shape - a convex polygonal PShape (non-null)

Returns:

a PVector (x, y, r) where x,y is the circle center and z (r) is the radius

Since:

2.1

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 - a polygonal shape

Returns:

a rectangle shape

See Also:

• maximumInscribedAARectangle() - the largest axis-aligned rectangle

maximumInscribedTriangle

public static processing.core.PShape maximumInscribedTriangle(processing.core.PShape shape)

Finds an approximate largest area triangle (of arbitrary orientation) contained within a polygon.

Parameters:

shape - a polygonal shape

Returns:

a triangular shape

Since:

2.1

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:

• maximumInscribedRectangle() -- the largest rectangle of arbitrary orientation

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 - a polygonal 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) that encloses all vertices of the provided shape.

The minimum bounding circle is the smallest circle that contains all vertices of the input shape.

Parameters:

shape - the input PShape; all its vertices will be considered for the bounding circle computation

Returns:

a PShape object representing the minimum bounding circle that encloses all vertices of the input shape

See Also:

• minimumBoundingCircle(PShape, PVector)

minimumBoundingCircle

public static processing.core.PShape minimumBoundingCircle(processing.core.PShape shape,
 @Nullable
 processing.core.PVector result)

Computes the minimum bounding circle (MBC) for the given shape, and optionally returns the center and radius.

The minimum bounding circle is the smallest circle that contains all vertices of the input shape. If the provided result vector is non-null, its x and y fields will be set to the coordinates of the circle's center, and its z field will be set to the circle's radius.

This method returns a new PShape representing the computed circle.

Parameters:

shape - the shape whose vertices will be used to compute the minimum bounding circle

result - a PVector; if non-null, receives the center as (x, y) and radius as (z)

Returns:

a PShape representing the minimum bounding circle enclosing all vertices of the input shape

Since:

2.1

See Also:

• minimumBoundingCircle(PShape)

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.

minimumBoundingTriangle

public static processing.core.PShape minimumBoundingTriangle(processing.core.PShape shape)

Computes the minimum-area bounding triangle that encloses a shape.

Parameters:

shape -

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 -

minimumWidthAnnulus

public static processing.core.PShape minimumWidthAnnulus(processing.core.PShape shape)

Computes the minimum-width annulus (the donut-like region between two concentric circles with minimal width that encloses the vertices of the given PShape).

The annulus is defined as the region between two concentric circles (with computed center and radii), such that all vertices of the input shape lie between the inner and outer circle, and the distance between these circles (the "width" of the annulus) is minimized.

The algorithm considers only the vertices of the input shape (not the filled area or edges) as points to be enclosed.

Parameters:

shape - the PShape whose vertices are to be enclosed by the minimum-width annulus; must be non-null and contain at least three points

Returns:

a PShape representing the minimum-width annulus (as a ring shape)

Since:

2.1

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(PShape, int, long)

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:

• circleCoverage(PShape, int)

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

closestVertex

public static processing.core.PVector closestVertex(processing.core.PShape shape,
 processing.core.PVector queryPoint)

Returns the closest vertex of a shape to a query point. For GROUP shapes, any child geometry's vertex may be returned.

Parameters:

shape - the PShape to search for the closest vertex

queryPoint - the query PVector

Returns:

a new PVector at the position of the closest vertex (not a reference to existing shape data)

Since:

2.1

closestPoint

public static processing.core.PVector closestPoint(processing.core.PShape shape,
 processing.core.PVector point)

Returns the nearest point along the edges of the given shape to the specified query point.

This method computes the point on the perimeter (including all edges, not only the vertices) of the given shape that is closest to the given point. For composite shapes (such as GROUP shapes made of multiple child geometries), the single closest point across all children is returned.

Note: The nearest location may be somewhere along an edge of the shape, not necessarily at one of the original shape's vertices.

Parameters:

shape - the PShape to search for the closest boundary point.

point - the PVector point to which the nearest point is sought.

Returns:

a new PVector representing the exact coordinates of the closest point on the shape's boundary or edge (not a reference to the original coordinate).

See Also:

• closestPoints(PShape, PVector)

closestPoint

public static processing.core.PVector closestPoint(Collection<processing.core.PVector> points,
 processing.core.PVector point)

Finds the closest point in the collection to a specified point.

Parameters:

points - the collection of points to search within

point - the point to find the closest neighbor for

Returns:

the closest point from the collection to the specified point

Since:

2.1

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:

• closestPoint(PShape, PVector)

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(Collection)

farthestVertex

public static processing.core.PVector farthestVertex(processing.core.PShape shape,
 processing.core.PVector queryPoint)

Returns the farthest vertex of a shape from a query point. For GROUP shapes, any child geometry's vertex may be returned.

Parameters:

shape - the PShape to search for the farthest vertex

queryPoint - the query PVector

Returns:

a new PVector at the position of the farthest vertex (not a reference to existing shape data)

Since:

2.1

farthestPoint

public static processing.core.PVector farthestPoint(Collection<processing.core.PVector> points,
 processing.core.PVector point)

Finds the farthest point in the collection from a specified point.

Parameters:

points - the collection of points to search within

point - the point from which the farthest neighbor is sought

Returns:

the farthest point from the collection to the specified point

Since:

2.1

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:

• closestPointPair(Collection)
• closestPoints(PShape, PVector)

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

spiralSortFaces

public static processing.core.PShape spiralSortFaces(processing.core.PShape mesh,
 processing.core.PShape startFace)

Reorders the faces of a mesh into an anti-clockwise “spiral” (breadth-first rings) starting from a given face, then returns a new, flattened PShape containing exactly those faces in spiral order.

Parameters:

mesh - mesh-like GROUP PShape

startFace - One of the child‐faces of mesh. This face will appear first in the returned ordering; subsequent faces follow in concentric breadth‐first “rings” around it, sorted anti-clockwise.

Returns:

A new, flattened PShape whose set of faces equals the children of mesh, but ordered in a spiral starting at startingFace.

Since:

2.1

centroidSortFaces

public static processing.core.PShape centroidSortFaces(processing.core.PShape mesh)

Returns a new, flattened PShape containing the child faces of mesh sorted by the x and then y coordinates of their centroids.

This is commonly used for ordering the faces of a mesh spatially in a grid-like manner, first by increasing x-coordinate of the face centroids, and breaking ties using y-coordinate.

Parameters:

mesh - a mesh-like GROUP PShape whose children (faces) will be sorted by centroid

Returns:

a new, flattened PShape whose faces are sorted by the centroids’ x and y coordinates

Since:

2.1

radialSortFaces

public static processing.core.PShape radialSortFaces(processing.core.PShape mesh,
 processing.core.PVector centre,
 double offset)

Sorts the faces (children) of a mesh radially around a given centre, then applies a circular rotation to the order based on the offset parameter.

Parameters:

mesh - a PShape with polygonal children (the faces to order)

centre - the point around which radial sorting is performed (usually the mesh centroid)

offset - a fractional value in [0, 1) that specifies where the ordering starts around the centre, as a proportion of a full 360° turn:

• offset = 0.0: face whose centroid points directly to the right (positive X direction) comes first
• offset = 0.25: ordering is rotated 90° counterclockwise; face pointing “up” (positive Y) comes first
• offset = 0.5: ordering is rotated 180°; face pointing to the left (-X) comes first
• offset = 0.75: ordering is rotated 270°; face pointing “down” (-Y) comes first

Intermediate values smoothly rotate the sequence; outside [0,1) values wrap around. In other words, this lets you “spin” the order of faces by a fraction of a circle.

Returns:

a new PShape, with faces flattened into one shape, ordered so that face[0] begins at offset·360° from the right and continues clockwise

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(PShape, Collection)

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:

• visibilityPolygon(PShape, PVector)