Opened 10 years ago
Closed 5 years ago
#13517 closed enhancement (fixed)
Voronoi diagrams
Reported by:  moritz  Owned by:  mhampton 

Priority:  minor  Milestone:  sage8.0 
Component:  geometry  Keywords:  voronoi, delaunay, days84 
Cc:  vbraun, jipilab, tmonteil, pelegm  Merged in:  
Authors:  Moritz Firsching  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  5dc6bd5 (Commits, GitHub, GitLab)  Commit:  5dc6bd55273408801d8b79681c985ad2a91f5443 
Dependencies:  Stopgaps: 
Description
a feature request: Voronoi diagrams, see https://groups.google.com/d/topic/sagedevel/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
Attachments (3)
Change History (84)
Changed 10 years ago by
comment:1 Changed 10 years ago by
I added a patch just to see if I understood correctly how patching and the mercurial export etc works..
comment:2 followup: ↓ 3 Changed 10 years ago by
The patch is correct ;)
You should format the examples in the docstring as in http://www.sagemath.org/doc/developer/conventions.html#docstringmarkupwithrestandsphinx, 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 hardcode floatingpoint 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
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#docstringmarkupwithrestandsphinx, 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 hardcode floatingpoint 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 usesage: 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:4 Changed 10 years ago by
 Milestone changed from sagefeature to sage5.4
 Status changed from new to needs_review
comment:5 Changed 10 years ago by
I added a first version, which provides the basic functionality
comment:6 Changed 10 years ago by
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.
comment:7 Changed 10 years ago by
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
 Milestone changed from sage5.6 to sage5.5
comment:9 followup: ↓ 10 Changed 9 years ago by
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
Replying to mmarco:
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 Polyhedronmethod only works with QQ and RDF.
If you really want support for extensions of QQ, either the algorithm of finding the Voronoidiagram 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
See also
 https://sage.math.clemson.edu:34567/home/pub/388/ which seems to have an implementation of Voronoi diagrams
 http://pypi.python.org/pypi/voropy/0.0.1
 http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html
 We include qhull somewhere, which is also part of an optional package in R
 Some information at various posts at this blog, though I don't know how detailed they are
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
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 :
http://bl.ocks.org/mbostock/4060366
I wrote a patch (#14953) that uses this library to draw graphs :)
Nathann
comment:13 Changed 9 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:14 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:15 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:16 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:17 Changed 7 years ago by
 Milestone changed from sage6.4 to sage6.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
Dear JP,
I haven't touched the file for a long time, I don't think it ever has been migrated.
comment:20 Changed 5 years ago by
 Branch set to u/moritz/voronoi
comment:21 Changed 5 years ago by
 Cc jipilab added
 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 pointconfiguration class giving back the voronoidiagram.
New commits:
44cc3a4  starting with the old patch

7dda65c  polished the first version a bit

comment:22 Changed 5 years ago by
 Commit changed from 7dda65c8901ba952a1df98123c4694f7cd59220c to 854c9eccdbf253d012d5daf6f0a96e20ecedeed3
comment:23 Changed 5 years ago by
rebased in order to merge cleanly with develop
comment:24 Changed 5 years ago by
one failing doctest, probably you should sort the result
comment:25 Changed 5 years ago by
 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
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
 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
I would really be happy if someone could review this basic version of implementing Voronoidiagrams. Once this is done I would like to
 make the calculation of the voronoi diagram faster
 implement 3dplotting (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
 Branch changed from u/moritz/voronoi to public/13517
 Commit changed from ccf7a5189acd408783604ea36b643c68f1ed0a33 to f77b6ca948bd5b41a4385e4a35b1730c876541dc
comment:30 Changed 5 years ago by
 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
 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
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
 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:34 Changed 5 years ago by
 Cc tmonteil added
comment:35 Changed 5 years ago by
 Cc pelegm added
comment:36 Changed 5 years ago by
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
 Milestone changed from sage6.8 to sage7.6
 Status changed from needs_review to needs_work
one failing doctest, see patchbot report
comment:38 Changed 5 years ago by
 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
 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
All tests pass on 7.6.b4.
Running:
sage t warnlong 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 45 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
 Status changed from needs_review to needs_work
comment:42 Changed 5 years ago by
 Commit changed from 984f495310ce85dbc4a129587402274a5d9e4513 to 28b3461cca77dfd386915cfe84422e5507cf3abf
comment:43 Changed 5 years ago by
 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
 Commit changed from 28b3461cca77dfd386915cfe84422e5507cf3abf to 61078e71630a79efe4d56dcf3c2abe97affb9b98
Branch pushed to git repo; I updated commit sha1. New commits:
61078e7  whitespace

comment:45 Changed 5 years ago by
 Keywords days84 added
comment:46 Changed 5 years ago by
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
 Commit changed from 61078e71630a79efe4d56dcf3c2abe97affb9b98 to f980041ed5dcb1634c1127a491dd7e5cb3024917
comment:48 Changed 5 years ago by
TODOs are included and the docstring is improved
comment:49 Changed 5 years ago by
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
 Reviewers set to JeanPhilippe Labbé
comment:51 Changed 5 years ago by
 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
Sage classes must be caml case voronoi_diagram > VoronoiDiagram
.
comment:53 Changed 5 years ago by
 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
 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
Thanks for the comments, JP and Vincent! I adressed them; should be better now.
comment:56 Changed 5 years ago by
 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
 Status changed from needs_review to needs_work
So more comments:
 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
 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
 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
Salut Moritz,
Some last comments (hopefully):
 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
 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
 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
 Dependencies #22496 deleted
I remove the dependency, because it doesn't build without errors.
comment:64 Changed 5 years ago by
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
 Status changed from needs_review to positive_review
There is no doc errors anymore. Looks good!
comment:66 Changed 5 years ago by
 Status changed from positive_review to needs_work
Merge conflict, wait for next beta
comment:67 Changed 5 years ago by
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
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
 Milestone changed from sage7.6 to sage8.0
comment:70 Changed 5 years ago by
 Commit changed from 90477d40f88b27ae04ca1620af61754496991a2f to 7a7905ddf8535b5a3637272a984add13e2a22fc8
comment:71 Changed 5 years ago by
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
 Status changed from needs_work to needs_review
comment:73 Changed 5 years ago by
 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 3dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line, P(2.00000000000000, 2.00000000000000, 1.00000000000000): A 3dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line, P(1.00000000000000, 2.00000000000000, 0.100000000000000): A 3dimensional 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 3dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line, P(1.00000000000000, 2.00000000000000, 0.100000000000000): A 3dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line, P(2.00000000000000, 2.00000000000000, 1.00000000000000): A 3dimensional 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
 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
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
 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
 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
 Status changed from needs_review to needs_work
comment:79 Changed 5 years ago by
 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
 Status changed from needs_review to positive_review
comment:81 Changed 5 years ago by
 Branch changed from public/13517 to 5dc6bd55273408801d8b79681c985ad2a91f5443
 Resolution set to fixed
 Status changed from positive_review to closed
a first try