# Re: Voronoi diagram

148 views

### Volker Braun

Sep 21, 2012, 8:00:02 AM9/21/12
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)
P=[]
e=[([sum(i[k]^2 for k in range(d))]+[(-2)*i[l] for l in range(d)]+) 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

### Jason Grout

Sep 21, 2012, 10:12:10 AM9/21/12
On 9/21/12 7:00 AM, Volker Braun wrote:
> 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.
>
>
>

And here are some more links to things that may be useful.

http://pypi.python.org/pypi/voropy/0.0.1

Thanks,

Jason

### mhampton

Sep 21, 2012, 11:58:28 AM9/21/12

There is support for this in qhull, at least numerically.  This is somewhat wrapped by Scipy:

http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html

It would be great to integrate that and your other suggestions into PointConfigurations as Volker suggests.

-Marshall Hampton