Skip to content

Latest commit

 

History

History
913 lines (827 loc) · 39.3 KB

README.md

File metadata and controls

913 lines (827 loc) · 39.3 KB

Lines of Code

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

Processing IDE — Quick

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

Processing IDE — Permanently

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).

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

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
  • 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

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
A contour map based on a distance field of a shape

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

Hull

Concave Hull Convex Hull of Polygons
Concave hull of point sets via breadth-first or depth-first approaches.
Convex Hull Snap Hull
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 Clean Coverage
Extract Holes Nest

Triangulation

Delaunay Triangulation Earcut Triangulation
Poisson Delaunay Triangulation
Delaunay triangulation of shapes where steiner points generated by poisson disk sampling are inserted.

Voronoi Diagrams

Voronoi Diagram (inner) Voronoi Diagram (compound)
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

Geometric Optimisation

Maximum Inscribed Circle Minimum Bounding Rectangle Maximum Inscribed Rectangle Maximum Perimeter Square
Minimum Bounding Circle Minimum Bounding Ellipse
Minimum Bounding Triangle Envelope Problem of Apollonius
Largest Empty Circle Largest Empty Circles Closest Point Pair Farthest Point Pair
Closest Vertex Circle Covering Visibility Polygon / Isovist
Bin Pack Rectangle Bin Pack
Hilbert 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 Distance Prune Hilbert Sort
EMST Cluster Weighted Median

Segment Sets

Graph-matched Stochastic Noded
Parallel Polygon Interior Segments

Tiling & Subdivision

Random Quad Subdivision Random Rect Subdivision Random Triangle Subdivision Hatch Subdivision
Islamic Tiling Doyle Spiral Hexagon Tiling
Penrose Tiling Square-Triangle Tiling