micycle.pgs

Class PGS_Processing

java.lang.Object

micycle.pgs.PGS_Processing

public final class PGS_Processing
extends Object

Geometry Processing -- methods that process a shape in some way: compute hulls, partition, slice, etc.

Author:

Michael Carleton

Method Summary

Modifier and Type	Method and Description
static processing.core.PShape	cleanCoverage(processing.core.PShape coverage, double distanceTolerance, double angleTolerance) Removes gaps and overlaps from meshes/polygon collections that are intended to satisfy the following conditions: Vector-clean - edges between neighbouring polygons must either be identical or intersect only at endpoints. Non-overlapping - No two polygons may overlap.
static processing.core.PShape	convexPartition(processing.core.PShape shape) Partitions shape(s) into convex (simple) polygons.
static processing.core.PShape	densify(processing.core.PShape shape, double distanceTolerance) Densifies a shape by inserting additional vertices along its line segments.
static processing.core.PShape	eliminateSlivers(processing.core.PShape shape, double threshold) Removes narrow areas ("slivers") from a shape while preserving the geometry of the remaining parts.
static processing.core.PShape	equalPartition(processing.core.PShape shape, int parts) Randomly partitions a shape into N approximately equal-area polygonal cells.
static processing.core.PShape	equalPartition(processing.core.PShape shape, int parts, long seed) Randomly (with a given seed) partitions a shape into N approximately equal-area polygonal cells.
static processing.core.PShape	extractHoles(processing.core.PShape shape) Extracts all the holes from a shape, returning them as if they are polygons.
static processing.core.PShape	extractPerimeter(processing.core.PShape shape, double from, double to) Extracts a portion/subline of the perimeter of a shape between two locations on the perimeter.
static processing.core.PShape	filterChildren(processing.core.PShape shape, Predicate<processing.core.PShape> filterFunction) Filters out the children of a given PShape object based on a given Predicate function.
static List<processing.core.PVector>	generateRandomGridPoints(processing.core.PShape shape, int maxPoints, boolean constrainedToCircle, double gutterFraction) Generates up to maxPoints number of random points that are contained within the shape region.
static List<processing.core.PVector>	generateRandomGridPoints(processing.core.PShape shape, int maxPoints, boolean constrainedToCircle, double gutterFraction, long randomSeed) Generates up to maxPoints number of random points that are contained within the shape region.
static List<processing.core.PVector>	generateRandomPoints(processing.core.PShape shape, int points) Generates N random points that lie within the shape region.
static List<processing.core.PVector>	generateRandomPoints(processing.core.PShape shape, int points, long seed) Generates N random points that are contained within the shape region.
static List<processing.core.PVector>	lineSegmentsIntersection(List<processing.core.PVector> lineSegments) Computes all points of intersection between segments in a set of line segments.
static processing.core.PShape	nest(processing.core.PShape shape, int n, double r) Creates a nested shape having n levels of inner polygons; each inner polygon is obtained by joining the points at some fractional distance r along each side of the previous polygon.
static processing.core.PVector	pointOnExterior(processing.core.PShape shape, double perimeterPosition, double offsetDistance) Extracts a point from the perimeter (exterior) of the given shape at a specific position along its perimeter.
static processing.core.PVector	pointOnExteriorByDistance(processing.core.PShape shape, double perimeterDistance, double offsetDistance) Extracts a point from the perimeter (exterior) of the given shape at some distance along its perimeter.
static List<processing.core.PVector>	pointsOnExterior(processing.core.PShape shape, double interPointDistance, double offsetDistance) Generates a list of points that lie on the exterior/perimeter of the given shape.
static List<processing.core.PVector>	pointsOnExterior(processing.core.PShape shape, int points, double offsetDistance) Efficiently extracts multiple points from the perimeter of a shape, evenly distributed along its boundary.
static processing.core.PShape	polygonizeLines(List<processing.core.PVector> lineSegmentVertices) Finds the polygonal faces formed by a set of intersecting line segments.
static processing.core.PShape	removeHiddenLines(processing.core.PShape shape) Removes overlap between polygons contained in a GROUP shape, preserving only visible line segments suitable for pen plotting and similar applications.
static processing.core.PShape	removeSmallHoles(processing.core.PShape shape, double areaThreshold) Returns a copy of the shape where holes having an area less than the specified threshold are removed.
static List<processing.core.PVector>	shapeIntersection(processing.core.PShape a, processing.core.PShape b) Computes all points of intersection between the perimeters of two shapes.
static processing.core.PShape	slice(processing.core.PShape shape, processing.core.PVector p1, processing.core.PVector p2) Slices a shape using a line given by its start and endpoints.
static processing.core.PShape	split(processing.core.PShape shape) Splits a shape into four equal quadrants (based on the envelope of the shape).
static processing.core.PShape	split(processing.core.PShape shape, int splitDepth) Splits a shape into 4^(1+recursions) rectangular partitions.
static double	tangentAngle(processing.core.PShape shape, double perimeterRatio) Calculates the angle of the line tangent to the shape at a specific point on its perimeter.
static processing.core.PShape	trapezoidPartition(processing.core.PShape shape) Decomposes/partitions a shape into axis-aligned (stip-like) trazepoids.

