Skip to main content

quad-edge data structure

Project description

# PyDelaunator Test of implementation of a quad-edge data structure using python.

This little project is here to study quad-edge structure for further developments of [Delaunator](, which waits since a long time.

There is a small GUI (done with the awesome [pyglet]( module) that allow one to play with the triangulation.

## Installation/requirements Installation in one command, including dependancies:

pip install pydelaunator

## Usage The package run the GUI if launched directly:

python -m pydelaunator

Use –help for options.

The higher-level API is the [Placer object](pydelaunator/ See [tests](pydelaunator/test/ for other usage examples.

## Notes ### Goals This work is mainly here to prototype a better API and detect where and why are bugs in Delaunator.

Efficiency is not a primarily goal, altough, since interfacing python with other languages is a fun exercise, i probably will try some optimizations related to C. Similarly, some algorithms ideas could be easily tested here.

Therefore, PyDelaunator is also a playground for further researchs.

### Computational geometry [Codes used there](pydelaunator/ are mainly constitued from online ressources (SO, wikipedia). They are not toroughly [tested](pydelaunator/test/, but as far as the triangulation works.

Implementating them in C could probably speed them up a little, since in python arithmetic codes tends to be costly.

### Duality Vertex/data Maybe not the most optimized, but a mapping object/vertex with a dict is certainly the less invasive for end-user, [as implemented in the Placer object](pydelaunator/

Other ways to go:

  • client objects inheriting from Vertex

  • client objects keeping a reference to their vertex

These two ways are probably far more efficient in case of big data. However, if current API allow these, Placer object continue to track objects using the dict mapping. Modification of the Placer is needed, or an alternative implementation.

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

pydelaunator-0.0.15.tar.gz (35.7 kB view hashes)

Uploaded Source

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