Skip to main content

What?

This is a pure python library for finding the delaunay triangulation on given pointsets. Maybe one day voronoi tessellation will be added, since its based on the quad-edge datastructure, which makes finding the dual to each representations easy.

delaunay triangulation

Installation && Usage

Either clone this repository or install via pip:

pip install delaunay

An example usage looks like this:

from random import seed, uniform
from delaunay.quadedge.mesh import Mesh
from delaunay.quadedge.point import Vertex
from delaunay.delaunay import delaunay

if __name__ == "__main__":

    seed(123123123)

    N = 44 # number of vertices

    vertices = [Vertex(uniform(0, 100), uniform(0, 100)) for v in range(N)]

    m = Mesh() # this object holds the edges and vertices

    m.loadVertices(vertices)

    end = N - 1

    delaunay(m, 0, end) # computes the triangulation

    # populates a list of [org, dest], values for further manipulation
    lines = []
    for qe in m.quadEdges:
        if qe.org is not None:
            lines += [[[qe.org.x, qe.dest.x], [qe.org.y, qe.dest.y]]]

    # plotting, for example:

    # import matplotlib.pyplot as plt

    # fig, ax = plt.subplots()

    # for line in lines:
    #     start, end = line

    #     ax.plot(start, end)

    # plt.show()

How?

In their paper 'Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams'[0] from 1985, L. Guibas & J. Stolfi propose a divide-and-conquer-algorithm with all the rigor one can hope for. The algorithm runs in O(n log(n)), which should be fine, but for really huge sets R. Dwyers modification [1] of the original algo from 1986 should provide a significant improvement. For now i'll stick with the first one mentioned, but later maybe this work will progress.

Why?

In comparison with scipy[2] this library is consirably more lightweight. Of course scipy's delaunay is based on QHull[3], a library written in c, which means it runs ~40 times faster than a python implementation [4].

References

[0] Guibas, Leonidas and Stolfi, Jorge 'Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi' In: ACM Trans. Graph.4.2 (Apr.1985), pp. 74–123. issn: 0730-0301 doi:10.1145/282918.282923

[1] - Dwyer's Algorithm

[2] - Scipy Delaunay Implementation

[3] - QHull Delaunay Implementation

[4] - V-hill's Delaunay Implementation

Metadata

Release files for delaunay 1.0.5

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for delaunay 1.0.5
File Size Uploaded Provenance Actions
delaunay-1.0.5.tar.gz 7.1 kB Without provenance Details for delaunay-1.0.5.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for delaunay 1.0.5
File Interpreter ABI Platform Actions
delaunay-1.0.5-py3-none-any.whl Python 3 none any Details for delaunay-1.0.5-py3-none-any.whl

Total release size: 15.1 kB

Release files / delaunay-1.0.5.tar.gz

Download URL delaunay-1.0.5.tar.gz
Size 7.1 kB
Tags Source
SHA-256 checksum
How to use checksums
01fec6edd48497130df38e90af9b207c00b60ea4b9d8c647aad46cd3f85799bf
BLAKE2b-256 checksum
How to use checksums
191c03fbeb19396b8cf75ce67dcb9271371a45b6810b240b361b9c5cd368afe8
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.7.1 importlib_metadata/4.10.0 pkginfo/1.8.2 requests/2.27.1 requests-toolbelt/0.9.1 tqdm/4.62.3 CPython/3.9.2

Release files / delaunay-1.0.5-py3-none-any.whl

Download URL delaunay-1.0.5-py3-none-any.whl
Size 8.0 kB
Tags Python 3
SHA-256 checksum
How to use checksums
15613f30bfe47e360debe36ba083eb0c5767c539adb8f7d5036a570220b4c004
BLAKE2b-256 checksum
How to use checksums
5e0795ec8034569d8291d24b0e783bf6699bfa2a41ec388173208c635cfa027b
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.7.1 importlib_metadata/4.10.0 pkginfo/1.8.2 requests/2.27.1 requests-toolbelt/0.9.1 tqdm/4.62.3 CPython/3.9.2

Security for delaunay 1.0.5

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page