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.
  • Runnable scripts live in the examples folder, ported one for one from pgl's own — predicates, canvas styling, a shape gallery, ShapeTree queries and constrained triangulation.
  • 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.5.0.tar.gz (1.8 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.5.0-cp313-cp313-win_amd64.whl (1.6 MB view details)

Uploaded CPython 3.13Windows x86-64

pypgl-0.5.0-cp313-cp313-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (1.4 MB view details)

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

pypgl-0.5.0-cp313-cp313-macosx_11_0_arm64.whl (1.5 MB view details)

Uploaded CPython 3.13macOS 11.0+ ARM64

pypgl-0.5.0-cp312-cp312-win_amd64.whl (1.6 MB view details)

Uploaded CPython 3.12Windows x86-64

pypgl-0.5.0-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (1.4 MB view details)

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

pypgl-0.5.0-cp312-cp312-macosx_11_0_arm64.whl (1.5 MB view details)

Uploaded CPython 3.12macOS 11.0+ ARM64

pypgl-0.5.0-cp311-cp311-win_amd64.whl (1.6 MB view details)

Uploaded CPython 3.11Windows x86-64

pypgl-0.5.0-cp311-cp311-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (1.3 MB view details)

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

pypgl-0.5.0-cp311-cp311-macosx_11_0_arm64.whl (1.5 MB view details)

Uploaded CPython 3.11macOS 11.0+ ARM64

pypgl-0.5.0-cp310-cp310-win_amd64.whl (1.6 MB view details)

Uploaded CPython 3.10Windows x86-64

pypgl-0.5.0-cp310-cp310-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (1.3 MB view details)

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

pypgl-0.5.0-cp310-cp310-macosx_11_0_arm64.whl (1.5 MB view details)

Uploaded CPython 3.10macOS 11.0+ ARM64

pypgl-0.5.0-cp39-cp39-win_amd64.whl (1.6 MB view details)

Uploaded CPython 3.9Windows x86-64

pypgl-0.5.0-cp39-cp39-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (1.3 MB view details)

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

pypgl-0.5.0-cp39-cp39-macosx_11_0_arm64.whl (1.5 MB view details)

Uploaded CPython 3.9macOS 11.0+ ARM64

File details

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

File metadata

  • Download URL: pypgl-0.5.0.tar.gz
  • Upload date:
  • Size: 1.8 MB
  • Tags: Source
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for pypgl-0.5.0.tar.gz
Algorithm Hash digest
SHA256 e4310d82d5fed86e4cc9a4c40034605e95478956f47616a069d6bb2c2fdb52aa
MD5 bbaf49c2d3018bc347253fdd14432149
BLAKE2b-256 98f9a39e292f6fcc2084eac3d08b52a86cb30e23a64d9a93ac042d6f2a5b9578

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp313-cp313-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.5.0-cp313-cp313-win_amd64.whl
  • Upload date:
  • Size: 1.6 MB
  • Tags: CPython 3.13, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for pypgl-0.5.0-cp313-cp313-win_amd64.whl
Algorithm Hash digest
SHA256 625237429f7a63539b50618ae631ac29ba245bdf15adfc6f94223eb1d036f09e
MD5 53faff0e0634c26a2797e3b9292fc41b
BLAKE2b-256 53068766e1191997b924d22c8555ae31839f834bfa7918de5bcb297532ca7113

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp313-cp313-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp313-cp313-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 6367700995248bee70ea51150c1a4f8e3cb4d69edc0465f07a4e5a59536bca6d
MD5 152ec548d9a40be8367672b1e3473984
BLAKE2b-256 56b3e96ad6151043d6c2e6a8b9194ea991bbfeb89e12ae5a8955e1943072ecd0

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp313-cp313-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp313-cp313-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 8c4e6041378558d1edce01c83cbce5489a06104179ba760894780564797bfafa
MD5 9fbeb555942a6653bca76c22e7acf576
BLAKE2b-256 b12af36ac6872426d835dd8fca5632114199570d26f653fe38f5b78f98d47e85

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp312-cp312-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.5.0-cp312-cp312-win_amd64.whl
  • Upload date:
  • Size: 1.6 MB
  • Tags: CPython 3.12, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for pypgl-0.5.0-cp312-cp312-win_amd64.whl
Algorithm Hash digest
SHA256 51fb53235843ce5554dce322204f25993da3a9f2f9186b2ca36a5e411753f008
MD5 2d2dda9553fdadae6889f57a1021d165
BLAKE2b-256 2cdae37aa4fc1d013677e5568f65e47c554804bbdd13ed56532eff18fcb6ffc2

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 01db67b02308e2ba953ba62792d4b67d5ed61249992b64f6036e14e76461e39a
MD5 ed2be321622f36625b41dfc1bb99f67e
BLAKE2b-256 7db1e4c458f457fb557658ea1c6879bc230a7422063af704e7eb436b4f704799

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp312-cp312-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp312-cp312-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 64592fbb768a6ddedd72f8235f657d579c751ebeac2ba47c582fc70ef358a5c8
MD5 f61627b0feba045e483c34b102c53ca8
BLAKE2b-256 b8ee5dbf7414775f0a7943c06587f2ddff71ffcd5ec1fa17045f23e2281cba0b

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp311-cp311-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.5.0-cp311-cp311-win_amd64.whl
  • Upload date:
  • Size: 1.6 MB
  • Tags: CPython 3.11, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for pypgl-0.5.0-cp311-cp311-win_amd64.whl
Algorithm Hash digest
SHA256 6c3516ed646b7e4b7e83f9639e8dcf6fce1cf06184b0dfa24b4fc35bb7d71de1
MD5 65157777d87a16b369adecf1c667396d
BLAKE2b-256 220cca424a0e19a2d54377ce8acbf5fde72c27d809bd5d358ab04f1209dccbbc

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp311-cp311-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp311-cp311-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 c9850c4db3e6af3cba6592b95c0b6a54e9e2a3fd46628e33c58133a57f9ddc8e
MD5 75254d6644e3319fc7c367151943916b
BLAKE2b-256 68ce14cb1004e489dbb97e6f6bab1cd034c260b6c93d3e8c87709104275a5fbb

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp311-cp311-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp311-cp311-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 79e153073aec6b54912657cc8983fa239ea7131d400f5dfea18fd4c17f2624be
MD5 c70c0e11208cc393a434257b4685be78
BLAKE2b-256 0e18d6fa7fb9fe7ab1455fe7e3bfe0d788249583c8aa149232086bbbfa90aa11

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp310-cp310-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.5.0-cp310-cp310-win_amd64.whl
  • Upload date:
  • Size: 1.6 MB
  • Tags: CPython 3.10, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for pypgl-0.5.0-cp310-cp310-win_amd64.whl
Algorithm Hash digest
SHA256 85d927fbde951d5691d7a59f17b9bd0994d0300886940a1d471048e28801c750
MD5 60efb51c1d7878b04d1962db69c9c66c
BLAKE2b-256 63c175fbae5fab4d37d4bc7e0720fb6acefcaa75bf3a7bfa2cb9bebc67186ce7

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp310-cp310-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp310-cp310-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 b77bca0a715bd187f653817973c127a78b9ba488dd31a662a697a6d8ccb972ed
MD5 7da6c92da4b1b98693e4c03ed82ba62d
BLAKE2b-256 5f8bcd46fa1c00f74a1bd84dd78e43fbcd5d224b79b7a7dab2e5cb5efc855a2c

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp310-cp310-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp310-cp310-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 4b8a916fcc4f3357ff094f725b64cb83bed26b70cd473af706618b89c35fee30
MD5 6900f1be8303388ac37642df0e4c8c5d
BLAKE2b-256 ce372b5ef96d67d71ffa8002c74b441cffd480e52d3a0273a8367c1f67e9c0c7

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp39-cp39-win_amd64.whl.

File metadata

  • Download URL: pypgl-0.5.0-cp39-cp39-win_amd64.whl
  • Upload date:
  • Size: 1.6 MB
  • Tags: CPython 3.9, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for pypgl-0.5.0-cp39-cp39-win_amd64.whl
Algorithm Hash digest
SHA256 decd71228df9eef6799aff73e5b96ea8ab50020b8d8c4ebc9086fff3fd8b7617
MD5 175cb60b8cd1b47a50559e07606da2a9
BLAKE2b-256 2c14718bd15cb2b53a1816f0236366242d8d280f81ef8fc46778a467e4125b9d

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp39-cp39-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for pypgl-0.5.0-cp39-cp39-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 ade6314bca4c890e4e8faf8e9c5fd726bfd5d004ea649f91e72e39e38bd14d5d
MD5 618490c5a2d56c7a3e24ffdd132ada1a
BLAKE2b-256 7cf786c80b533c28133ba9375c9125f99fa8f68aa8b669391ab5c61766fdb971

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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.5.0-cp39-cp39-macosx_11_0_arm64.whl.

File metadata

  • Download URL: pypgl-0.5.0-cp39-cp39-macosx_11_0_arm64.whl
  • Upload date:
  • Size: 1.5 MB
  • Tags: CPython 3.9, macOS 11.0+ ARM64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for pypgl-0.5.0-cp39-cp39-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 1164931d118ae45295a68b3e0b8434386d601a28ae7ed04a30bd07ebeca5303e
MD5 bd7b1f6318099cf3c348931c1c22205b
BLAKE2b-256 a586fb5d56e7118185bce19fb297be8cce886549f5d7c7941ef4ebf80680c70c

See more details on using hashes here.

Provenance

The following attestation bundles were made for pypgl-0.5.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