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.




 
clear screen
 
sites = 200
xEdge = 600
yEdge = 400
 
open window xEdge, yEdge
 
dim townX(sites), townY(sites), col$(sites)
 
for i =1 to sites
    townX(i) =int(xEdge *ran(1))
    townY(i) =int(yEdge *ran(1))
    col$(i) = str$(int(256 * ran(1))) + ", " + str$(int(256 * ran(1))) + ", " + str$(int(256 * ran(1)))
    color col$(i)
    fill circle townX(i), townY(i), 2
next i
 
dim nearestIndex(xEdge, yEdge)
dim dist(xEdge, yEdge)
 
//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
 
color 0,0,255
//for other towns
for i = 2 to sites
    //display some progress
    //print at(0,20) "computing: ", (i/sites*100) using "###.#", " %"
 
    //look left
    for x = townX(i) to 0 step -1
        if not(checkRow(i, x,0, yEdge - 1)) break
    next x
    //look right
    for x = townX(i) + 1 to xEdge - 1
        if not(checkRow(i, x, 0, yEdge - 1)) break
    next x
next i
 
for x = 0 to xEdge - 1
    for y =0 to yEdge - 1
    	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 : break : end if
        next y
        line x, startY, x, y + 1
    next y
next x
 
color 0,0,0
for i =1 to sites
    fill circle townX( i), townY( i), 2
next i
print peek("millisrunning"), " ms"
 
sub checkRow(site, x, startY, endY)
    local dxSquared, y, check
 
    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
             check = 1
         end if
    next y
    return check
end sub