Skip to main content

No project description provided

Project description

delaunay-triangulation-and-its-dual-2d

The scipy.spatial module has data structures to construct Delaunay tessellation and Voronoi diagram, given a set of points. However, it does not link the attributes of the two diagrams even though duality exists between them. For example, each simplex in Delaunay diagram corresponds to a vertex in Voronoi diagram and there are cases that we may want to make use of this relationship.

Therefore, this small extension is written to blend the attributes of the dual. In current version, it only provides the Delaunay class to construct a 2D Delaunay diagram at initialization. Afterwards, you can call corresponding functions to get its dual. See section Usage for examples.

Installation

$ pip install delaunay-triangulation-and-its-dual-2d

Usage

Import packages and prepare points as a numpy array of shape (n, 2), where n is the number of points and 2 are the Cartesian coordinates of the point.

import numpy as np
import scipy.spatial

import delaunay_triangulation_and_its_dual_2d

points = np.array([[0, 0], [1, 0], [2, 0], [1, 1]], dtype=np.float32)

Voronoi iteration

If points are not well-distributed, the Voronoi graph of the points will contain lots of non-uniform polygons. Voronoi iteration, also called Lloyd's algorithm, could be used to offset the points so that the Voronoi graph generated from the new points are more uniformly sized.

rng = np.random.default_rng()
delaunay_triangulation_and_its_dual_2d.voronoi_iteration(
    points=points, rng=rng
)

Delaunay triangulation

Below is an example to initialize the delaunay_triangulation_and_its_dual_2d.Delaunay object and then plot the diagram using the scipy.spatial.delaunay_plot_2d function.

delaunay = delaunay_triangulation_and_its_dual_2d.Delaunay(points=points)
scipy.spatial.delaunay_plot_2d(delaunay.get_mocked_scipy_spatial_delaunay())

Voronoi tessellation (Circumcentric mesh)

Below is an example to initialize the delaunay_triangulation_and_its_dual_2d.Delaunay object and then plot the Voronoi diagram using the scipy.spatial.voronoi_plot_2d function.

delaunay = delaunay_triangulation_and_its_dual_2d.Delaunay(points=points)
scipy.spatial.voronoi_plot_2d(delaunay.get_mocked_scipy_spatial_voronoi())

Barycentric mesh

Below is an example to initialize the delaunay_triangulation_and_its_dual_2d.Delaunay object and then plot the Barycentric mesh diagram using the scipy.spatial.voronoi_plot_2d function.

delaunay = delaunay_triangulation_and_its_dual_2d.Delaunay(points=points)
scipy.spatial.voronoi_plot_2d(
    delaunay.get_barycentric_dual_as_mocked_scipy_spatial_voronoi()
)

Relationships between attributes

Attributes which have a one-to-one mapping with the given points have the same order as the points. FOr example, delaunay.points are the points provided at initialization. This first point delaunay.points[0] corresponds to the first delaunay triangle delaunay.triangles[0], which in turn corresponds to the first Voronoi vertex delaunay.voronoi_vertices[0].

Styles of codes and comments

  • Google Python Style Guide link

References

  • How do I derive a Voronoi diagram given its point set and its Delaunay triangulation? link
  • duhaime/lloyd. link

Remarks

Construction of the Delaunay diagram at initialization of delaunay_triangulation_and_its_dual_2d.Delaunay object is fast as it just calls scipy.spatial.Delaunay to get the attributes. Yet, the conversions to its dual is written in Python codes in this package so it is 3 - 5 times slower than calling scipy.spatial.Voronoi directly. You can make the comparison yourself using the "tests\delaunay\performance.py" script.

License

This project is licensed under the terms of the MIT license.

Project details


Download files

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

Source Distribution

Built Distribution

File details

Details for the file delaunay_triangulation_and_its_dual_2d-0.1.6.tar.gz.

File metadata

File hashes

Hashes for delaunay_triangulation_and_its_dual_2d-0.1.6.tar.gz
Algorithm Hash digest
SHA256 8c9dcdde32cb611292a8120b3f4dcf9a1cc071298de50ec8c5a66ac251bd3a72
MD5 886524b5828fce6826240803e5d8c8fa
BLAKE2b-256 b034e61c3615dc15b707faa2ad1d0edc417a4816a70f6cb85d76dccae0d43fd8

See more details on using hashes here.

File details

Details for the file delaunay_triangulation_and_its_dual_2d-0.1.6-py3-none-any.whl.

File metadata

File hashes

Hashes for delaunay_triangulation_and_its_dual_2d-0.1.6-py3-none-any.whl
Algorithm Hash digest
SHA256 d28dfbdd73e1b98455929e9199408556642d0ce3b37ec7cd80b5658e97da6306
MD5 e817646d6a1adcc16d83c42b46ec55fc
BLAKE2b-256 3089f03fa616813c8eacbb2db07876ffea018789f41d456bcfaa235d9eeea6e2

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page