Skip to main content
Pangolin: Plane Geometry Library

License

⚠️ Work in Progress: This library is still under construction and contains bugs and missing features. Use in production environments is not recommended.

Pangolin (or pgl) is a C++ library for computational geometry in the plane and pypgl is the official python binding for it. It is designed to be pleasant to use and always exact. Calculations are exact using rational numbers (floating point is not accepted).

import pypgl as pgl

p = pgl.Point(1, 0)
q = pgl.Point(4, '15/2')
s = pgl.Segment(p, q)
t = pgl.Segment(0, 8, '7/3', 1)
if s.intersects(t):
    print(s, "intersects", t)
# Output: (1,0)--(4,15/2) intersects (0,8)--(7/3,1)

Shapes and Predicates

Family Shapes
0-dimensional Point
1-dimensional Segment, OrientedSegment, Line, OrientedLine, Ray, Polyline, MonotoneChain
2-dimensional Halfplane, Triangle, Rectangle, Disk, Convex, Polygon

The following predicates are implemented as methods of all shapes.

  • contains(Shape) Does it contain the other shape?
  • boundaryContains(Shape) Does its boundary contain the other shape?
  • interiorContains(Shape) Does it contain the other shape in the interior?
  • intersects(Shape) Do the two shapes intersect?
  • interiorsIntersect(Shape) Do the interiors of the two shapes intersect?
  • separates(Shape) Does one shape cut the other into two (or more) components?
  • crosses(Shape) Do both shapes separate each other?
import pypgl as pgl

o = pgl.Point()      # Point (0,0)
d = pgl.Disk(o, 10)  # Disk of radius 10 centered at (0,0)
if d.contains(o):
    print("Disk contains", o)
diam = d.diameter()
if d.contains(diam):
    print("Disk contains the diameter")
if not d.interiorContains(diam):
    print("Disk's interior does not contain the diameter")
# Output:
# Disk contains (0,0)
# Disk contains the diameter
# Disk's interior does not contain the diameter

Other Methods

Several other methods are supported by the shapes.

import pypgl as pgl

c = pgl.Convex([pgl.Point(0, 0), pgl.Point(1, 0), pgl.Point(1, 2), pgl.Point(0, 1)])
s = c.diameter()
print("The diameter of", c,
      "is defined by", s,
      "and has length", s.length())
# Output: The diameter of Convex[(0,0),(1,0),(1,2),(0,1)] is defined by (0,0)--(1,2) and has length 2.23607

Distances come in the Euclidean (squaredDistance, exact and therefore squared), Manhattan (distanceL1) and Chebyshev (distanceLInf) flavors, each with a Hausdorff variant between shapes.

