Opened 10 years ago

Closed 5 years ago

# Voronoi diagrams

Reported by: Owned by: moritz mhampton minor sage-8.0 geometry voronoi, delaunay, days84 vbraun, jipilab, tmonteil, pelegm Moritz Firsching Jean-Philippe Labbé N/A 5dc6bd5 5dc6bd55273408801d8b79681c985ad2a91f5443

### Description

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

a first try

### comment:1 Changed 10 years ago by moritz

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

### comment:2 follow-up: ↓ 3 Changed 10 years ago by 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
```

### comment:3 in reply to: ↑ 2 Changed 10 years ago by moritz

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

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
```

### Changed 10 years ago by moritz

first working version

### comment:4 Changed 10 years ago by moritz

• Milestone changed from sage-feature to sage-5.4
• Status changed from new to needs_review

### comment:5 Changed 10 years ago by moritz

I added a first version, which provides the basic functionality

### comment:6 Changed 10 years ago by mmarco

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

-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.

reviewed

### comment:7 Changed 10 years ago by moritz

thanks for looking at the file.

• the file voronoi_diagram.py.out was indeed a mistake, the new patch does not include that file.
• I introduced a self._base_ring variable to handle QQ and RDF depending on input, as you suggested. (Now if the base_ring of the PointConfiguration? is a subring of the rationals, it uses QQ, otherwise RDF)

### comment:8 Changed 9 years ago by moritz

• Milestone changed from sage-5.6 to sage-5.5

### comment:9 follow-up: ↓ 10 Changed 9 years ago by mmarco

Would it be a lot of trouble to introduce also the posibility of using algebraic extensions of QQ as base ring? Arithmetic in those cases may be slow, but i can imagine some situations where it would be important to know the vertices of the diagram in an exact form.

### comment:10 in reply to: ↑ 9 Changed 9 years ago by moritz

Would it be a lot of trouble to introduce also the possibility of using algebraic extensions of QQ as base ring? Arithmetic in those cases may be slow, but i can imagine some situations where it would be important to know the vertices of the diagram in an exact form.

I don't see how one could easily adapt the algorithm for algebraic extensions of QQ for the following reason:

The Polyhedron-method only works with QQ and RDF.

If you really want support for extensions of QQ, either the algorithm of finding the Voronoi-diagram has to be changed, or one has adapt the Polyhedron method. Both are nontrivial tasks, which might make a good upgrade later on.

### comment:11 Changed 9 years ago by kcrisman

And so forth. And Delaunay triangulations exist in matplotlib too, I think... would it be faster to use that, especially since they fixed the problem we had in #13167?

### comment:12 Changed 9 years ago by ncohen

Hellooooooooooooo !!

Just thought I would add a link toward d3.js here. It's a javascript library that can be used to plot a lot of things, and there's an example of a Voronoi Diagram on its website :

