Sounds great. We already have a PointConfiguration class that lets you iterate over the triangulations of the convex hull, your code should fit in there perfectly. Definitely open a trac ticket, and please cc me on it.
On Friday, September 21, 2012 12:33:38 PM UTC+1, moritz wrote: > > I thought it might be a good idea to add a new feature: Voronoi diagrams. > > I am not quite sure what the right class of objects would be but to get an > idea what I mean, I wrote the following function: > > Given a list of k points in \RR^d return a list of voronoi cells, i.e. > polyhedra, in R^d: > > def voronoi(s): > n=len(s) > d=len(s[0]) > P=[] > e=[([sum(i[k]^2 for k in range(d))]+[(-2)*i[l] for l in range(d)]+[1]) > for i in s] #Note: when weights are added, some regions become empty and > this should be checked..) > #Convex hull method. See e.g. Jiří Matoušek, Lectures on discrete > Geometry, p. 118 (Ch. 5.7) > p=Polyhedron(ieqs = e, base_ring=RDF) > for i in range(len(s)): > equ=p.Hrepresentation(i) > pvert=[[u[k] for k in range(d)] for u in equ.incident() if > u.is_vertex()] > prays=[[u[k] for k in range(d)] for u in equ.incident() if > u.is_ray()] > pline=[[u[k] for k in range(d)] for u in equ.incident() if > u.is_line()] > P.append(Polyhedron(vertices=pvert, lines=pline, rays=prays, > base_ring=RDF)) > return P > > To get an idea how this works we can get get the Voronoi diagram for some > points in \RR^2 and plot it: > > d=2; #dimension, plotting works well only in dimension 2 > n=7; #number of points > s=[[random() for k in range(d)] for i in range(n)] > > P=voronoi(s) > > S=line([]) > for i,j in enumerate(s): > S+=(P[i]).render_solid(color=rainbow(n)[i], zorder=1) > S+=point(j, color=rainbow(n)[i], pointsize=10,zorder=3) > S+=point(vector(j), color='black',pointsize=20,zorder=2) > show(S, xmax=1,xmin=0,ymax=1,ymin=0) > > > 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 > > > I am new to sage, but I want to start contributing. > > Whats the best way to proceed? > Is there anyone interested in having such a feature? > Should I open a trac ticket? > > Any suggestions are welcome. > > moritz > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