Methods inherited from class java.lang.Object

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

Method Detail

densify

public static processing.core.PShape densify(processing.core.PShape shape,
                                             double distanceTolerance)

Densifies a shape by inserting additional vertices along its line segments. This results in a more detailed representation of the shape, affecting its structure without altering its geometry.

Parameters:

shape - The shape to be densified. It should be a lineal or polygonal shape.

distanceTolerance - The densification tolerance used. All line segments in the densified geometry will have lengths no longer than the specified distance tolerance. The distance tolerance must be a positive value.

Returns:

A new PShape object representing the densified geometry.

pointOnExterior

public static processing.core.PVector pointOnExterior(processing.core.PShape shape,
                                                      double perimeterPosition,
                                                      double offsetDistance)

Extracts a point from the perimeter (exterior) of the given shape at a specific position along its perimeter.

Parameters:

shape - A lineal or polygonal shape. If the input is a GROUP shape, a single point will be extracted from its first child shape.

perimeterPosition - A normalised position along the perimeter of a shape [0...1]. 0 corresponds to the starting point of the shape's perimeter, and 1 corresponds to the ending point of the perimeter; any value between 0 and 1 represents a proportional distance along the shape's boundary.

offsetDistance - A perpendicular offset distance from the shape's perimeter. A value of 0 corresponds to exactly on the shape's exterior/ Positive values offset the point away from the shape (outwards); negative values offset the point inwards towards its interior.

Returns:

See Also:

pointsOnExterior(PShape, int, double)

pointOnExteriorByDistance

public static processing.core.PVector pointOnExteriorByDistance(processing.core.PShape shape,
                                                                double perimeterDistance,
                                                                double offsetDistance)

Extracts a point from the perimeter (exterior) of the given shape at some distance along its perimeter.

Parameters:

shape - A lineal or polygonal shape. If the input is a GROUP shape, a single point will be extracted from its first child shape.

perimeterDistance - Distance along shape perimeter to extract the point. 0 corresponds to the first vertex of the shape's perimeter.

offsetDistance - A perpendicular offset distance from the shape's perimeter. A value of 0 corresponds to exactly on the shape's exterior/ Positive values offset the point away from the shape (outwards); negative values offset the point inwards towards its interior.

Returns:

Since:

1.4.0

pointsOnExterior

public static List<processing.core.PVector> pointsOnExterior(processing.core.PShape shape,
                                                             int points,
                                                             double offsetDistance)

Efficiently extracts multiple points from the perimeter of a shape, evenly distributed along its boundary.

