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.




Structure VCoo
  x.i:  y.i
  Colour.i: FillColour.i
EndStructure
 
Macro RandInt(MAXLIMIT)
  Int(MAXLIMIT*(Random(#MAXLONG)/#MAXLONG))
EndMacro
 
Macro SQ2(X, Y)
  ((X)*(X) + (Y)*(Y))
EndMacro
 
Procedure GenRandomPoints(Array a.VCoo(1), xMax, yMax, cnt)
  Protected i, j, k, l
  cnt-1
  Dim a(cnt)
  For i=0 To cnt
    a(i)\x = RandInt(xMax): a(i)\y = RandInt(yMax)
    j = RandInt(255): k = RandInt(255): l = RandInt(255)
    a(i)\Colour = RGBA(j, k, l, 255)
    a(i)\FillColour = RGBA(255-j, 255-k, 255-l, 255)
  Next i
  ProcedureReturn #True
EndProcedure
 
Procedure MakeVoronoiDiagram(Array a.VCoo(1),xMax, yMax) ; Euclidean
  Protected i, x, y, img, dist.d, dt.d
  img = CreateImage(#PB_Any, xMax+1, yMax+1)
  If StartDrawing(ImageOutput(img))
    For y=0 To yMax
      For x=0 To xMax
        dist = Infinity()
        For i=0 To ArraySize(a())
          dt = SQ2(x-a(i)\x, y-a(i)\y)
          If dt > dist 
            Continue
          ElseIf dt < dist
            dist = dt
            Plot(x,y,a(i)\FillColour)
          Else ; 'Owner ship' is unclear, set pixel to transparent.
            Plot(x,y,RGBA(0, 0, 0, 0))
          EndIf
        Next
      Next
    Next
    For i=0 To ArraySize(a())
      Circle(a(i)\x, a(i)\y, 1, a(i)\Colour)
    Next
    StopDrawing()
  EndIf
  ProcedureReturn img 
EndProcedure
 
; Main code
Define img, x, y, file$
Dim V.VCoo(0)
x = 640: y = 480
If Not GenRandomPoints(V(), x, y, 150): End: EndIf  
img = MakeVoronoiDiagram(V(), x, y)
If img And OpenWindow(0, 0, 0, x, y, "Voronoi Diagram in PureBasic", #PB_Window_SystemMenu)
  ImageGadget(0, 0, 0, x, y, ImageID(img))
  Repeat: Until WaitWindowEvent() = #PB_Event_CloseWindow
EndIf
 
UsePNGImageEncoder()
file$ = SaveFileRequester("Save Image?", "Voronoi_Diagram_in_PureBasic.png", "PNG|*.png", 0)
If file$ <> ""
  SaveImage(img, file$, #PB_ImagePlugin_PNG)
EndIf