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.

Calling Sequence

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

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.

Example

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

N = 20

X = RANDOMU(seed, N) ; Create a random grid of N points

Y = RANDOMU(seed, N)

TRIANGULATE, X, Y, tr, CONN=C ; Triangulate it

FOR I=0, N-1 DO BEGIN & $

    VORONOI, X, Y, I, C, Xp, Yp & $ ; Get the ith polygon

    POLYFILL, Xp, Yp, COLOR = (I MOD 10) + 2 & $
; Draw it

ENDFOR

See Also

TRIANGULATE