This method provides a faster alternative to calling other methods repeatedly when you need to obtain multiple points along the exterior of the shape. The extracted points will be evenly distributed along the shape's perimeter, allowing you to efficiently sample the boundary.

Parameters:

shape - The shape from which to extract points. It should be a lineal or polygonal shape. If the input is a GROUP shape, a single point will be extracted from its first child.

points - The number of points to return, evenly distributed around the perimeter of the shape.

offsetDistance - The offset distance along a line perpendicular to the perimeter. Positive values will offset the points away from the shape's boundary (outwards), while negative values will offset the points inwards towards its interior.

Returns:

An array of PVector objects representing the extracted points on the shape's perimeter.

Since:

1.3.0

See Also:

pointOnExterior(PShape, double, double), pointsOnExterior(PShape, double, double)

pointsOnExterior

public static List<processing.core.PVector> pointsOnExterior(processing.core.PShape shape,
                                                             double interPointDistance,
                                                             double offsetDistance)

Generates a list of points that lie on the exterior/perimeter of the given shape.

This method creates a list of points that are evenly spaced along the shape's exterior. The points are distributed around the shape's boundary with a specified distance between each consecutive point. You can use this method to obtain a set of points that represents an approximation of the shape's outline.

Parameters:

shape - The shape from which to generate the points. It should be a lineal or polygonal shape. If the input is a GROUP shape, a single point will be extracted from its first child.

interPointDistance - The distance between each exterior point. This value controls the density of the points and determines how closely the points will be spaced along the shape's perimeter.

offsetDistance - The offset distance along a line perpendicular to the perimeter. Positive values will offset the points away from the shape's boundary (outwards), while negative values will offset the points inwards towards its interior.

Returns:

An array of PVector objects representing the points lying on the shape's exterior.

Since:

1.3.0

See Also:

pointOnExterior(PShape, double, double), densify(PShape, double)

extractPerimeter

public static processing.core.PShape extractPerimeter(processing.core.PShape shape,
                                                      double from,
                                                      double to)

Extracts a portion/subline of the perimeter of a shape between two locations on the perimeter.

Parameters:

shape - the shape from which to extract a the perimeter

from - the starting location of the perimeter extract, given by a fraction (0...1) of the total perimeter length

to - the end location of the perimeter extract, given by a fraction (0...1) of the total perimeter length

Returns:

lineal shape

Since:

1.2.0

tangentAngle

public static double tangentAngle(processing.core.PShape shape,
                                  double perimeterRatio)

Calculates the angle of the line tangent to the shape at a specific point on its perimeter. The position of the point is determined by the normalized distance along the shape's perimeter.

Parameters:

shape - The shape for which to find the tangent angle.

perimeterRatio - A normalised position along the perimeter of a shape [0...1]. 0 corresponds to the starting point of the shape's perimeter, and 1 corresponds to the ending point of the perimeter; any value between 0 and 1 represents a proportional distance along the shape's boundary.

Returns:

the normalized angle (in radians) that the tangent line at the specified position makes with the positive x-axis (east), orientated clockwise.

Since:

1.3.0

shapeIntersection

public static List<processing.core.PVector> shapeIntersection(processing.core.PShape a,
                                                              processing.core.PShape b)

Computes all points of intersection between the perimeters of two shapes.

NOTE: This method shouldn't be confused with PGS_ShapeBoolean.intersect(), which finds the shape made by the intersecting shape areas.

Parameters:

a - one shape

b - another shape

Returns:

list of all intersecting points (as PVectors)

lineSegmentsIntersection

public static List<processing.core.PVector> lineSegmentsIntersection(List<processing.core.PVector> lineSegments)

Computes all points of intersection between segments in a set of line segments. The input set is first processed to remove degenerate segments (does not mutate the input).

Parameters:

lineSegments - a list of PVectors where each pair (couplet) of PVectors represent the start and end point of one line segment

