Package micycle.pgs

Class PGS_Hull

java.lang.Object

micycle.pgs.PGS_Hull

public class PGS_Hull
extends Object

Generates various types of geomtric hulls (convex, concave, etc.) for polygons and point sets.

A hull is the smallest enclosing shape that contains all points in a set.

Since:

1.3.0

Author:

Michael Carleton

Method Summary

Modifier and Type	Method	Description
static processing.core.PShape	concaveHull(processing.core.PShape shapeSet, double concavity, boolean tight)	Constructs a concave hull of a set of polygons, respecting the polygons as constraints (i.e. the hull is guaranteed to contain the polygons).
static processing.core.PShape	concaveHullBFS(List<processing.core.PVector> points, double edgeLengthRatio)	Computes the concave hull of a point set using a breadth-first method.
static processing.core.PShape	concaveHullBFS2(List<processing.core.PVector> points, double threshold)	Computes the concave hull of a point set using a different algorithm.
static processing.core.PShape	concaveHullDFS(List<processing.core.PVector> points, double concavity)	Computes the concave hull of a point set using a depth-first method.
static processing.core.PShape	convexHull(Collection<processing.core.PVector> points)	Computes the convex hull of a point set (the smallest convex polygon that contains all the points).
static processing.core.PShape	convexHull(processing.core.PShape shape)	Computes the convex hull of the vertices from the input shape (the smallest convex polygon that contains all the shape's vertices).
static processing.core.PShape	snapHull(processing.core.PShape shape, double convexity)	Computes a hull, having a variable level of convexity, of a shape.

Methods inherited from class java.lang.Object

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

Method Details

convexHull

public static processing.core.PShape convexHull(Collection<processing.core.PVector> points)

Computes the convex hull of a point set (the smallest convex polygon that contains all the points).

Parameters:

points - a collection of points

Returns:

the minimum-area convex polygon containing the points

Since:

1.3.0

convexHull

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

Computes the convex hull of the vertices from the input shape (the smallest convex polygon that contains all the shape's vertices).

Parameters:

shape - a concave shape

Returns:

the minimum-area convex polygon containing the input's vertices

Since:

1.3.0

concaveHull

public static processing.core.PShape concaveHull(processing.core.PShape shapeSet,
 double concavity,
 boolean tight)

Constructs a concave hull of a set of polygons, respecting the polygons as constraints (i.e. the hull is guaranteed to contain the polygons).

Parameters:

shapeSet - a GROUP PShape, having multiple child PShapes, each of which is a polygon

concavity - a factor value between 0 and 1, specifying how concave the output is.

tight - sets whether the boundary of the hull polygon is kept tight to precisely the outer edges of the input polygons

Returns:

concave hull of the input shapes

Since:

1.3.0

concaveHullDFS

public static processing.core.PShape concaveHullDFS(List<processing.core.PVector> points,
 double concavity)

Computes the concave hull of a point set using a depth-first method. In contrast to the BFS method, the depth-first approach produces shapes that are more contiguous/less branching and spiral-like.

Parameters:

points -

concavity - a factor value between 0 and 1, specifying how concave the output is (where 1 is maximal concavity)

Returns:

Since:

1.1.0

See Also:

• concaveHullBFS(List, double)
• concaveHullBFS2(List, double)

concaveHullBFS

public static processing.core.PShape concaveHullBFS(List<processing.core.PVector> points,
 double edgeLengthRatio)

Computes the concave hull of a point set using a breadth-first method.

Parameters:

points -

edgeLengthRatio - Sets the target maximum edge length ratio for the concave hull. The edge length ratio is a fraction of the difference between the longest and shortest edge lengths in the Delaunay Triangulation of the input points. It is a value in the range 0.0 to 1; at 0.0 it produces a concave hull of minimum area that is still connected; 1.0 produces the convex hull.

Returns:

Since:

1.1.0

See Also:

• concaveHullDFS(List, double)
• concaveHullBFS2(List, double)

concaveHullBFS2

public static processing.core.PShape concaveHullBFS2(List<processing.core.PVector> points,
 double threshold)

Computes the concave hull of a point set using a different algorithm. This approach has a more "organic" structure compared to other concaveBFS method.

Parameters:

points -

threshold - 0...1 (Normalized length parameter).

• Setting threshold=1 means that no edges will be removed from the Delaunay triangulation, so the resulting polygon will be the convex hull.
• Setting threshold=0 means that all edges that can be removed subject to the regularity constraint will be removed (however polygons that are eroded beyond the point where they provide a desirable characterization of the shape).
• Although the optimal parameter value varies for different shapes and point distributions, values between 0.05–0.2 typically produce optimal or near-optimal shape characterization across a wide range of point distributions.

Returns:

See Also:

• concaveHullBFS(List, double)

snapHull

public static processing.core.PShape snapHull(processing.core.PShape shape,
 double convexity)

Computes a hull, having a variable level of convexity, of a shape.

When convexity=0, the original shape is reproduced (a pure concave hull); the hull tends towards a convex hull of the input as convexity goes to 1 (in other words, a hull with some level of "snapping" to the original shape).

Parameters:

shape -

convexity - how convex the snap hull is, where 0 is the original shape (no convexity, fully concave) and 1 forms the convex hull of the shape's vertices

Returns: