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

Author
: Bruno Guerrieri
This Application runs in Maple. Don't have Maple? No problem!
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

#### Share

This app is not in any Collections

#### Tags

geometry algorithm linear-algebra