Returns:

A list of PVectors each representing the intersection point of a segment pair

generateRandomPoints

public static List<processing.core.PVector> generateRandomPoints(processing.core.PShape shape,
                                                                 int points)

Generates N random points that lie within the shape region.

This is a fast method but note that the underlying algorithm makes a minor trade-off for its speed: the resulting point set is slightly more uniformly distributed over the input shape compared to a purely random approach (this arises because the shape is first divided into triangles; each triangle is then sampled a fixed number of times according to its area relative to the whole).

Parameters:

shape - defines the region in which random points are generated

points - number of points to generate within the shape region

Returns:

See Also:

generateRandomPoints(PShape, int, long), generateRandomGridPoints(PShape, int, boolean, double)

generateRandomPoints

public static List<processing.core.PVector> generateRandomPoints(processing.core.PShape shape,
                                                                 int points,
                                                                 long seed)

Generates N random points that are contained within the shape region. Points are distributed completely randomly. This method accepts a seed for the RNG when identical sequences of random points are required.

This is a fast method but note that the underlying algorithm makes a minor trade-off for its speed: the resulting point set is slightly more uniformly distributed over the input shape compared to a purely random approach (this arises because the shape is first divided into triangles; each triangle is then sampled a fixed number of times according to its area relative to the whole).

Parameters:

shape - defines the region in which random points are generated

points - number of points to generate within the shape region

seed - number used to initialize the underlying pseudorandom number generator

Returns:

Since:

1.1.0

See Also:

generateRandomPoints(PShape, int), generateRandomGridPoints(PShape, int, boolean, double)

generateRandomGridPoints

public static List<processing.core.PVector> generateRandomGridPoints(processing.core.PShape shape,
                                                                     int maxPoints,
                                                                     boolean constrainedToCircle,
                                                                     double gutterFraction)

Generates up to maxPoints number of random points that are contained within the shape region. Points are distributed according to a grid of cells (one point randomly located in each cell), based on the envelope of the shape.

Parameters:

shape - defines the region in which random points are generated

maxPoints - maximum number of points, if this shape was its own envelope

constrainedToCircle - Sets whether generated points are constrained to lie within a circle contained within each grid cell. This provides greater separation between points in adjacent cells.

gutterFraction - Sets the fraction of the grid cell side which will be treated as a gutter, in which no points will be created. The provided value is clamped to the range [0.0, 1.0]. Higher values increase how "grid-like" the point distribution is.

Returns:

a list of random points, distributed according to a grid, contained within the given shape

See Also:

generateRandomPoints(PShape, int), generateRandomGridPoints(PShape, int, boolean, double, long)

generateRandomGridPoints

public static List<processing.core.PVector> generateRandomGridPoints(processing.core.PShape shape,
                                                                     int maxPoints,
                                                                     boolean constrainedToCircle,
                                                                     double gutterFraction,
                                                                     long randomSeed)

Generates up to maxPoints number of random points that are contained within the shape region. Points are distributed according to a grid of cells (one point randomly located in each cell), based on the envelope of the shape.

This method accepts a seed for the RNG when identical sequences of random points are required.

Parameters:

shape - defines the region in which random points are generated

maxPoints - maximum number of points, if this shape was its own envelope

constrainedToCircle - Sets whether generated points are constrained to lie within a circle contained within each grid cell. This provides greater separation between points in adjacent cells.

gutterFraction - Sets the fraction of the grid cell side which will be treated as a gutter, in which no points will be created. The provided value is clamped to the range [0.0, 1.0]. Higher values increase how "grid-like" the point distribution is.

randomSeed -

Returns:

a list of random points, distributed according to a grid, contained within the given shape

See Also:

generateRandomGridPoints(PShape, int, boolean, double)

nest

public static processing.core.PShape nest(processing.core.PShape shape,
                                          int n,
                                          double r)