Shapes are moved around with +/-/*//, and an arbitrary affine map is applied with a Transformation:

import pypgl as pgl

t = pgl.Transformation.rotation90() * pgl.Transformation.translation(2, 0)
print(t * pgl.Segment(0, 0, 5, 5))
# Output: (-5,7)--(0,2)

Visualization

A Canvas class is provided for visualization, exporting to SVG, PDF, or Ipe:

import pypgl as pgl

canvas = pgl.Canvas()
canvas.draw(pgl.Point(0, 0))

tri = pgl.Triangle(-1, -1, 0, 2, 1, -2)
canvas.stroke("green")
canvas.draw(tri)
canvas.stroke("blue")
canvas.draw(2*tri)
canvas.writeSVG("example2.svg")

Algorithms and Data Structures

PGL includes fundamental algorithms and data structures such as:

  • Convex hull: convexHull / convexHullExtended, computed with Graham scan.
  • Line segment intersection: sweep-line and brute-force pair enumeration plus detection predicates, all using rational numbers.
  • Sort points: in place by angle (sortAround) or Hilbert order (hilbertSort).
  • Polyomino enumeration: hole-free free polyominoes as Polygon objects.
  • ShapeTree: a kd-tree for points, generalized to a mix of any bounded shapes, answering range and nearest-neighbor queries.
  • Triangulation: including Delaunay and constrained Delaunay triangulations for points and polygons, with traversal queries and incremental insertion.

Installation

pypgl requires Python 3.9 or newer.

From PyPI

pip install pypgl

Pre-built wheels are published for CPython 3.9–3.13 on Linux (manylinux_2_28, x86_64), macOS (Apple Silicon), and Windows, so most users need no compiler.

From source

Installing from a source tree or directly from GitHub builds the extension locally and therefore needs a C++20 compiler (GCC 12+, Clang 15+, or, on Windows, the LLVM/ClangCL toolset). The header-only pgl library is fetched automatically by CMake — nothing else to install.

pip install git+https://github.com/gfonsecabr/pypgl.git

Development install

Work on the bindings from a checkout with an editable, in-place build:

git clone https://github.com/gfonsecabr/pypgl.git
cd pypgl
python3 -m venv .venv
.venv/bin/pip install scikit-build-core nanobind pytest
.venv/bin/pip install -e . --no-build-isolation
.venv/bin/python -m pytest tests/ -q

--no-build-isolation lets CMake find the venv's nanobind. Re-run the pip install -e . step after editing any src/*.cpp, since the editable install is what rebuilds the extension. To build against a local pgl checkout instead of the pinned upstream commit:

.venv/bin/pip install -e . --no-build-isolation \
  -C cmake.define.PGL_INCLUDE_DIR=/path/to/pgl/include

More Information

  • For a brief description, check the documents at the doc folder.
  • Shapes and canvases render inline in a Jupyter notebook — see canvas.md.
  • Check the C++ version.

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pypgl-0.4.0.tar.gz (1.7 MB view details)

Uploaded Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

pypgl-0.4.0-cp313-cp313-win_amd64.whl (1.2 MB view details)

Uploaded CPython 3.13Windows x86-64

pypgl-0.4.0-cp313-cp313-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (990.4 kB view details)

Uploaded CPython 3.13manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

pypgl-0.4.0-cp313-cp313-macosx_11_0_arm64.whl (1.0 MB view details)

Uploaded CPython 3.13macOS 11.0+ ARM64

pypgl-0.4.0-cp312-cp312-win_amd64.whl (1.2 MB view details)

Uploaded CPython 3.12Windows x86-64

pypgl-0.4.0-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (990.5 kB view details)

Uploaded CPython 3.12manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

pypgl-0.4.0-cp312-cp312-macosx_11_0_arm64.whl (1.0 MB view details)

Uploaded CPython 3.12macOS 11.0+ ARM64

pypgl-0.4.0-cp311-cp311-win_amd64.whl (1.2 MB view details)

Uploaded CPython 3.11Windows x86-64

pypgl-0.4.0-cp311-cp311-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (986.4 kB view details)

Uploaded CPython 3.11manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

pypgl-0.4.0-cp311-cp311-macosx_11_0_arm64.whl (1.0 MB view details)

Uploaded CPython 3.11macOS 11.0+ ARM64

pypgl-0.4.0-cp310-cp310-win_amd64.whl (1.2 MB view details)

Uploaded CPython 3.10Windows x86-64

pypgl-0.4.0-cp310-cp310-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (986.7 kB view details)

Uploaded CPython 3.10manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

pypgl-0.4.0-cp310-cp310-macosx_11_0_arm64.whl (1.0 MB view details)

Uploaded CPython 3.10macOS 11.0+ ARM64

pypgl-0.4.0-cp39-cp39-win_amd64.whl (1.2 MB view details)

Uploaded CPython 3.9Windows x86-64

pypgl-0.4.0-cp39-cp39-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (987.4 kB view details)

Uploaded CPython 3.9manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

pypgl-0.4.0-cp39-cp39-macosx_11_0_arm64.whl (1.0 MB view details)

Uploaded CPython 3.9macOS 11.0+ ARM64

File details

Details for the file pypgl-0.4.0.tar.gz.

File metadata

  • Download URL: pypgl-0.4.0.tar.gz
  • Upload date:
  • Size: 1.7 MB
  • Tags: Source
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for pypgl-0.4.0.tar.gz
Algorithm Hash digest
SHA256 0d43417bbd58dec18c1ee2f8cb8244c9baed681ce745d9ba54b70a92f67c915e
MD5 9ceee79279202350ffb5626b9ef30657
BLAKE2b-256 b35916956841d8671bcd5f112a3ec67e4362a5b27b9851b5002623e1bee00ad2

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0.tar.gz:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp313-cp313-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.4.0-cp313-cp313-win_amd64.whl
  • Upload date:
  • Size: 1.2 MB
  • Tags: CPython 3.13, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for pypgl-0.4.0-cp313-cp313-win_amd64.whl
Algorithm Hash digest
SHA256 fee1fe604925197ff60a34342f6e85989d8d941ab36b86bed4fcef65660598a0
MD5 03ddb3d239c6aac101a32f4f76ff3d69
BLAKE2b-256 6cf48230729e2aacc1ff3a9c8de7ad52216d37449444ea3bcd1a63931404eebc

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp313-cp313-win_amd64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp313-cp313-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp313-cp313-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 f83308b40575b446386cdfbfec30adfce3d7187993ebf47b674546da5a078697
MD5 13fb47363118fa26a23a37fd7f27a604
BLAKE2b-256 06244e73d01ab71167edb839e5ab15bb0ee3fe0cc2f60318f6e35a18ed146349

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp313-cp313-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp313-cp313-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp313-cp313-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 c0809ad33fc9bc1300710cf4632c0a5a75cfd5ac2bc1c66fda50727268c61ae2
MD5 04c688d8de6e865255e20e6c8250ed06
BLAKE2b-256 3b19fcb744a2bdc38fbc805bba04cc11e5359641391a5d89021f95835c2938f3

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp313-cp313-macosx_11_0_arm64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp312-cp312-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.4.0-cp312-cp312-win_amd64.whl
  • Upload date:
  • Size: 1.2 MB
  • Tags: CPython 3.12, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for pypgl-0.4.0-cp312-cp312-win_amd64.whl
Algorithm Hash digest
SHA256 c86e78de48d84e0c944f3480b727bff72fe57903e6934669e6a8bbffc525acd8
MD5 04cb0f7accf1f0d9b37bc24de6944b0f
BLAKE2b-256 82db29cb88cfe222e2c9cc2ed0c825430d7ce30ad28f0bd25e0702a8a1598d3e

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp312-cp312-win_amd64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 ab6f2b9c82bf17b5ca6237fb6ca34d5b8b8d6e6118f3f5e4960221f76d991c09
MD5 8208f31a95a57be4b5c3a4e7587ca333
BLAKE2b-256 c0b855db34e0444d789accfeb13f90ee56cc5f80f0dc79230e3e4d00b5dd264a

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp312-cp312-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp312-cp312-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 d018e987375984986984b73fe4492c444c3a82c66d8a5ab9c5891b07cb80e3fa
MD5 1dbdd67c795a3d88fc15492f5826db0d
BLAKE2b-256 4658000c8cd0031d46a2496b5482e5a2e70615e86a05ba38ef348f1fa60329e9

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp312-cp312-macosx_11_0_arm64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp311-cp311-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.4.0-cp311-cp311-win_amd64.whl
  • Upload date:
  • Size: 1.2 MB
  • Tags: CPython 3.11, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for pypgl-0.4.0-cp311-cp311-win_amd64.whl
Algorithm Hash digest
SHA256 e84487b9dbe3d80dd7d1551caadd4574ef1bedcc21e52084e904a5a33c3823ea
MD5 1446731c360329769bbc7cdb01e64920
BLAKE2b-256 4444bcbd2aeca015c04db770619abc9a4262d65a6b81bf55e9045d5d4315f1f3

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp311-cp311-win_amd64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp311-cp311-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp311-cp311-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 9ab644a04917adf40ae780aa6ffc9f059ef5611e4ad420345dca29a8dee2433c
MD5 08b9270ae5038228d23cc9bc8ff08c74
BLAKE2b-256 3afaddf612222443cdb5e280417ad0c427012291d36e080e390a99c4ccb97a39

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp311-cp311-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp311-cp311-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp311-cp311-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 996af8c73706fe38df56f88e9c30117d7b59da600392951361a1c8af84b146b3
MD5 dedf4bf8dea4e5a61cf5b6555aa12c66
BLAKE2b-256 77c0e1c0cffcea634bc80a196f0de3a8b27fd8ad40d361f4d9b72b85924ae7c9

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp311-cp311-macosx_11_0_arm64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp310-cp310-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.4.0-cp310-cp310-win_amd64.whl
  • Upload date:
  • Size: 1.2 MB
  • Tags: CPython 3.10, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for pypgl-0.4.0-cp310-cp310-win_amd64.whl
Algorithm Hash digest
SHA256 f959f80101219bff41668970c7e4443e05a33c1f68e4f92049b23d162250c807
MD5 234c9d2cb858cd5095a7257cac35a1bc
BLAKE2b-256 e4cdee1576406a3511ecabf7e9cbca143c7e9fd4aa02c9f8f1dade285107e835

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp310-cp310-win_amd64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp310-cp310-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp310-cp310-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 d2639bee3dd4e1d87bd781870494945a04919d377ddf9a4613d6f01e515bd3ed
MD5 7561a9e4aca0bf51fdda55f997b215f2
BLAKE2b-256 558c9c1738fe9dfc2d60fb45e722b7f0c21025df2f0e3c1c295a6bb2db883804

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp310-cp310-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp310-cp310-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp310-cp310-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 2bab591f1955623230ee22663cc3880395d6c5d62c2b21dbc206e2fe135abd51
MD5 72c0bddbd87e05bae9c5df41120fa409
BLAKE2b-256 ae07f78dfe05b45eedbff369ecb5dbacda6142821fed606168684ee7559cf464

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp310-cp310-macosx_11_0_arm64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp39-cp39-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.4.0-cp39-cp39-win_amd64.whl
  • Upload date:
  • Size: 1.2 MB
  • Tags: CPython 3.9, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for pypgl-0.4.0-cp39-cp39-win_amd64.whl
Algorithm Hash digest
SHA256 a8c3da28d983e8099f549f8bdd74ad98b88168f8e731f044eb3c5504f90aad43
MD5 0839992dc5f3b93004b70b4d2def3098
BLAKE2b-256 856526e026307d303f9185366f02484cc1ca89d5ef72db916801d03ae1db385e

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp39-cp39-win_amd64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp39-cp39-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.4.0-cp39-cp39-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 fa384608fc917eb99ce30f82c9d4a70cfe48c27cc08b25a177f65c9a3b4dceeb
MD5 32c12616c4dbde59ceb46f546eaedb3b
BLAKE2b-256 59f76fa8931d5a17451650b766af18aca8d591c3d65fb45b862eec000bb050a4

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp39-cp39-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file pypgl-0.4.0-cp39-cp39-macosx_11_0_arm64.whl.

File metadata

  • Download URL: pypgl-0.4.0-cp39-cp39-macosx_11_0_arm64.whl
  • Upload date:
  • Size: 1.0 MB
  • Tags: CPython 3.9, macOS 11.0+ ARM64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for pypgl-0.4.0-cp39-cp39-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 68fd0ed986aa6fa0440be0cb1ecad8d13de28aac347f261ed07075e750518a17
MD5 3eb06f2e8d4d5f23f433388c51c9fdfd
BLAKE2b-256 3bf150c823474941c4eb8919fc8eaceb155979700ff534885fd41a8eebcf589a

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.4.0-cp39-cp39-macosx_11_0_arm64.whl:

Publisher: wheels.yml on gfonsecabr/pypgl

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Depot Continuous Integration Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page