Opened 9 years ago

Closed 4 years ago

#13517 closed enhancement (fixed)

Voronoi diagrams

Reported by: moritz Owned by: mhampton
Priority: minor Milestone: sage-8.0
Component: geometry Keywords: voronoi, delaunay, days84
Cc: vbraun, jipilab, tmonteil, pelegm Merged in:
Authors: Moritz Firsching Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 5dc6bd5 (Commits, GitHub, GitLab) Commit: 5dc6bd55273408801d8b79681c985ad2a91f5443
Dependencies: Stopgaps:

Status badges

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

Attachments (3)

trac_#13517_voronoi_first_try.patch (3.0 KB) - added by moritz 9 years ago.
a first try
trac_#13517_new_class_initial_version.patch (11.8 KB) - added by moritz 9 years ago.
first working version
trac_#13517_new_class_reviewed.patch (8.1 KB) - added by moritz 9 years ago.
reviewed

Download all attachments as: .zip

Change History (84)

Changed 9 years ago by moritz

a first try

comment:1 Changed 9 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: Changed 9 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 9 years ago by moritz

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

Changed 9 years ago by moritz

first working version

comment:4 Changed 9 years ago by moritz

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

comment:5 Changed 9 years ago by moritz

I added a first version, which provides the basic functionality

comment:6 Changed 9 years ago by mmarco

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.

Changed 9 years ago by moritz

reviewed

comment:7 Changed 9 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: 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

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

See also

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 8 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 :

http://bl.ocks.org/mbostock/4060366

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

Nathann

comment:13 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:14 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:15 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:16 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:17 Changed 6 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 6 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 6 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

  • 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 point-configuration class giving back the voronoi-diagram.


New commits:

44cc3a4starting with the old patch
7dda65cpolished 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:

6422be4starting with the old patch
854c9ecpolished 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:

78b66afpoints 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:

78b66afpoints 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:

ccf7a51more 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:

975e3ccMerge branch 'u/moritz/voronoi' in 7.5.rc1
f77b6catrac 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:

90bfdd1trac 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:

49cd896added '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:

1845492adding a doctest for input an invalid base ring

comment:34 Changed 5 years ago by tmonteil

  • Cc tmonteil added

comment:35 Changed 4 years ago by pelegm

  • Cc pelegm added

comment:36 Changed 4 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 4 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 4 years ago by git

  • Commit changed from 1845492dec4cd22960b0af2573605af1932e8741 to 984f495310ce85dbc4a129587402274a5d9e4513

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

efc25f6starting with the old patch
0def0adpolished the first version a bit
8da57depoints are now resorted if necessary
5b582a0more doctests and correct reordering of the cells
caefa55trac 13517 code and doc cleanup
a2c0f6atrac 13517 some more details
ec2b584added 'AA' in the NotImplementedError in the init
3ddad48adding a doctest for input an invalid base ring
5474325fixed description of points, added option for color
984f495Merge branch 'public/13517' of git://trac.sagemath.org/sage into voronoi

comment:39 Changed 4 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 4 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 4 years ago by jipilab

  • Status changed from needs_review to needs_work

comment:42 Changed 4 years ago by git

  • Commit changed from 984f495310ce85dbc4a129587402274a5d9e4513 to 28b3461cca77dfd386915cfe84422e5507cf3abf

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

d9469fdchanged dodehedron to pentagon to get faster doctest
28b3461added TODOs and removed backslashes

comment:43 Changed 4 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 4 years ago by git

  • Commit changed from 28b3461cca77dfd386915cfe84422e5507cf3abf to 61078e71630a79efe4d56dcf3c2abe97affb9b98

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

61078e7whitespace

comment:45 Changed 4 years ago by jipilab

  • Keywords days84 added

comment:46 Changed 4 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 4 years ago by git

  • Commit changed from 61078e71630a79efe4d56dcf3c2abe97affb9b98 to f980041ed5dcb1634c1127a491dd7e5cb3024917

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

a2c0b08improve docstring
f980041Merge branch 'develop' into voronoi

comment:48 Changed 4 years ago by moritz

TODOs are included and the docstring is improved

comment:49 Changed 4 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 4 years ago by jipilab

  • Reviewers set to Jean-Philippe Labbé

comment:51 Changed 4 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 4 years ago by vdelecroix

Sage classes must be caml case voronoi_diagram -> VoronoiDiagram.

comment:53 Changed 4 years ago by git

  • Commit changed from f980041ed5dcb1634c1127a491dd7e5cb3024917 to 5026d3f483e958a2d0c4024aa607f4b17f1f689b

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

5026d3fchanged class name to CamelCase

comment:54 Changed 4 years ago by git

  • Commit changed from 5026d3f483e958a2d0c4024aa607f4b17f1f689b to 5f6bb85be3d11e135789c02bb980c93eace2f877

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

5f6bb85removed a colon

comment:55 Changed 4 years ago by moritz

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

comment:56 Changed 4 years ago by git

  • Commit changed from 5f6bb85be3d11e135789c02bb980c93eace2f877 to 35dc80b4f778c4ca6be65157d0fbd1d3418a4844

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

35dc80bimproved TODO in docstring

comment:57 Changed 4 years ago by jipilab

  • 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 4 years ago by git

  • Commit changed from 35dc80b4f778c4ca6be65157d0fbd1d3418a4844 to 63507e1a9d16d9dc1b55016ce081a440a9de4eb2

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

63507e1moved reference and other small improvements

comment:59 Changed 4 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 4 years ago by jipilab

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 4 years ago by git

  • Commit changed from 63507e1a9d16d9dc1b55016ce081a440a9de4eb2 to 835929b18456a3672368440a8bae6edeb85b4800

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

835929bspaces and removed 8

comment:62 Changed 4 years ago by git

  • Commit changed from 835929b18456a3672368440a8bae6edeb85b4800 to 90477d40f88b27ae04ca1620af61754496991a2f

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

90477d4changed reference abbreviation

comment:63 Changed 4 years ago by moritz

  • Dependencies #22496 deleted

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

comment:64 Changed 4 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 4 years ago by jipilab

  • Status changed from needs_review to positive_review

There is no doc errors anymore. Looks good!

comment:66 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict, wait for next beta

comment:67 Changed 4 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 4 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 4 years ago by jipilab

  • Milestone changed from sage-7.6 to sage-8.0

comment:70 Changed 4 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:

ef78175Voronoi diagram merge
7a7905dadded to new reference index

comment:71 Changed 4 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 4 years ago by moritz

  • Status changed from needs_work to needs_review

comment:73 Changed 4 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 4 years ago by git

  • Commit changed from 7a7905ddf8535b5a3637272a984add13e2a22fc8 to fc3c49a23b377822ca25f7fd93bfbee31ea2391a

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

fc3c49amake doctest independent of order in dict

comment:75 Changed 4 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 4 years ago by git

  • Commit changed from fc3c49a23b377822ca25f7fd93bfbee31ea2391a to 5dc6bd55273408801d8b79681c985ad2a91f5443

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

5dc6bd5nicer linebreaks

comment:77 Changed 4 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 4 years ago by moritz

  • Status changed from needs_review to needs_work

comment:79 Changed 4 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 4 years ago by moritz

  • Status changed from needs_review to positive_review

comment:81 Changed 4 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.