I wrote a patch (#14953) that uses this library to draw graphs `:-)`

Nathann

### comment:13 Changed 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:14 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:15 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:16 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:17 Changed 7 years ago by jipilab

• Milestone changed from sage-6.4 to sage-6.8

Hi Moritz,

What is the status of the patch? Was it migrated to the git format at all?

JP

### comment:18 Changed 7 years ago by moritz

Dear JP,

I haven't touched the file for a long time, I don't think it ever has been migrated.

### comment:19 Changed 7 years ago by chapoton

• Status changed from needs_review to needs_work

needs a git branch

### comment:20 Changed 5 years ago by moritz

• Branch set to u/moritz/voronoi

### comment:21 Changed 5 years ago by moritz

• Commit set to 7dda65c8901ba952a1df98123c4694f7cd59220c
• Status changed from needs_work to needs_review

I adressed the comments made by mmarco: The class now handles all the input (QQ, RDF and AA) that polyhedron can take as input.

As for the comments by kcrisman and ncohen: There are certainly much faster methods to calculate the voronoi diagram and the delaunay triangulation; I just wanted to put forward a first working version, that is conceptually clear and can be improved later.

Two things that could easily be added are plotting in the 3d case and adding a function to the point-configuration class giving back the voronoi-diagram.

New commits:

 ​44cc3a4 `starting with the old patch` ​7dda65c `polished the first version a bit`

### comment:22 Changed 5 years ago by git

• Commit changed from 7dda65c8901ba952a1df98123c4694f7cd59220c to 854c9eccdbf253d012d5daf6f0a96e20ecedeed3

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​6422be4 `starting with the old patch` ​854c9ec `polished the first version a bit`

### comment:23 Changed 5 years ago by moritz

rebased in order to merge cleanly with develop

### comment:24 Changed 5 years ago by chapoton

one failing doctest, probably you should sort the result

### comment:25 Changed 5 years ago by git

• Commit changed from 854c9eccdbf253d012d5daf6f0a96e20ecedeed3 to 78b66af8a81beaea5d2d8309b714926cc0457141

Branch pushed to git repo; I updated commit sha1. New commits:

 ​78b66af `points are now resorted if necessary`

### comment:26 Changed 5 years ago by moritz

thanks for looking at it, chapoton; I tried to settle the issue, will do more testing (and add more doctests) later

New commits:

 ​78b66af `points are now resorted if necessary`

### comment:27 Changed 5 years ago by git

• Commit changed from 78b66af8a81beaea5d2d8309b714926cc0457141 to ccf7a5189acd408783604ea36b643c68f1ed0a33

Branch pushed to git repo; I updated commit sha1. New commits:

 ​ccf7a51 `more doctests and correct reordering of the cells`

### comment:28 Changed 5 years ago by moritz

I would really be happy if someone could review this basic version of implementing Voronoi-diagrams. Once this is done I would like to

• make the calculation of the voronoi diagram faster
• implement 3d-plotting (this will be somewhat easy)
• make sure that one can take elements from Number Fields other than AA as input
• allow weights

### comment:29 Changed 5 years ago by chapoton

• Branch changed from u/moritz/voronoi to public/13517
• Commit changed from ccf7a5189acd408783604ea36b643c68f1ed0a33 to f77b6ca948bd5b41a4385e4a35b1730c876541dc

I made a cleanup of the code and doc, look at the diff to learn what you should have done.

New commits:

 ​975e3cc `Merge branch 'u/moritz/voronoi' in 7.5.rc1` ​f77b6ca `trac 13517 code and doc cleanup`

### comment:30 Changed 5 years ago by git

• Commit changed from f77b6ca948bd5b41a4385e4a35b1730c876541dc to 90bfdd155772b71fa19d0f2e187a996724a4479f

Branch pushed to git repo; I updated commit sha1. New commits:

 ​90bfdd1 `trac 13517 some more details`

### comment:31 Changed 5 years ago by git

• Commit changed from 90bfdd155772b71fa19d0f2e187a996724a4479f to 49cd896648e382c7cff10d500f929cb7d70026b6

Branch pushed to git repo; I updated commit sha1. New commits:

 ​49cd896 `added 'AA' in the NotImplementedError in the init`

### comment:32 Changed 5 years ago by moritz

Thank you very much, Frédéric, for cleaning up the code! I read carefully the changes and learned a lot!

### comment:33 Changed 5 years ago by git

• Commit changed from 49cd896648e382c7cff10d500f929cb7d70026b6 to 1845492dec4cd22960b0af2573605af1932e8741

Branch pushed to git repo; I updated commit sha1. New commits:

 ​1845492 `adding a doctest for input an invalid base ring`

### comment:36 Changed 5 years ago by pelegm

Just a question: why would the colours be necessarily random? It would probably be best to leave that optional. I would be happy to use the `plot` method with a list/map of colours for the vertices (that is, for the cells dominated by the vertices). This is, in fact, the main use of such diagrams in percolation theory (in which it is customary to colour the cells blue and red).

### comment:37 Changed 5 years ago by chapoton

• Milestone changed from sage-6.8 to sage-7.6
• Status changed from needs_review to needs_work

one failing doctest, see patchbot report

### comment:38 Changed 5 years ago by git

• Commit changed from 1845492dec4cd22960b0af2573605af1932e8741 to 984f495310ce85dbc4a129587402274a5d9e4513

Branch pushed to git repo; I updated commit sha1. New commits:

 ​efc25f6 `starting with the old patch` ​0def0ad `polished the first version a bit` ​8da57de `points are now resorted if necessary` ​5b582a0 `more doctests and correct reordering of the cells` ​caefa55 `trac 13517 code and doc cleanup` ​a2c0f6a `trac 13517 some more details` ​ec2b584 `added 'AA' in the NotImplementedError in the init` ​3ddad48 `adding a doctest for input an invalid base ring` ​5474325 `fixed description of points, added option for color` ​984f495 `Merge branch 'public/13517' of git://trac.sagemath.org/sage into voronoi`

### comment:39 Changed 5 years ago by moritz

• Status changed from needs_work to needs_review

I fixed the failing doctest (which was due to a change here: #22132)

Also I addressed the comment by pelegm and now provide an extra "cell_colors" option for plotting. However, plotting can (and should) be improved somewhat, but this should be a seperate ticket. Since the routine provides the polyhedra that are the cells, one can easily adapt the favorite style for plotting (possible with wireframe etc.)

I somehow messed up the git history, a bit, but the patch should now work..

### comment:40 Changed 5 years ago by jipilab

All tests pass on 7.6.b4.

Running:

sage -t --warn-long src/sage/geometry/voronoi_diagram.py

The test on line 49:

DV = voronoi_diagram([[AA(c) for c in v] for v in polytopes.dodecahedron().vertices_list()]); DV

was flagged as long on my machine; it took around 4-5 sec. in average, but if you tell me that it is not flagged on a newer machine, then I guess it is okay.

I would put the "TODOs" in the description of the ticket inside the file in the doc, so that it is not only to be found here. (Similar as EXAMPLES and TESTS).

In the examples for plot, the backslash produces a series of spaces to align the newlines when typing .plot? . I would remove that unless it is desired...

Otherwise, it looks good to me.

### comment:41 Changed 5 years ago by jipilab

• Status changed from needs_review to needs_work

### comment:42 Changed 5 years ago by git

• Commit changed from 984f495310ce85dbc4a129587402274a5d9e4513 to 28b3461cca77dfd386915cfe84422e5507cf3abf

Branch pushed to git repo; I updated commit sha1. New commits:

 ​d9469fd `changed dodehedron to pentagon to get faster doctest` ​28b3461 `added TODOs and removed backslashes`

### comment:43 Changed 5 years ago by moritz

• Status changed from needs_work to needs_review

Thanks for taking a look at it, JP!

I have

• made the long doctest faster
• removed the slashes
• added a list of TODOs

### comment:44 Changed 5 years ago by git

• Commit changed from 28b3461cca77dfd386915cfe84422e5507cf3abf to 61078e71630a79efe4d56dcf3c2abe97affb9b98

Branch pushed to git repo; I updated commit sha1. New commits:

 ​61078e7 `whitespace`

### comment:46 Changed 5 years ago by jipilab

Hi Moritz,

Could you change the description of the ticket also to include the TODO?

There is a second ":" missing after the examples of the class. Otherwise, it looks okay.

### comment:47 Changed 5 years ago by git

• Commit changed from 61078e71630a79efe4d56dcf3c2abe97affb9b98 to f980041ed5dcb1634c1127a491dd7e5cb3024917

Branch pushed to git repo; I updated commit sha1. New commits:

 ​a2c0b08 `improve docstring` ​f980041 `Merge branch 'develop' into voronoi`

### comment:48 Changed 5 years ago by moritz

TODOs are included and the docstring is improved

### comment:49 Changed 5 years ago by jipilab

All tests pass on 7.6.beta6.

The doc does not build: There is a double colon on line 16.

Otherwise, it looks good to me. Once you fixed it, you can put a positive review on my behalf.

### comment:50 Changed 5 years ago by jipilab

• Reviewers set to Jean-Philippe Labbé

### comment:51 Changed 5 years ago by jipilab

• Dependencies set to #22496

Dear Moritz,

The doc folder geometry is renamed in #22496. I guess it would make sense to make a dependancy on this ticket to avoid to have to add it and then have to move it.

What do you think?

### comment:52 Changed 5 years ago by vdelecroix

Sage classes must be caml case `voronoi_diagram -> VoronoiDiagram`.

### comment:53 Changed 5 years ago by git

• Commit changed from f980041ed5dcb1634c1127a491dd7e5cb3024917 to 5026d3f483e958a2d0c4024aa607f4b17f1f689b

Branch pushed to git repo; I updated commit sha1. New commits:

 ​5026d3f `changed class name to CamelCase`

### comment:54 Changed 5 years ago by git

• Commit changed from 5026d3f483e958a2d0c4024aa607f4b17f1f689b to 5f6bb85be3d11e135789c02bb980c93eace2f877

Branch pushed to git repo; I updated commit sha1. New commits:

 ​5f6bb85 `removed a colon`

### comment:55 Changed 5 years ago by moritz

Thanks for the comments, JP and Vincent! I adressed them; should be better now.

### comment:56 Changed 5 years ago by git

• Commit changed from 5f6bb85be3d11e135789c02bb980c93eace2f877 to 35dc80b4f778c4ca6be65157d0fbd1d3418a4844

Branch pushed to git repo; I updated commit sha1. New commits:

 ​35dc80b `improved TODO in docstring`

### comment:57 Changed 5 years ago by jipilab

• Status changed from needs_review to needs_work

• The reference should be put in the file `SAGE_ROOT/src/doc/en/reference/references/index.rst`
• In .plot() there are 2 lines after the `INPUT`
• When there is an optional parameter, the syntax should be something like

` - p -- (default: 2) a positive prime integer`

In order to scan through the python conventions, you can use a pep8 plugin to scan your file for such things

### comment:58 Changed 5 years ago by git

• Commit changed from 35dc80b4f778c4ca6be65157d0fbd1d3418a4844 to 63507e1a9d16d9dc1b55016ce081a440a9de4eb2

Branch pushed to git repo; I updated commit sha1. New commits:

 ​63507e1 `moved reference and other small improvements`

### comment:59 Changed 5 years ago by moritz

• Status changed from needs_work to needs_review

Thank you JP! I used pep8 to improve some more little things..

### comment:60 Changed 5 years ago by jipilab

Salut Moritz,

• Spacing after commas in the examples will make reading easier
• Input of plot: there is an "8" at the end of a line

Then let's see if the doc builds and it could be merged after #22496.

### comment:61 Changed 5 years ago by git

• Commit changed from 63507e1a9d16d9dc1b55016ce081a440a9de4eb2 to 835929b18456a3672368440a8bae6edeb85b4800

Branch pushed to git repo; I updated commit sha1. New commits:

 ​835929b `spaces and removed 8`

### comment:62 Changed 5 years ago by git

• Commit changed from 835929b18456a3672368440a8bae6edeb85b4800 to 90477d40f88b27ae04ca1620af61754496991a2f

Branch pushed to git repo; I updated commit sha1. New commits:

 ​90477d4 `changed reference abbreviation`

### comment:63 Changed 5 years ago by moritz

• Dependencies #22496 deleted

I remove the dependency, because it doesn't build without errors.

### comment:64 Changed 5 years ago by jipilab

Hi Moritz,

Well, all right, then the ticket #22496 will depend on this one. That's why I was asking if it was okay to put the dependency on this one.

Anyhow, that's not important.

### comment:65 Changed 5 years ago by jipilab

• Status changed from needs_review to positive_review

There is no doc errors anymore. Looks good!

### comment:66 Changed 5 years ago by vbraun

• Status changed from positive_review to needs_work

Merge conflict, wait for next beta

### comment:67 Changed 5 years ago by jipilab

There is going to be a conflict with #22496. I guess rebasing will just do the thing. Let's wait some time that the "rc" versions pass...

### comment:68 Changed 5 years ago by jipilab

Dear Moritz,

I guess you can now rebase and once the bot gives the green light, I'll give positive review again.

### comment:69 Changed 5 years ago by jipilab

• Milestone changed from sage-7.6 to sage-8.0

### comment:70 Changed 5 years ago by git

• Commit changed from 90477d40f88b27ae04ca1620af61754496991a2f to 7a7905ddf8535b5a3637272a984add13e2a22fc8

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​ef78175 `Voronoi diagram merge` ​7a7905d `added to new reference index`

### comment:71 Changed 5 years ago by moritz

Ok, just rebasing didn't qute work, I did another merge (and squashed). In any case I hope the bot doesn't complain now.

I added it to the misc section in the discrete geometry reference.

Let's see what the bot thinks.

### comment:72 Changed 5 years ago by moritz

• Status changed from needs_work to needs_review

### comment:73 Changed 5 years ago by jipilab

• Status changed from needs_review to needs_work

Hi Moritz,

There is a doctest failure:

```File "voronoi_diagram.py", line 197, in sage.geometry.voronoi_diagram.VoronoiDiagram.regions
Failed example:
V = VoronoiDiagram([[1, 3, .3], [2, -2, 1], [-1, 2, -.1]]); V.regions()
Expected:
{P(1.00000000000000, 3.00000000000000, 0.300000000000000): A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line,
P(2.00000000000000, -2.00000000000000, 1.00000000000000): A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line,
P(-1.00000000000000, 2.00000000000000, -0.100000000000000): A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line}
Got:
{P(1.00000000000000, 3.00000000000000, 0.300000000000000): A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line,
P(-1.00000000000000, 2.00000000000000, -0.100000000000000): A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line,
P(2.00000000000000, -2.00000000000000, 1.00000000000000): A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line}
**********************************************************************

```

I guess the output should fix the order. Or change the doctest.

### comment:74 Changed 5 years ago by git

• Commit changed from 7a7905ddf8535b5a3637272a984add13e2a22fc8 to fc3c49a23b377822ca25f7fd93bfbee31ea2391a

Branch pushed to git repo; I updated commit sha1. New commits:

 ​fc3c49a `make doctest independent of order in dict`

### comment:75 Changed 5 years ago by tscrim

It is better if you use:

```            sage: V.regions() == {P[0]: Polyhedron(base_ring=RDF, lines=[(-RDF(0.375), RDF(0.13888888890000001), RDF(1.5277777779999999))],
....:                                                 rays=[(RDF(9), -RDF(1), -RDF(20)), (RDF(4.5), RDF(1), -RDF(25))],
....:                                                 vertices=[(-RDF(1.1074999999999999), RDF(1.149444444), RDF(9.0138888890000004))]),
....:                 P[1]: Polyhedron(base_ring=RDF, lines=[(-RDF(0.375), RDF(0.13888888890000001), RDF(1.5277777779999999))],
....:                                                 rays=[(RDF(9), -RDF(1), -RDF(20)), (-RDF(2.25), -RDF(1), RDF(2.5))],
....:                                                 vertices=[(-RDF(1.1074999999999999), RDF(1.149444444), RDF(9.0138888890000004))]),
....:                 P[2]: Polyhedron(base_ring=RDF, lines=[(-RDF(0.375), RDF(0.13888888890000001), RDF(1.5277777779999999))],
....:                                                 rays=[(RDF(4.5), RDF(1), -RDF(25)), (-RDF(2.25), -RDF(1), RDF(2.5))],
....:                                                 vertices=[(-RDF(1.1074999999999999), RDF(1.149444444), RDF(9.0138888890000004))])}
```

### comment:76 Changed 5 years ago by git

• Commit changed from fc3c49a23b377822ca25f7fd93bfbee31ea2391a to 5dc6bd55273408801d8b79681c985ad2a91f5443

Branch pushed to git repo; I updated commit sha1. New commits:

 ​5dc6bd5 `nicer linebreaks`

### comment:77 Changed 5 years ago by moritz

• Status changed from needs_work to needs_review

Thanks for the tip, Travis! I changed it accordingly.

I hope all is well now.

### comment:78 Changed 5 years ago by moritz

• Status changed from needs_review to needs_work

### comment:79 Changed 5 years ago by moritz

• Status changed from needs_work to needs_review

Dear JP, I will set it on positive review on your behalf, as soon as the bot does not complain about the white space changes

### comment:80 Changed 5 years ago by moritz

• Status changed from needs_review to positive_review

### comment:81 Changed 5 years ago by vbraun

• Branch changed from public/13517 to 5dc6bd55273408801d8b79681c985ad2a91f5443
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.