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.




_Title "Voronoi Diagram"
 
Dim As Integer pnt, px, py, i, x, y, adjct, sy, ly
Dim As Double st
 
'=====================================================================
' Changes number of points and screen size here
'=====================================================================
pnt = 100
px = 512
py = 512
'=====================================================================
Screen _NewImage(px, py, 32)
Randomize Timer
 
Dim Shared As Integer pax(pnt), pay(pnt), indx(px, py)
Dim Shared As Long dSqr(px, py)
Dim As Long col(pnt)
 
For i = 1 To pnt
    pax(i) = Int(Rnd * px)
    pay(i) = Int(Rnd * py)
    col(i) = _RGB(Rnd * 256, Rnd * 256, Rnd * 256)
Next
st = Timer
For x = 0 To px - 1
    For y = 0 To py - 1
        dSqr(x, y) = (pax(1) - x) * (pax(1) - x) + (pay(1) - y) * (pay(1) - y)
        indx(x, y) = 1
    Next
Next
 
For i = 2 To pnt
    ly = py - 1
    For x = pax(i) To 0 Step -1
        If (scan(i, x, ly)) = 0 Then Exit For
    Next x
    For x = pax(i) + 1 To px - 1
        If (scan(i, x, ly)) = 0 Then Exit For
    Next
Next
 
For x = 0 To px - 1
    For y = 0 To py - 1
        sy = y
        adjct = indx(x, y)
        For y = y + 1 To py
            If indx(x, y) <> adjct Then y = y - 1: Exit For
        Next
        Line (x, sy)-(x, y + 1), col(adjct)
    Next
Next
 
Sleep
System
 
Function scan (site As Integer, x As Integer, ly As Integer)
    Dim As Integer ty
    Dim As Long delt2, dsq
    delt2 = (pax(site) - x) * (pax(site) - x)
    For ty = 0 To ly
        dsq = (pay(site) - ty) * (pay(site) - ty) + delt2
        If dsq <= dSqr(x, ty) Then
            dSqr(x, ty) = dsq
            indx(x, ty) = site
            scan = 1
        End If
    Next
End Function