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.




$ include "seed7_05.s7i";
  include "draw.s7i";
  include "keybd.s7i";
 
const type: point is new struct
    var integer: xPos is 0;
    var integer: yPos is 0;
    var color: col is black;
  end struct;
 
const proc: generateVoronoiDiagram (in integer: width, in integer: height, in integer: numCells) is func
  local
    var array point: points is 0 times point.value;
    var integer: index is 0;
    var integer: x is 0;
    var integer: y is 0;
    var integer: distSquare is 0;
    var integer: minDistSquare is 0;
    var integer: indexOfNearest is 0;
  begin
    screen(width, height);
    points := numCells times point.value;
    for index range 1 to numCells do
      points[index].xPos := rand(0, width);
      points[index].yPos := rand(0, height);
      points[index].col := color(rand(0, 65535), rand(0, 65535), rand(0, 65535));
    end for;
    for y range 0 to height do
      for x range 0 to width do
        minDistSquare := width ** 2 + height ** 2;
        for index range 1 to numCells do
          distSquare := (points[index].xPos - x) ** 2 + (points[index].yPos - y) ** 2;
          if distSquare < minDistSquare then
            minDistSquare := distSquare;
            indexOfNearest := index;
          end if;
        end for;
        point(x, y, points[indexOfNearest].col);
      end for;
    end for;
    for index range 1 to numCells do
      line(points[index].xPos - 2, points[index].yPos, 4, 0, black);
      line(points[index].xPos, points[index].yPos - 2, 0, 4, black);
    end for;
  end func;
 
const proc: main is func
  begin
    generateVoronoiDiagram(500, 500, 25);
    KEYBOARD := GRAPH_KEYBOARD;
    readln(KEYBOARD);
  end func;