Re: Voronoi diagram

148 views
Skip to first unread message

Volker Braun

unread,
Sep 21, 2012, 8:00:02 AM9/21/12
to sage-...@googlegroups.com
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

unread,
Sep 21, 2012, 10:12:10 AM9/21/12
to sage-...@googlegroups.com
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

unread,
Sep 21, 2012, 11:58:28 AM9/21/12
to sage-...@googlegroups.com

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

unread,
Sep 24, 2012, 6:52:35 AM9/24/12
to sage-...@googlegroups.com
Thanks for the encouraging replies! 
I opened a ticket:
Reply all
Reply to author
Forward
0 new messages