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.




global ancho, alto
ancho = 500 : alto = 500
 
clg
graphsize ancho, alto
 
function hypot(a, b)
	return sqr(a^2+b^2)
end function
 
subroutine Generar_diagrama_Voronoi(ancho, alto, num_celdas)
	dim nx(num_celdas+1)
	dim ny(num_celdas+1)
	dim nr(num_celdas+1)
	dim ng(num_celdas+1)
	dim nb(num_celdas+1)
 
	for i = 0 to num_celdas
		nx[i] = int(rand * ancho)
		ny[i] = int(rand * alto)
		nr[i] = int(rand * 256) + 1
		ng[i] = int(rand * 256) + 1
		nb[i] = int(rand * 256) + 1
	next i
	for y = 1 to alto
		for x = 1 to ancho
			dmin = hypot(ancho-1, alto-1)
			j = -1
			for i = 1 to num_celdas
				d = hypot(nx[i]-x, ny[i]-y)
				if d < dmin then dmin = d : j = i
			next i
			color rgb(nr[j], ng[j], nb[j])
			plot (x, y)
		next x
	next y
end subroutine
 
call Generar_diagrama_Voronoi(ancho, alto, 25)
refresh
imgsave "Voronoi_diagram.jpg", "jpg"
end