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.
