Voronoi diagrams

[mo271]

a feature request: Voronoi diagrams, see https://groups.google.com/d/topic/sage-devel/JgqyInSu8S8/discussion

A list of things that could be included in an implementation of Voronoi diagrams could be:

• the graph structure of the Voronoi diagram and it's dual, the Delaunay triangulation
• generalizations
  • Voronoi diagrams with weights (possibly empty regions!)
  • Voronoi diagrams with respect to other metrics (regions not necessary convex Polyhedra anymore)
  • farthest points Voronoi diagrams
• a closest pair method for the list of points/ nearest neighbor
• a plotting routine in 2d and 3d

Perhaps in the file sage/geometry/triangulation/point_configuration.py

CC: @vbraun @jplab @sagetrac-tmonteil @pelegm

Component: geometry

Keywords: voronoi, delaunay, days84

Author: Moritz Firsching

Branch/Commit: 5dc6bd5

Reviewer: Jean-Philippe Labbé

Issue created by migration from https://trac.sagemath.org/ticket/13517

[mo271]

a first try

[mo271]

comment:1

Attachment: trac_#13517_voronoi_first_try.patch.gz

I added a patch just to see if I understood correctly how patching and the mercurial export etc works..

[vbraun]

comment:2

The patch is correct ;-)

You should format the examples in the docstring as in http://www.sagemath.org/doc/developer/conventions.html#docstring-markup-with-rest-and-sphinx, then they become tests that you can run with sage -t sage/geometry/voroni_diagram.py.

If you want to lay the path for more functionality you should create a class that holds the initial data (the points) and caches the polyhedral cells. Then other methods, for example a plot() method, can be easily added without having to pass lists of polyhedra around.

Also you don't have to hard-code floating-point doubles as the ring, you could allow exact rationals at the same time. This requires you to figure out what a good ring for the input points is, of course. You could just put them into a PointConfiguration and use

sage: pc = PointConfiguration([(1,2), (1,2/3)])
sage: pc.base_ring()
Rational Field
sage: pc = PointConfiguration([(1,2), (1,0.3)])
sage: pc.base_ring()
Real Field with 53 bits of precision

[mo271]

comment:3

Thanks for the hints, I will get cracking on this.

Replying to @vbraun:

The patch is correct ;-)

You should format the examples in the docstring as in http://www.sagemath.org/doc/developer/conventions.html#docstring-markup-with-rest-and-sphinx, then they become tests that you can run with sage -t sage/geometry/voroni_diagram.py.

If you want to lay the path for more functionality you should create a class that holds the initial data (the points) and caches the polyhedral cells. Then other methods, for example a plot() method, can be easily added without having to pass lists of polyhedra around.

Also you don't have to hard-code floating-point doubles as the ring, you could allow exact rationals at the same time. This requires you to figure out what a good ring for the input points is, of course. You could just put them into a PointConfiguration and use

sage: pc = PointConfiguration([(1,2), (1,2/3)])
sage: pc.base_ring()
Rational Field
sage: pc = PointConfiguration([(1,2), (1,0.3)])
sage: pc.base_ring()
Real Field with 53 bits of precision

[mo271]

Attachment: trac_#13517_new_class_initial_version.patch.gz

first working version

[mo271]

comment:5

I added a first version, which provides the basic functionality

[miguelmarco]

comment:6

Thanks for the work, i think it is a nice addition.

A couple of comments though.

-I don't understand why your patch adds the file voronoi_diagram.py.out. Is that made on purpose or is it a mistake?

-Unless i am missing something, i think that allowing exact fields (like rationals, or maybe even algebraic reals) should work just the same way. There is really no need to hard code RDF, it would be better to use the same field as the given entry. This should be a really trivial change: just define a self._field as self._points.base_ring(), and then replace RDF by self._field in the rest of your code.