"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.

I got a bunch of points and a scan line, and managed to plot all of the
parabolas and kind of draw some of the Voronoi edges by looping all the way down
the screen and plotting all of the intersection points.
It took a long time to spot a pair of missing parentheses that I should have
had.
Repeat after me: -b +/- sqrt (b*b -4*a*c)    ***ALL*** over 2*a
which makes it (-b +/- sqrt (b*b -4*a*c)) / 2*a

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.

For that, I need to test if a point lay inside of a triangle's circumcircle, and
luckily someone had a nice little simple compact method for doing so.

I always find it fascinating how many geometric questions can be answered just
by simple arithmetic of point coordinates, be it sum, difference,
multiplication, vdot, vcross, or a matrix determinant.

We would be served well by compiling a list of such useful tricks and
maintaining that on a wiki page, or in the documentation, or as a periodically
updated (with version number and date) include file.

I also find these simple inside/outside test renders to be unusually visually
appealing for some reason.  Attached is the testing of 5000 points against a
triangle's circumcircle.

If there was a band named POV-Ray (a college friend had a band named Man Ray)
this would make a good album cover.   :D

- BE

Post a reply to this message

Attachments:
Download 'circumcircle.png' (348 KB)

Preview of image 'circumcircle.png'