Voronoi diagram: Difference between revisions

=={{header|Yabasic}}==

<lang Yabasic>

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</lang>