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.




graphic #g, 400,400
#g flush()
spots		= 100
leftSide	= 400
rightSide	= 400
 
dim locX(spots)
dim locY(spots)
dim rgb(spots,3)
dim seal(leftSide, rightSide)
dim reach(leftSide, rightSide)
 
for i =1 to spots
    locX(i)	= int(leftSide  * rnd(1))
    locY(i)	= int(rightSide * rnd(1))
    rgb(i,1)	= int(256 * rnd(1))
    rgb(i,2)	= int(256 * rnd(1))
    rgb(i,3)	= int(256 * rnd(1))
    #g color(rgb(i,1),rgb(i,2),rgb(i,3))
    #g set(locX(i),locY(i))
next i
#g size(1)
' find reach to the first site
for x = 0 to leftSide - 1
    for y = 0 to rightSide - 1
        reach(x, y) = (locX(1) - x) ^ 2 + (locY(1) - y) ^ 2
        seal(x, y) = 1
    next y
next x
#g color("darkblue")
 
' spots other than 1st spot
for i = 2 to spots
    for x = locX(i) to 0 step -1		' looking left
        if not(chkPos(i,x,0, rightSide - 1)) then exit for
    next x
    for x = locX(i) + 1 to leftSide - 1		' looking right
        if not(chkPos(i, x, 0, rightSide - 1)) then exit for
    next x
next i
 
for x = 0 to leftSide - 1
    for y = 0 to rightSide - 1
	c1	= rgb(seal(x, y),1)
	c2	= rgb(seal(x, y),2)
	c3	= rgb(seal(x, y),3)
        #g color(c1,c2,c3)
        startY	= y
        nearest	= seal(x, y)
        for y = y + 1 to rightSide
            if seal(x, y) <> nearest then y = y - 1 : exit for
        next y
        #g line(x,startY,x,y + 1)
    next y
next x
 
#g color("black")
#g size(4)
for i =1 to spots
    #g set(locX(i),locY(i))
next i
render #g
end
 
function chkPos(site, x, startY, endY)
	dxSqr = (locX(site) - x) ^ 2
	for y = startY to endY
		dSqr = (locY(site) - y) ^ 2 + dxSqr
		if dSqr <= reach(x, y) then
			reach(x,y)	= dSqr
			seal(x,y)	= site
			chkPos		= 1
		end if
	next y
end function