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_Processing
  • Methods that process a shape in some way: compute hulls, partition, slice, 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

<details><summary>Processing IDE — Quick</summary> <p>

Download the latest PGS.jar from releases and simply drag-and-drop it onto the Processing IDE.

</p> </details> <details><summary>Processing IDE — Permanently</summary> <p>

Download the latest PGS.jar from releases and save it to Documents\Processing\libraries\PGS\library.

Result: Documents\Processing\libraries\PGS\library\PGS.jar.

(Note the .jar and the folder must be called PGS — rename the .jar if this is not the case).

</p> </details> <details><summary>Maven/Gradle</summary> <p>

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

</p> </details>

Examples

A number of example Processing sketches are provided in examples.

<p float="middle"> <a href="examples/partitionSmooth"><img src="resources/examples/partitionSmooth.png" alt="" width="24%"/></a> <a href="examples/textOffsetCurves"><img src="resources/examples/textOffsetCurves.png" alt="" width="24%"/></a> <a href="examples/ripplingTriangles"><img src="resources/examples/ripplingTriangles.png" alt="" width="24%"/></a> <a href="examples/contourMap"><img src="resources/examples/contourMap.png" alt="" width="24%"/></a> </p>

Illustrations

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

2D Boolean Operations

<table> <tr> <td align="center" valign="center"><b>Union</td> <td align="center" valign="center"><b>Intersection</td> <td align="center" valign="center"><b>Subtraction</td> <td align="center" valign="center"><b>Symmetric Difference</td> </tr> <tr> <td valign="top"><img src="resources/boolean/union.gif"></td> <td valign="top"><img src="resources/boolean/intersect.gif"></td> <td valign="top"><img src="resources/boolean/subtract.gif"></td> <td valign="top" ><img src="resources/boolean/symDifference.gif"></td> </tr> <tr> <td align="center" valign="center"><b>Complement</td> <td align="center" valign="center"><b>Mesh Union</td> <td align="center" valign="center"><b>Mesh Intersection</td> <td align="center" valign="center"><b>Mesh Subtraction</td> </tr> <tr> <td valign="top" width="25%"><img src="resources/boolean/complement.png"></td> <td valign="top" width="25%"><img src="resources/boolean/meshUnion.gif"></td> <td valign="top" width="25%"><img src="resources/boolean/intersectMesh.gif"></td> <td valign="top" width="25%"><img src="resources/boolean/subtractMesh.gif"></td> </tr> </table>

Transformation

<table> <tr> <td align="center" valign="center" colspan="2"><b>Rotate Around</td> <td align="center" valign="center"><b>Translate To</td> <td align="center" valign="center"><b>Touch Scale</td> </tr> <tr> <td valign="top" width="25%"><img src="resources/transform/rotateCenter.gif"></td> <td valign="top" width="25%"><img src="resources/transform/rotate.gif"></td> <td valign="top" width="25%"><img src="resources/transform/translateTo.gif"></td> <td valign="top" width="25%"><img src="resources/transform/touchScale.gif"></td> </tr> <tr> <td align="center" valign="center" colspan="2">Rotate a shape around its centroid or an arbitrary point.</td> <td align="center" valign="center">Translate a shape such that its centroid matches some position.</td> <td align="center" valign="center">Scale one shape such that it touches another.</td> </tr> <tr> <td align="center" valign="center"><b>Resize</td> <td align="center" valign="center"><b>Homothetic Transformation</td> <td align="center" valign="center"><b>Shear</td> <td align="center" valign="center"><b>Align</td> </tr> <tr> <td valign="top" width="25%"><img src="resources/transform/resize.gif"></td> <td valign="top" width="25%"><img src="resources/transform/homothetic.gif"></td> <td valign="top" width="25%"><img src="resources/transform/shear.gif"></td> <td valign="top" width="25%"><img src="resources/transform/align.gif"></td> </tr> <tr> <td align="center" valign="center"></td> <td align="center" valign="center">Projection-transform a shape with respect to a fixed point.</td> <td align="center" valign="center"></td> <td align="center" valign="center">Maximum-overlap alignment.</td> </tr> </table>

Geometric Predicates & Metrics

<table> <tr> <td align="center" valign="center"><b>Intersects</td> <td align="center" valign="center"><b>Contains Shape</td> <td align="center" valign="center"><b>Contains Point</td> <td align="center" valign="center"><b>Containing Cell</td> </tr> <tr> <td valign="top" align="center" width="25%"> <img src="resources/predicate/intersect.gif"><br>Do shapes intersect with each other?</td> <td valign="top" align="center" width="25%"><img src="resources/predicate/contains.gif"><br>Does one shape fully contain another?</td> <td valign="top" align="center" width="25%"><img src="resources/predicate/containsPoint.gif"><br>For individual points and point sets.</td> <td valign="top" align="center" width="25%"><img src="resources/predicate/containingCell.gif"><br>Which cell contains the query point?</td> </table>

