Main Menu

search

You are here

Home

Voronoi

[last updated: 2023-11-14]
...

-----

  • Random/General Info extracted from the web:
    • An easy algorithm to compute the Delaunay triangulation of a point set is flipping edges. Since a Delaunay triangulation is the dual graph of a Voronoi diagram, you can construct the diagram from the triangulation in linear time.
      Unfortunately, the worst case running time of the flipping approach is O(n^2). Better algorithms such as Fortune's line sweep exist, which take O(n log n) time. This is somewhat tricky to implement though. If you're lazy (as I am), I would suggest looking for an existing implementation of a Delaunay triangulation, use it, and then compute the dual graph.
      In general, a good book on the topic is Computational Geometry by de Berg et al.
    • Easiest? That's the brute-force approach: For each pixel in your output, iterate through all points, compute distance, use the closest. Slow as can be, but very simple. If performance isn't important, it does the job. I've been working on an interesting refinement myself, but still searching to see if anyone else has had the same (rather obvious) idea.
    • The Bowyer-Watson algorithm is quite easy to understand. Here is an implementation: (link to:) paulBourke.net. It's a delaunay triangulation for a set of points but you can use it to get the dual of the delaunay, ie. a voronoi-diagram. BTW. the minimum spanning tree is a subset of delaunay triangulation.
    • The most efficient algorithm to construct a voronoi diagram is Fortune's algorithm
      (link to:) wiki - Fortune's algorithm
      It runs in O(n log n).
      Here is a link to his reference implementation in C. (ect.bell-labs.com/who/sjf/voronoi.tar)
      Personally I really like the python implementation (svn.osgeo.org/qgis/trunk/qgis/python/plugins/fTools/tools/voronoi.py) by Bill Simons and Carson Farmer, since I found it easier to extend.

    -------------------------------------------------------------------------

  • Links:

    .

    .

    .

    eof

Powered by Drupal