Did you see this implementation?
Quasimondo
Alan Shaw
Yes, of course, I see all Voronoi activity on the Web. With my giant VoronEye.
I have a feeling (unproved) that this one does more math than mine,
and I believe that it also simply outputs the line segments of the
diagram and doesn't maintain the data structure. That said, it
demonstrates an understanding of Fortune's algorithm, and I'm sure I
can clarify my own understanding of the algorithm by studying this one
some more.
My goals with the github project are to provide a library that people
will use, and to continue to refactor the code for clarity so as to
make the algorithm as transparent as possible. And of course to
enhance performance. These latter two goals are in conflict, though,
so we'll see where that goes.
I kept the code private for a long time with the idea that I should
get it to a certain clean-code standard first, but releasing it has
actually focused me a bit more on things I can address in the core
Fortune algorithm implementation, so I expect there will be some
revisions to that quickly.
For me it is also interesting to observe how the structure of the code
has changed. It is at heart simply a port of Fortune's original C
code, which I have archived on the mailing list site.
I also want to see if anyone as obsessed with the details as I am will
fork and modify the code.
Finally, this library offers no rendering capabilities whatsoever.
I'd like to see how people may use it, and what they may come up with
in terms of rendering, before I add my take on that.
On Tue, Sep 29, 2009 at 10:34 AM, Quasimondo <quasi...@gmail.com> wrote:
>
> http://blog.controul.com/2009/05/speedy-voronoi-diagrams-in-as3flash/
Quasimondo
somehow I hadn't realized that it was you who sent the invite to this
group. Of course I know that you know this other implementation. So
here's another stupid question: where is the AS3 source code of your
github project? I only see the c sources and a PDF in the "files"
section. Also on your blog I don't find any links.
About that other code: indeed it only returns line segments. I have
written a LinearMesh class which can return the regions that are made
up from these segments, the problem is that my code is not optimized
yet and will become quite slow with more points. Another issue I
encountered with this implementation is that it produces artifacts or
stray lines with certain point constellations (regular grids for
example). It seems like certain numeric conditions are not handled and
it creates division by zero errors.
So I'd really love to check out your code of course.
Mario
Alan Shaw
The AS3 source code of the github project is located on github:
http://github.com/nodename/as3delaunay
Yes, regular grids, yes. I'm just starting to explore those as well.
Those often give rise to the dreaded Degenerate Voronoi Diagram in which
some edges have shrunk to zero length and the (actually double) vertex
winds up equidistant from four sites rather than three.
The Voronoi literature generally just waves a crucifix when these are mentioned.
I think they come out OK in my implementation though; check out this link:
http://nodename.com/wpEmbeds/VoronoiLattice/DelaunayLattice.swf
which is a musical instrument keyboard layout simulation to be blogged
about soon.
-A