[Qgis-developer] Voronoi missing

[Barry Rowlingson]

On Fri, Oct 9, 2009 at 4:52 PM, Carson Farmer <carson.farmer at gmail.com> wrote:
> Barry (et al.),
>
>> > http://www.oxfish.com/python/voronoi.py
>>
>>  Ah, you already are using this! I guess the problem is extracting the
>> polygon topology from the segments, and dealing with the infinities...
>
> Exactly! I've come close (Clipping the polygons to the extent of the largest
> complete polygon (if I recall correctly).
> The hardest part as you say, extracting the polygon topology :-( The
> implementation I've developed so far is also very messy ;-)
>

 I had an idea - if you can get the points of the voronoi polygons in
any order, then (I think) they must lie on a convex hull. So find the
centroid, and then order them in increasing bearing (atan2(y,x) or
something).

 I've just been looking at the source for the deldir package in R that
does voronoi polys. I dont think it gives direct access to the built
polygons (only segments) but it does do clipping. And it's written in
ratfor, which looks rather fine....

 Wish I had more time to code, but weekends are spent decorating....

Barry