Voronoi

2D Voronoi Maps generator - Version 1.0

SYNOPSIS
        package require Voronoi
        Voronoi _list_of_seeds_ ?-clip _clip_area_?

DESCRIPTION
The Voronoi command takes a _list_of_seeds_ (i.e. a list of 2D points) and an 
optional _clip_area_ and returns a list of cells (or regions) describing the 
geometry of each area growing around each seed.

A _list_of_seeds_ can be expressed
   as a list of coordinate pairs   {x0 y0  x1 y1 ......}
 or 
   as a list of 'points'            {{x0 y0} {x1 y1} ...}

If the _clip_area_ is not specified, an automatic clip-box is calculated, with 
extra padding of 10 units.
In general, a clip-area is a *convex* polygon whose vertices are expressed as 
a list of coordinates or as a list of 'points', using the same notation 
(coords or points) used for the input seeds. As a shorthand, the geometry for 
a rectangular clip-area can be specified with just two vertices as {xmin ymin 
xmax ymax} or as {{xmin ymin} {xmax ymax}}

All input-seeds outside the clip-area will be excluded.


The result is a list of *regions*, one for each input seed (except those seeds 
outside the clip area).
A *region* is a tcl-dictionary with the following entries:
  "vertices" ::  list of the vertices of the region (enumerated in CCW order)
  "seed-idx" ::  integer 0..N - it refers to the i-th input seed
                 (indices are numbered starting from 0)
  "seed-xy"  ::  a list of two numbers - the x,y coords of the i-th input seed
  "centroid" ::  a list of two numbers - the computed centroid of the region
  "area"     ::  the computed area of the region
  "neighbors"::  a list of integers - list of neighbors seed-idx  (see below)
plus some optional entries:
  "fix       ::  "true" if edge-loop has been fixed for this region (see below)
                 (if the fix was not applied, this entry is not added)

*** NOTES:

"vertices" in the "vertices" list will be expressed as pairs of coordinates or 
   as a list of 2 coordinates, according to the notation used for the input 
   seeds. Note that a region is a convex polygon and its vertices are always 
   listed in counter-clockwise (CCW) order.
"neighbors" is a list of 'indices' (integers), one for each edge of the 
   polygon described by the above "vertices" entry. the j-th 'neighbor' is the 
   "seed-idx" of the region beyond the j-th edge (or -1 if there's no region 
   beyond that edge (this also means that the edge is a boundary edge of the 
   whole diagram)).
e.g.
   given 
    "vertices"  {x0 y0  x1 y1  x2 y2 ...  xN yN}   
    "neighbors" { 5      -1          ...    3  } 
   then
    the neighbor beyond the first edge  (x0 y0 x1 y1) is the seed 5
    the neighbor beyond the second edge (x1 y1 x2 y2) is the seed -1 (no neigbor!)
      ...
    the neighbor beyond the last edge   (xN yN x0 y0) is the seed 3


*** THE "fix" ENTRY

Due to some floating-point approximations in the underlying core algorithm, 
sometimes vertices of a region are repeated, producing a double 'edge-loop'
e.g: 
  instead of {P0 P1...} we got {P0 P1 ... P0' P1'...}.
  where P0' is 'quite the same' as P0  (error<1e-6)
  and so P1, P2 , ....

This is a rare occurrence, but sometimes it happens!
As far as I experienced, this happens only when
  the number of computed regions is 2 
  AND
  a clip-polygon is used (instead of a simple clip-box).

The above 2 conditions are not a rule; sometimes a very small variation 
of the input points, may cause this bug, and sometimes another small variation 
may produce correct results.

As a thumb of rule, a simple *check and attempt to fix* is applied only in 
these cases, being expensive to apply when the number of regions is large.
When this check is applied and an edge-loop is detected, the loop is corrected
and, as a remark for debugging, a "fix" entry with value "true" is added to the 
dictionary of the region.


** DRAWING the Voronoi map in a (Tk) canvas:

Here is a simple way to draw and fill the computed geometries.

        Given
         $cvs   a canvas widgets
         $seeds a list of input coord pairs, e.g.  {x0 y0 x1 y1 .... }

        set colors {red blue}
         # -- compute the regions around the seeds -------
        set regions [Voronoi  $seeds]
         # -----------------------------------------------
        foreach region $regions {
                set vertices [dict get $region "vertices"]

                 # a simple rule for colors:
                 # regions whose seed is has an even index are "red", others are "blue"
                set idx [dict get $region "seed-idx"]
                set color [lindex $colors [expr {$idx%2}]]
                
                $cvs create polygon $vertices -fill $color -outline black
        }