VORONOI

The VORONOI procedure computes the Voronoi polygon of a point within an irregular grid of points, given the Delaunay triangulation. The Voronoi polygon of a point contains the region closer to that point than to any other point.

For interior points, the polygon is constructed by connecting the midpoints of the lines connecting the point with its Delaunay neighbors. Polygons are traversed in a counterclockwise direction.

For exterior points, the set is described by the midpoints of the connecting lines, plus the circumcenters of the two triangles that connect the point to the two adjacent exterior points.

This routine is written in the IDL language. Its source code can be found in the file voronoi.pro in the lib subdirectory of the IDL distribution.

Examples

To draw the Voronoi polygons of each point of an irregular grid:

; Use a color table:
DEVICE, GET_DECOMPOSED=old_decomposed
DEVICE, DECOMPOSED=0
LOADCT, 15
; Create a random grid of N points:
N = 20
X = RANDOMU(seed, N)
Y = RANDOMU(seed, N)
; Triangulate it:
TRIANGULATE, X, Y, tr, CONN=C
FOR I=0, N-1 DO BEGIN & $
   ; Get the ith polygon:
   VORONOI, X, Y, I, C, Xp, Yp & $
      ; Draw it:
      POLYFILL, Xp, Yp, COLOR = I * 10 & $
ENDFOR
; Reset device paramters
DEVICE, DECOMPOSED=old_decomposed
LOADCT, 0

Syntax

VORONOI, X, Y, I0, C, Xp, Yp, Rect

Arguments

X

An array containing the X locations of the points.

Y

An array containing the Y locations of the points.

I0

An array containing the indices of the points.

C

A connectivity list from the Delaunay triangulation. This list is produced with the CONNECTIVITY keyword of the TRIANGULATE procedure.

Xp, Yp

Named variables that will contain the X and Y vertices of Voronoi polygon.

Rect

The bounding rectangle: [Xmin, Ymin, Xmax, Ymax]. Because the Voronoi polygon (VP) for points on the convex hull extends to infinity, a clipping rectangle must be supplied to close the polygon. This rectangle has no effect on the VP of interior points. If this rectangle does not enclose all the Voronoi vertices, the results will be incorrect. If this parameter, which must be a named variable, is undefined or set to a scalar value, it will be calculated.

Version History

Pre-4.0

Introduced