A Voronoi diagram is a diagram consisting of a number of sites.

Each Voronoi site s also has a Voronoi cell consisting of all points closest to s.



Task

Demonstrate how to generate and display a Voroni diagram.



See algo K-means++ clustering.




 
WindowWidth  =600
WindowHeight =600
 
sites = 100
xEdge = 400
yEdge = 400
graphicbox #w.gb1, 10, 10, xEdge, yEdge
 
open "Voronoi neighbourhoods" for window as #w
 
#w     "trapclose quit"
#w.gb1 "down ; fill black ; size 4"
#w.gb1 "font courier_new 12"
 
dim townX( sites), townY( sites), col$( sites)
 
for i =1 to sites
    townX( i) =int( xEdge *rnd( 1))
    townY( i) =int( yEdge *rnd( 1))
    col$( i) = int( 256 *rnd( 1)); " "; int( 256 *rnd( 1)); " "; int( 256 *rnd( 1))
    #w.gb1 "color "; col$( i)
    #w.gb1 "set "; townX( i); " "; townY( i)
next i
 
#w.gb1 "size 1"
 
dim nearestIndex(xEdge, yEdge)
dim dist(xEdge, yEdge)
 
start = time$("ms")
 
'fill distance table with distances from the first site
for x = 0 to xEdge - 1
    for y = 0 to yEdge - 1
        dist(x, y) = (townX(1) - x) ^ 2 + (townY(1) - y) ^ 2
        nearestIndex(x, y) = 1
    next y
next x
 
#w.gb1 "color darkblue"
'for other towns
for i = 2 to sites
    'display some progress
    #w.gb1 "place 0 20"
    #w.gb1 "\computing: "; using("###.#", i / sites * 100); "%"
    'look left
    for x = townX(i) to 0 step -1
        if not(checkRow(i, x,0, yEdge - 1)) then exit for
    next x
    'look right
    for x = townX(i) + 1 to xEdge - 1
        if not(checkRow(i, x, 0, yEdge - 1)) then exit for
    next x
    scan
next i
 
for x = 0 to xEdge - 1
    for y =0 to yEdge - 1
        #w.gb1 "color "; col$(nearestIndex(x, y))
        startY = y
        nearest = nearestIndex(x, y)
        for y = y + 1 to yEdge
            if nearestIndex(x, y) <> nearest then y = y - 1 : exit for
        next y
        #w.gb1 "line "; x; " "; startY; " "; x; " "; y + 1
    next y
next x
 
#w.gb1 "color black; size 4"
for i =1 to sites
    #w.gb1 "set "; townX( i); " "; townY( i)
next i
print time$("ms") - start
wait
 
sub quit w$
    close #w$
    end
end sub
 
function checkRow(site, x, startY, endY)
    dxSquared = (townX(site) - x) ^ 2
    for y = startY to endY
         dSquared = (townY(site) - y) ^ 2 + dxSquared
         if dSquared <= dist(x, y) then
             dist(x, y) = dSquared
             nearestIndex(x, y) = site
             checkRow = 1
         end if
    next y
end function
 