Re: Voronoi Furtune algorithm

"Bald Eagle" <cre### [at] netscapenet> wrote:
> "Bald Eagle" <cre### [at] netscapenet> wrote:
> So, I played around with starting to implement the Fortune algorithm for the
> Voronoi diagram, but I also need a DCEL and a red-black tree data structure, a
> balanced binary tree, or similar.

Update here - jr has been leading me by the nose-hairs to get the binary tree /
Red-Black tree coded up, and hopefully we (mostly he) will have some code we can
start to play with soon.

> Someone said it was easier to code the Bowyer-Watson algorithm, so I might try
> to code both in parallel and see which one (if any) I get to work first.

Admittedly, I have not started on that one yet.

The RB-tree and the DCEL are used for storing the data for/from the Fortune
algorithm, and that seems to be mostly the results of "site events" and "circle
events".

The site event seems trivial (scanline is the same height as a voronoi seed),
and so I worked out the detection of a circle event (the intersection of 3
parabolas)  to the best of my meager ability.

Shown is the point where the scanline generates a circle event, where the seeds
are all equidistant from each other and the scanline, and so all lie on a
circumcircle, with the Voronoi vertex at the center.

- BW

Post a reply to this message

Attachments:
Download 'circleeventdetection.png' (42 KB)

Preview of image 'circleeventdetection.png'