Creates a nested shape having n levels of inner polygons; each inner polygon is obtained by joining the points at some fractional distance r along each side of the previous polygon.

This is also called a "derived polygon".

Parameters:

shape - a PShape representing the single input polygon for which the nested shape will be created. Although all polygon types are compatible, simpler/convex polygons make for a more effective result.

n - the number of nested levels to be created inside the input shape.

r - fractional distance between each nested level of polygons, where 0.5 produces maximal nesting.

Returns:

A PShape representing the nested shape, including the input shape and all the nested levels.

Since:

1.4.0

removeHiddenLines

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

Removes overlap between polygons contained in a GROUP shape, preserving only visible line segments suitable for pen plotting and similar applications.

This method processes a GROUP shape consisting of lineal or polygonal child shapes, aiming to create linework that represents only the segments visible to a human, rather than a computer. The resulting linework is useful for pen plotters or other applications where only the visible paths are desired.

During the operation, any overlapping lines are also removed to ensure a clean and clear representation of the shapes. It's important to note that the order of shape layers in the input GROUP shape is significant. The method considers the last child shape of the input to be "on top" of all other shapes, as is the case visually.

Parameters:

shape - A GROUP shape containing lineal or polygonal child shapes.

Returns:

The resulting linework of the overlapping input as a LINES PShape, representing only visible line segments.

Since:

1.3.0

removeSmallHoles

public static processing.core.PShape removeSmallHoles(processing.core.PShape shape,
                                                      double areaThreshold)

Returns a copy of the shape where holes having an area less than the specified threshold are removed.

Parameters:

shape - a single polygonal shape or GROUP polygonal shape

areaThreshold - removes any holes with an area smaller than this value

Returns:

extractHoles

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

Extracts all the holes from a shape, returning them as if they are polygons.

Parameters:

shape - the PShape to extract holes from

Returns:

a new PShape that represents the holes extracted from the input shape. If the input had multiple holes, the output is a GROUP PShape where each child is polygon of one hole.

Since:

1.4.0

polygonizeLines

public static processing.core.PShape polygonizeLines(List<processing.core.PVector> lineSegmentVertices)

Finds the polygonal faces formed by a set of intersecting line segments.

Parameters:

lineSegmentVertices - a list of PVectors where each pair (couplet) of PVectors represent the start and end point of one line segment

Returns:

a GROUP PShape where each child shape is a face / enclosed area formed between intersecting lines

Since:

1.1.2

split

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

Splits a shape into four equal quadrants (based on the envelope of the shape).

Parameters:

shape - The shape to be split into quadrants.

Returns:

A GROUP PShape where each child shape represents one of the four quadrants partitioned from the original shape.

See Also:

split(PShape, int)

split

public static processing.core.PShape split(processing.core.PShape shape,
                                           int splitDepth)

Splits a shape into 4^(1+recursions) rectangular partitions.

This method performs a recursive split operation on the given shape, dividing it into a finer grid of rectangular partitions. Each recursion further divides the envelopes of the parent shapes into four quadrants, resulting in a more refined partitioning of the original shape.

It's important to note that this operation differs from merely overlaying a regular square grid on the shape and then splitting it. The recursive process ensures that each subdivision is based on the envelope of the parent shape, which may be rectangular.

Parameters:

shape - The shape to be split into rectangular partitions.

splitDepth - The number of split recursions to perform, determining the level of partitioning and grid refinement.

Returns:

A GROUP PShape, where each child shape represents one of the quadrant partitions of the original shape.

See Also:

split(PShape)

convexPartition

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

Partitions shape(s) into convex (simple) polygons.

Parameters:

shape - the shape to partition. can be a single polygon or a GROUP of polygons

Returns:

a GROUP PShape, where each child shape is some convex partition of the original shape

equalPartition

public static processing.core.PShape equalPartition(processing.core.PShape shape,
                                                    int parts)

