undefined | Better HN

0 pointsbovermyer7y ago0 comments

I spent a couple weekends trying to implement Voronoi via Fortune's algorithm in PHP, since there is no existing library for generating them.

I couldn't get past the point of creating a seemingly random mass of intersecting lines. My math knowledge is lacking (I'm not good at groking geometry for some reason), so I wasn't sure what was wrong or how to approach fixing it.

Maybe I should give Quickhull a go. I think I understand what it's doing.

0 comments

OskarS7y ago

To be clear: quickhull is not "easy" compared to other things you might program, it's an involved algorithm. But honestly, all Voronoi/Delaunay algorithms are difficult to implement in performant fashion, there's no free lunch.

The hardest part of quickhull in 3D is the "horizon" calculation: basically, every time you add a point to the hull, you have to find all the faces that the point can "see", and the horizon of all those faces, and replace them with new faces. This page describes the horizon part well: http://algolist.manual.ru/maths/geom/convhull/qhull3d.php

megaman227y ago

When I did it, I basically had to break down to the point of making a WinForms app that I could step through the algorithm iteration by iteration, drawing out the beach-line and and all the circles and edges as it progressed; I had to have that visualization to see that it was correct.

bovermyerOP7y ago

This sounds like a good way for me to understand it. I'll have to try this. Thanks!

j / k navigate · click thread line to collapse