Processing Geometry Suite

Processing Geometry Suite is a software project that provides easy access to 2D geometric algorithms in the form of a Processing library. Over time it has grown to include an incredibly comprehensive range of algorithms.

The focus of the library is on visualisation rather than providing underlying data structures. To this end all methods in the library are static and most of them take in and return PShapes or PVectors.

Docs are hosted via GitHub Pages here.

Overview

Library functionality is split over the following classes:

PGS_CirclePacking
- Circle packings of shapes, subject to varying constraints and patterns of tangencies.
PGS_Coloring
- Minimal colorings of meshes (or mesh-like shapes).
PGS_Construction
- Construct uncommon/interesting 2D primitives.
PGS_Contour
- Methods that produce various contours from shapes: medial axes, straight skeletons, offset curves, etc.
PGS_Conversion
- Conversion between Processing PShapes and JTS Geometries (amongst other formats).
PGS_Hull
- Convex and concave hulls of polygons and point sets.
PGS_Meshing
- Mesh generation (excluding triangulation) and processing.
PGS_Morphology
- Methods that affect the geometry or topology of shapes (buffering, simplification, smoothing, etc.).
PGS_Optimisation
- Solve geometric optimisation problems, such as finding the maximum inscribed circle, or the closest vertex to a coordinate.
PGS_PointSet
- Generates sets of 2D points having a variety of different distributions and constraints.
PGS_Polygonisation
- Generates simple polygonisations of point sets.
PGS_Processing
- Methods that process a shape in some way: partition, slice, clean, etc.
PGS_SegmentSet
- Generates sets of random non-intersecting line segments.
PGS_ShapeBoolean
- Boolean set-operations for 2D shapes.
PGS_ShapePredicates
- Various shape metrics (area, circularity, etc.) and predicates ("do these shapes intersect?").
PGS_Tiling
- Tiling, tessellation and subdivision of the plane using periodic or non-periodic geometric shapes.
PGS_Transformation
- Various geometric and affine transformations that affect vertex coordinates.
PGS_Triangulation
- Delaunay triangulation (constrained and refined) and earcut triangulation of shapes and point sets.
PGS_Voronoi
- Voronoi Diagrams of shapes and point sets.

Installation

Processing

PGS is available on Processing's contribution manager as "Geometry Suite for Processing".

Maven/Gradle

PGS is hosted as an artifact for use in Maven or Gradle projects via Jitpack — follow the instructions there (very easy).

Examples

A number of example Processing sketches are provided in examples.

Illustrations

Much of the functionality (but by no means all) is demonstrated below:

2D Boolean Operations

Union	Intersection	Subtraction	Symmetric Difference

Complement	Mesh Union	Mesh Intersection	Mesh Subtraction

Union Lines	Overlap Regions

Transformation

Rotate Around		Translate To	Touch Scale

Rotate a shape around its centroid or an arbitrary point.		Translate a shape such that its centroid matches some position.	Scale one shape such that it touches another.
Resize	Homothetic Transformation	Shear	Align

	Projection-transform a shape with respect to a fixed point.		Maximum-overlap alignment.

Geometric Predicates & Metrics

Intersects	Contains Shape	Contains Point	Containing Cell
Do shapes intersect with each other?	Does one shape fully contain another?	For individual points and point sets.	Which cell contains the query point?

Metrics


Length/perimeter	Similarity	Is simple?
Width & Height	Sphericity	Is convex?
Diameter	Elongation	Equal? (structural and topological equivalence)
Circularity	Density	Distance
Area	Holes	Centroid
Interior angles	Maximum interior angle	Median

Contour

Isolines		Offset Curves

Isolines from intra-shape euclidean distance, or point sets.		Inner and exterior offset curves; based on miter, bevel or round offset styles.
Straight Skeleton	Medial Axis		Chordal Axis

	Medial axis transform with feature pruning via distance, area or axial angle.		Chordal Axis Transform
Distance Field	Center Line	Distance Tree	Contrast Field

A contour map based on a distance field of a shape
Isolines from function

Morphology

Buffer	Erosion-Dilation	Minkowski Addition

	A negative followed by a positive buffer (in a single operation).	Minkowski sum and difference (a.k.a buffer one shape using another shape; the examples add a rotating & growing triangle).
Smoothing	Gaussian Smoothing	Rounding

Radial Warp	Sine Warp	Field Warp

Simplification	Chaikin Cutting		Interpolation

Variable Buffer	Precision Reduction	Hobby Curve Simplification	Elliptic Fourier Smoothing

Pinch Warp	ARAP Deform	Regularise	Bezier-fit Smoothing

Dilation Morph	Voronoi Morph

