Metadata-Version: 2.1
Name: pypgl
Version: 0.7.0
Summary: Python bindings for the Pangolin (pgl) exact geometry library
Author: Guilherme D. da Fonseca
License: MIT License
         
         Copyright (c) 2026 Guilherme D. da Fonseca
         
         Permission is hereby granted, free of charge, to any person obtaining a copy
         of this software and associated documentation files (the "Software"), to deal
         in the Software without restriction, including without limitation the rights
         to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
         copies of the Software, and to permit persons to whom the Software is
         furnished to do so, subject to the following conditions:
         
         The above copyright notice and this permission notice shall be included in all
         copies or substantial portions of the Software.
         
         THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
         IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
         FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
         AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
         LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
         OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
         SOFTWARE.
         
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: POSIX :: Linux
Classifier: Operating System :: MacOS
Classifier: Operating System :: Microsoft :: Windows
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Typing :: Typed
Project-URL: Homepage, https://github.com/gfonsecabr/pypgl
Project-URL: Repository, https://github.com/gfonsecabr/pypgl
Project-URL: pgl (C++ library), https://github.com/gfonsecabr/pgl
Requires-Python: >=3.10
Description-Content-Type: text/markdown

<img align="left" src="https://raw.githubusercontent.com/gfonsecabr/pypgl/main/doc/figures/logo.png" width="23%"/>

<picture>
  <source media="(prefers-color-scheme: dark)" srcset="https://raw.githubusercontent.com/gfonsecabr/pypgl/main/doc/figures/logotextdark.svg"/>
  <img alt="Pangolin: Plane Geometry Library" src="https://raw.githubusercontent.com/gfonsecabr/pypgl/main/doc/figures/logotext.svg" width="65%"/>
</picture>

<!-- [![Tests](https://github.com/gfonsecabr/pgl/actions/workflows/tests.yml/badge.svg)](https://github.com/gfonsecabr/pgl/actions/workflows/tests.yml)
[![Standard](https://img.shields.io/badge/C%2B%2B-20/23/26-rgb(10,66,158).svg)](https://en.wikipedia.org/wiki/C%2B%2B#Standardization) -->
[![License](https://img.shields.io/badge/license-MIT-rgb(216,134,42).svg)](https://opensource.org/licenses/MIT)
<!-- [![Benchmarks](https://img.shields.io/badge/benchmarks-online-rgb(21,153,135).svg)](https://gfonsecabr.github.io/pgl/benchmarks/index.html) -->

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

[Pangolin](https://github.com/gfonsecabr/pgl) (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).

```python
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)
```

There are many more [illustrated examples](examples/) that give a good overview of the library's features and syntax.


## Shapes and Predicates

| Family | Shapes |
| --- | --- |
| 0-dimensional | [`Point`](doc/shapes.md#point) |
| 1-dimensional | [`Segment`](doc/shapes.md#segment), [`OrientedSegment`](doc/shapes.md#oriented-segment), [`Line`](doc/shapes.md#line), [`OrientedLine`](doc/shapes.md#oriented-line), [`Ray`](doc/shapes.md#ray), [`Polyline`](doc/shapes.md#polyline), [`MonotoneChain`](doc/shapes.md#monotonechain) |
| 2-dimensional | [`Halfplane`](doc/shapes.md#half-plane), [`Triangle`](doc/shapes.md#triangle), [`Rectangle`](doc/shapes.md#rectangle), [`Disk`](doc/shapes.md#disk), [`Convex`](doc/shapes.md#convex), [`Polygon`](doc/shapes.md#polygon), [`PolygonWithHoles`](doc/shapes.md#polygon-with-holes), [`PolygonSet`](doc/shapes.md#polygon-set), [`HalfplaneIntersection`](doc/shapes.md#halfplane-intersection) |

The following [predicates](doc/shape_methods.md#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?

```python
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](doc/shape_methods.md) are supported by the shapes.

```python
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. `samePointSet` asks whether two shapes cover
the same points, across types and regardless of how each is written.

The [boolean operations](doc/shape_methods.md#boolean-operations)
(`regularizedUnion`, `difference`, `symmetricDifference`,
`regularizedIntersection`) and the
[Minkowski sum](doc/shape_methods.md#minkowski-sum) are closed over the region
shapes, so a result feeds straight back in. Its dual, the
[Minkowski erosion](doc/shape_methods.md#minkowski-erosion), answers where a
shape *fits* inside another:

```python
import pypgl as pgl

square = pgl.Polygon([pgl.Point(0,0), pgl.Point(10,0), pgl.Point(10,10), pgl.Point(0,10)])
holed = square.difference(pgl.Rectangle(pgl.Point(3,3), pgl.Point(7,7)))
print(holed.area(), holed.holeCount())
# Output: 84 1
```

Shapes are moved around with `+`/`-`/`*`/`/`, and an arbitrary affine map is
applied with a [`Transformation`](doc/shape_methods.md#transformations):

```python
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](doc/canvas.md), exporting to SVG, PDF, or [Ipe](https://ipe.otfried.org/):

<img align="right" src="https://raw.githubusercontent.com/gfonsecabr/pypgl/main/doc/figures/example2.svg" width="200"/>

```python
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

<img align="right" src="https://raw.githubusercontent.com/gfonsecabr/pgl/main/doc/figures/algds.svg" width="180"/>

Pangolin includes [fundamental algorithms](doc/algorithms.md):

- **Convex hull** computed with Graham scan.
- Line segment intersection: **Bentley-Ottmann sweep line** using rational numbers.
- **Minkowski sum**, **Minkowski erosion** and **boolean operations**.
- **Visibility** graph and visibility polygon.
- Find the **closest pair** of points using divide and conquer.
- Smallest **enclosing disk and rectangle**.
- Sort points by angle or Hilbert order.

 and [data structures](doc/data_structures.md):

- **Kd-tree** for points and a generalization for other bounded shapes.
- **Interval tree** to use 1-dimensional queries on projections.
- **Triangulation** including **Delaunay** and **constrained Delaunay** triangulations for points and polygons.
- **Arrangement** of lines, line segments, and rays with a **trapezoidal map** for fast point location.
- Graph class for combinatorial algorithms like **Dijkstra** and **Prim** that can be used to compute Euclidean minimum spanning trees and shortest paths among obstacles.


## Installation

`pypgl` requires **Python 3.10 or newer**. Up to 0.6.0 the floor was 3.9, which
reached end-of-life in October 2025; 3.9 users can stay on that release.

### From PyPI

```bash
pip install pypgl
```

Pre-built wheels are published for CPython 3.10–3.14 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.

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

### Development install

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

```bash
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:

```bash
.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](doc/).
- Runnable scripts live in the [examples folder](examples/) — predicates, canvas
  styling, a shape gallery, `ShapeTree` queries, constrained triangulation,
  Minkowski sums, enclosing shapes, minimum spanning trees, visibility, robot
  motion planning, arrangements and Voronoi diagrams.
- Shapes and canvases render inline in a Jupyter notebook — see [canvas.md](doc/canvas.md#inline-display-in-jupyter).
- Check the [C++ version](https://github.com/gfonsecabr/pgl).