Metrics

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

Contour

<table> <tr> <td align="center" valign="center" colspan="2"><b>Isolines</td> <td align="center" valign="center" colspan="2"><b>Offset Curves</td> </tr> <tr> <td valign="top"><img src="resources/contour/isolines.gif"></td> <td valign="top"><img src="resources/contour/isolines2.gif"></td> <td valign="top"><img src="resources/contour/miteredInterior.gif"></td> <td valign="top"><img src="resources/contour/miteredExterior.gif"></td> </tr> </tr> <tr> <td align="center" valign="center" colspan="2">Isolines from intra-shape euclidean distance, or point sets.</td> <td align="center" valign="center" colspan="2">Inner and exterior offset curves; based on <i>miter, bevel</i> or <i>round</i> offset styles.</td> </tr> <tr> <td align="center" valign="center"><b>Straight Skeleton</td> <td align="center" valign="center" colspan="2"><b>Medial Axis</td> <td align="center" valign="center"><b>Chordal Axis</td> </tr> <tr> <td valign="top" width="25%"><img src="resources/contour/straightSkeleton.png"></td> <td valign="top" width="25%"><img src="resources/contour/medialAxis.gif"></td> <td valign="top" width="25%"><img src="resources/contour/medialAxis.png"></td> <td valign="top" width="25%"><img src="resources/contour/chordalAxis.png"></td> </tr> </tr> <tr> <td align="center" valign="center"></td> <td align="center" valign="center" colspan="2">Medial axis transform with feature pruning via distance, area or <i>axial angle</i>. </td> <td align="center" valign="center">Chordal Axis Transform</td> </tr> <tr> <td align="center" valign="center"><b>Distance Field</td> <td align="center" valign="center"><b>Center Line</td> </tr> <tr> <td valign="top"><img src="resources/contour/distanceField.png"></td> <td valign="top"><img src="resources/contour/centerLine.gif"></td> </tr> </tr> <tr> <td align="center" valign="center">A contour map based on a distance field of a shape</td> </tr> </table>

Morphology

<table> <tr> <td align="center" valign="center"><b>Buffer</td> <td align="center" valign="center"><b>Erosion-Dilation</td> <td align="center" valign="center" colspan="2"><b>Minkowski Addition</td> </tr> <tr> <td valign="top" width="25%"><img src="resources/morphology/buffer.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/erosionDilation.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/minkSum.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/minkDiff.gif"></td> </tr> <tr> <td align="center" valign="center"></td> <td align="center" valign="center">A negative followed by a positive buffer (in a single operation).</td> <td align="center" valign="center" colspan="2">Minkowski sum and difference (a.k.a buffer one shape using another shape; the examples add a rotating & growing triangle).</td> </tr> <tr> <td align="center" valign="center"><b>Smoothing</td> <td align="center" valign="center"><b>Gaussian Smoothing</td> <td align="center" valign="center" colspan="2"><b>Rounding</td> </tr> <tr> <td valign="top"><img src="resources/morphology/smooth.gif"></td> <td valign="top"><img src="resources/morphology/gaussianSmooth.gif"></td> <td valign="top"><img src="resources/morphology/round.gif"></td> <td valign="top" ><img src="resources/morphology/round2.gif"></td> </tr> <tr> <td align="center" valign="center"><b>Radial Warp</td> <td align="center" valign="center"><b>Sine Warp</td> <td align="center" valign="center" colspan="2"><b>Field Warp</td> </tr> <tr> <td valign="top" width="25%"><img src="resources/morphology/radialWarp2.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/sineWarp.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/fieldWarp.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/fieldWarp2.gif"></td> </tr> <tr> <td align="center" valign="center"><b>Simplification</td> <td align="center" valign="center" colspan="2"><b>Chaikin Cutting</td> <td align="center" valign="center" colspan="2"><b>Interpolation</td> </tr> <tr> <td valign="top" width="25%"><img src="resources/morphology/simplifyVW.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/chaikinCut1.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/chaikinCut2.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/morph.gif"></td> </tr> <tr> <td align="center" valign="center"><b>Variable Buffer</td> <td align="center" valign="center"><b>Precision Reduction</td> <td align="center" valign="center"><b>Hobby Curve Simplification</td> <td align="center" valign="center"><b>Elliptic Fourier Smoothing</td> </tr> <tr> <td valign="top" width="25%"><img src="resources/morphology/variableBuffer.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/reducePrecision.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/hobbySimplify.gif"></td> <td valign="top" width="25%"><img src="resources/morphology/ellipticFourierSmooth.gif"></td> </tr> </table>

Hull

<table> <tr> <td align="center" valign="center" colspan="3"><b>Concave Hull</td> <td align="center"