Hull

Concave Hull			Convex Hull of Polygons

Concave hull of point sets via breadth-first or depth-first approaches.
Convex Hull	Snap Hull	Bounding Box

	A variable-convexity hull.

Geometry Processing

Points on Perimeter		Point on Perimeter	Perimeter Extraction

Find N points (evenly distributed) along the perimeter of a shape, or points every D distance (with optional perpendicular offset).		Find a point some fraction along the perimeter of a shape (with perpendicular offset).
Splitting	Convex Partitioning	Equal Partitioning	Trapezoid Partitioning

Subdivide (recursively) a shape into quadrants.	Partition a shape into convex polygons.	Partition a shape into N equal area polygons.
Slicing	Constrained Random Point Set	Segment Set Intersection

Slice a shape in two along a given line.	Generate constrained random point sets where all points lie within a shape.	Find all points of intersection between a collection of line segments.
Shape Intersection	Polygonize Lines		Hidden Line Removal

Find all points of intersection between two shapes.	Find the polygonal faces formed by a set of intersecting line segments.		Remove linework occulted by shapes (for pen plotting)
Densification	Tangent Angle	Eliminate Slivers	Segments on Exterior

Extract Holes	Nest	Centroid Split

Triangulation

Delaunay Triangulation		Earcut Triangulation

Poisson Delaunay Triangulation	Refinement

Delaunay triangulation of shapes where steiner points generated by poisson disk sampling are inserted.	Ruppert angle refinement.

Voronoi Diagrams

Voronoi Diagram (inner)		Voronoi Diagram (compound)

Manhattan Voronoi	Additively Weighted Voronoi	Multiplicatively Weighted Voronoi	Farthest-Point Voronoi

Power Diagram	Centroidal Relaxation

Meshing

Urquhart Faces		Gabriel Faces	Triangulation Dual

Polygon faces of an Urquhart Graph (derived from a triangulation).		Polygon faces of a Gabriel Graph (derived from a triangulation).
Relative Neighbour Faces	Spanner Faces	Centroid Quadrangulation	Edge Collapse Quadrangulation

Split Quadrangulation	Spiral Quadrangulation	Mesh Smoothing	Mesh Subdivision

Mesh Simplification	Stochastic Merge	Area Merge	Extract Inner Edges

Extract Inner Vertices	Fix Breaks	Matching Quadrangulation

Geometric Optimisation

Maximum Inscribed Circle	Minimum Bounding Rectangle	Maximum Inscribed Rectangle	Maximum Perimeter Square

Maximum Inscribed Triangle	Minimum Bounding Circle	Minimum Bounding Ellipse

Minimum Bounding Triangle	Minimum-width Annulus	Problem of Apollonius

Largest Empty Circle	Largest Empty Circles	Closest Point Pair	Farthest Point Pair

Circle Covering	Closest Vertex	Visibility Polygon / Isovist

Bin Pack		Rectangle Bin Pack

Hilbert Sort Faces	Spiral Sort Faces	Centroid Sort Faces

Circle Packing

Front Chain		Trinscribed

Maximum Inscribed		Stochastic

Repulsion		Square Lattice

Hex Lattice		Tangency Pack

Obstacle

Coloring

Construction

Supercircle	Supershape	Star

Random Convex Polygon	Heart	Ring	Arc

Linear Spiral	Fermat Spiral	Rectangular Spiral	Hilbert Curve

Sierpinski Carpet	Sierpinski Curve	Sierpinski Tri-Curve (TRI)	Sierpinski Tri-Curve (TETRA)

Koch Snowflake	Blobbie	RSFC	Taijitu

Arbelos	Teardrop	Sponge

Gear	Super Random Polygon	Random Bezier Polygon

Point Sets

Random	Gaussian	Square Grid	Hex Grid

Phyllotaxis	Poisson	Hexagon	Ring

Halton LDS	Hammersley LDS	Plastic LDS	Jittered Plastic LDS

Sobol LDS	N-Rooks LDS	Thomas Clusters	Hilbert Sort

EMST	Shortest Tour (TSP)	Cluster	Weighted Median

Distance Prune	k Centers

Segment Sets

Graph-matched		Stochastic	Noded

Parallel	Perpendicular Path Segments	Polygon Interior Segments	weave Segments

Tiling & Subdivision

Random Quad Subdivision	Random Rect Subdivision	Random Triangle Subdivision	Hatch Subdivision

Square Grid	Doyle Spiral		Hexagon Tiling

Islamic Tiling	Penrose Tiling	Square-Triangle Tiling	Annular Bricks

Slice Division	Arc Division	Soft Cells	Aztec Diamond

Auxetic Tiling