2-D Voronoi Diagrams with Byers' Method - Maple Application Center
Application Center Applications 2-D Voronoi Diagrams with Byers' Method

2-D Voronoi Diagrams with Byers' Method

: Bruno Guerrieri
Engineering software solutions from Maplesoft
This Application runs in Maple. Don't have Maple? No problem!
 Try Maple free for 15 days!
Given N points (sites) in the plane (a 1x1 square) we would like to generate a tessellation of that domain by assigning every point in the plane to its nearest site. The process, as presented by Byers [1], is to select a particular site, call it C, and determine its Voronoi polygon. This is achieved by a) generating all segments from C to the remaining sites, b) considering all bisecting lines of each of these segments (in other words, the normal to the segment through the midpoint), c) determining all intersections points of these 'bisectors", d) eliminate those intersection points not in the 1x1 square, and e) determine which ones of the remaining intersection points are "closest" to C. Their convex hull is the Voronoi cell we are looking for. We then repeat the process for each of the remaining sites. We are mainly interested in the discovery process and, therefore, are not always concerned with efficiency or storage minimization.

Application Details

Publish Date: April 26, 2004
Created In: Maple 9
Language: English

More Like This

Comparison of Multivariate Optimization Methods

Parabolic Reflectors and the Ideal Flashlight
Animation of Dudeney's Dissection Transforming an Equilateral Triangle to a Square
Pascal's triangle and its relationship to the Fibonacci sequence
Classroom Tips and Techniques: Sliders for Parameter-Dependent Curves
Rectification of the Circular Arc by Cochleoidal Curve Construction