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.
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
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)
| 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)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| 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.