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.




Dim Shared As Integer ancho = 500, alto = 500
Screenres ancho, alto, 8
Cls
Randomize Timer
 
Function hypot(a As Integer, b As Integer) As Double
    Return Sqr(a^2 + b^2)
End Function
 
Sub Generar_Diagrama_Voronoi(ancho As Integer, alto As Integer, num_celdas As Integer)
    Dim As Integer nx(num_celdas), ny(num_celdas), nr(num_celdas), ng(num_celdas), nb(num_celdas)
    Dim As Integer x, i, y, j, dmin, d
 
    For i = 1 To num_celdas
        nx(i) = (Rnd * ancho)
        ny(i) = (Rnd * alto)
        nr(i) = (Rnd * 256)
        ng(i) = (Rnd * 256)
        nb(i) = (Rnd * 256)
    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
            Pset (x, y), Rgb(nr(j), ng(j), ng(j))
        Next x
    Next y
End Sub
 
Generar_Diagrama_Voronoi(ancho, alto, 25)
Bsave "Voronoi_diadram.bmp",0
Sleep