Prof. Dr. Jay Martin Anderson
Professor Emeritus of Computer Science, Franklin & Marshall College
  • home
  • Development
    • Gallery
    • Stop and Pray
    • Stations at St. Thomas
    • PricePer
    • What's It Cost?
    • my own
    • at F&M
    • for clients
  • Small Gallery
  • LVC
  • Visualization
    • Algorithm Visualization >
      • Binary Space Partition
      • Convex Hull >
        • Extreme Point algorithm
        • Extreme Edge algorithm
        • "Gift Wrap" algorithm
        • Incremental algorithm
        • Incremental algorithm in three dimensions
        • "QuickHull" algorithm
      • Delaunay triangulation >
        • Incremental algorithm
        • from the Voronoi diagram
      • Line intersection >
        • a "brute force" algorithm
        • Sweepline algorithm
      • Motion planning
      • Point-in-Polygon >
        • Plumbline algorithm
        • Trapezoidal Map
        • Winding Number
      • Polygon triangulation >
        • "Art Gallery" Problem
        • Recursive algorithm
        • Make Monotone Polygons
        • Triangulate a Monotone Polygon
      • Voronoi diagram >
        • Fortune's algorithm
        • Intersection of Half-Planes
        • Quadtree algorithm
    • Data Visualization
  • OpenGL
    • OpenGL for Apple Software Developers
  • iBooks
  • about me
    • contact
Voronoi diagram by Intersection of Half-Planes
The definition of a Voronoi diagram is the partitioning of the plane into regions, directed by a set of points, such that all the points in one region are closer to that region's defining point than to any other defining point.

This means that the edges of the Voronoi diagram are segments taken from the perpendicular bisectors of the lines between the points.  The segments can be seen as intersections of lines which divide the plane in half, hence the name of this algorithm.

Download the zipped file for all movies described on this page by clicking the Download button at the right.  Most movies can be viewed by clicking the thumbnail next to each description.



Download
Picture
At the left, one frame in the visualization of constructing the Voronoi diagram by the intersection of half-planes, given six control points.  Click on the thumbnail to download and show the movie.  Click on the Download button above to download a zipped file of all movies.  

There is also a movie which shows the Voronoi diagram of six control points, interrupted through the algorithm by questions posed to the student. 

In addition, there are movies showing the half-plane intersection algorithm for ten and sixteen control points.

Proudly powered by Weebly