Re: Voronoi diagram

[Volker Braun]

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

[Jason Grout]

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

http://permalink.gmane.org/gmane.comp.python.matplotlib.devel/9827

Thanks,

Jason

[mhampton]

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

[moritz]

Thanks for the encouraging replies! 

I opened a ticket:

 http://trac.sagemath.org/sage_trac/ticket/13517 

moritz