Randomly partitions a shape into N approximately equal-area polygonal cells.

Parameters:

shape - a polygonal (non-group, no holes) shape to partition

parts - number of roughly equal area partitons to create

Returns:

a GROUP PShape, whose child shapes are partitions of the original

Since:

1.3.0

equalPartition

public static processing.core.PShape equalPartition(processing.core.PShape shape,
                                                    int parts,
                                                    long seed)

Randomly (with a given seed) partitions a shape into N approximately equal-area polygonal cells.

Parameters:

shape - a polygonal (non-group, no holes) shape to partition

parts - number of roughly equal area partitons to create

seed - number used to initialize the underlying pseudorandom number generator

Returns:

a GROUP PShape, whose child shapes are partitions of the original

Since:

1.4.0

trapezoidPartition

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

Decomposes/partitions a shape into axis-aligned (stip-like) trazepoids.

The output can contain some "degenerate" trapezoids that do indeed have 4 vertices but look like triangles.

Parameters:

shape - a polygonal or a GROUP shape

Returns:

a GROUP PShape comprising of trapezoid child shapes

Since:

1.3.0

slice

public static processing.core.PShape slice(processing.core.PShape shape,
                                           processing.core.PVector p1,
                                           processing.core.PVector p2)

Slices a shape using a line given by its start and endpoints.

Parameters:

shape - PShape to slice into two shapes

p1 - must be outside shape

p2 - must be outside shape

Returns:

a GROUP PShape with two children, where each child shape is one of the slices

eliminateSlivers

public static processing.core.PShape eliminateSlivers(processing.core.PShape shape,
                                                      double threshold)

Removes narrow areas ("slivers") from a shape while preserving the geometry of the remaining parts.

This operation is similar to erosionDilation(), but better preserves the original geometry of remaining parts.

If the input is a single polygon and if when removing slivers, a multipolygon is produced, further processing occurs within the method to repair it back into a single polygon.

Parameters:

shape - polygonal shape

threshold - width threshold (probably no more than 10); parts narrower than this are eliminated

Returns:

a copy of the input shape having narrow areas/parts removed

Since:

1.3.0

cleanCoverage

public static processing.core.PShape cleanCoverage(processing.core.PShape coverage,
                                                   double distanceTolerance,
                                                   double angleTolerance)

Removes gaps and overlaps from meshes/polygon collections that are intended to satisfy the following conditions:

• Vector-clean - edges between neighbouring polygons must either be identical or intersect only at endpoints.
• Non-overlapping - No two polygons may overlap. Equivalently, polygons must be interior-disjoint.

It may not always be possible to perfectly clean the input.

While this method is intended to be used to fix malformed coverages, it can be used to snap collections of disparate polygons together.

Parameters:

coverage - a GROUP shape, consisting of the polygonal faces to clean

distanceTolerance - the distance below which segments and vertices are considered to match

angleTolerance - the maximum angle difference between matching segments, in degrees

Returns:

GROUP shape whose child polygons satisfy a (hopefully) valid coverage

Since:

1.3.0

filterChildren

public static processing.core.PShape filterChildren(processing.core.PShape shape,
                                                    Predicate<processing.core.PShape> filterFunction)

Filters out the children of a given PShape object based on a given Predicate function. Child shapes are filtered when the predicate is true: "remove if...".

Example Lambda Code:

 
 PGS_Processing.filterChildren(myShape, child -> PGS_ShapePredicates.area(child) < 50); // discard small child shapes
 
 

Parameters:

shape - The PShape whose children will be filtered.

filterFunction - A Predicate function that takes a PShape object as its argument and returns true if the child shape should be filtered out/removed from the shape. To retain child shapes, the Predicate function should return false. You can use a lambda expression or a method reference to implement the Predicate function.

Returns:

A new PShape that contains only the children shapes of the input shape that satisfy the given Predicate function (==false).

Since:

1.4.0