unit Unit8;
{
This software has been designed and it is
CopyLefted by Han de Bruijn:

                          (===)
                         @-O^O-@
                          #/_\#
                           ###

            VORONOI REGIONS BY CONTOURING
            =============================
}
INTERFACE

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, ExtCtrls, Grafisch, Contours, Generaal, Algemeen, Shamos;

type
  TForm1 = class(TForm)
    Image1: TImage;
    procedure Toetsdruk(Sender: TObject; var Key: Char);
    procedure Scheppen(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

IMPLEMENTATION

{$R *.dfm}

var
  nodes : integer; { # of sites }
  rij : punten; { sites in the plane }

procedure Some_Help;
begin
  Writeln;
  Writeln('Voronoi regions contouring');
  Writeln;
  writeln('Syntax: [program] [nodes]');
  Writeln(' nodes = # random points');
  Halt;
end;

procedure Read_Parameters;
var
  woord : string;
  OK : boolean;
  k : integer;
begin
  nodes := 10;
  if ParamCount > 1 then Some_Help;
  if ParamCount = 0 then
  begin
    Writeln('Default # nodes = 10');
    Exit;
  end;
  woord := ParamStr(1);
  OK := true;
  for k := 1 to Length(woord) do
    if not (woord[k] in ['0'..'9']) then OK := false;
  if not OK then Some_Help;
  nodes := StrToInt(woord);
end;

function Voronoi(site : integer; x,y : double) : boolean;
{
  Voronoi region that
  belongs to a (site)
}
var
  N,k : integer;
  x1,x2,y1,y2,xm,ym,f : double;
  OK : boolean;
begin
  N := Length(rij);
  OK := true;
  x1 := rij[site].x; y1 := rij[site].y;
  for k := 0 to N-1 do
  begin
    if k = site then Continue;
    x2 := rij[k].x; y2 := rij[k].y;
  { For all Perpendicular Bisectors }
    xm := (x1+x2)/2; ym := (y1+y2)/2;
    f := (x-xm)*(x2-x1)+(y-ym)*(y2-y1);
    OK := OK and (f < 0);
  end;
  Voronoi := OK;
end;

procedure tekenen(N : integer);
{
  Make drawing
}
var
  i,j,k,L,m : integer;
  x,y,t,eps,D : double;
  OK : boolean;
  O : Omtrekken; { Contouring object }
  rond : Generaal.punten;
  p,q,r,s : punt;
  rand : drietal;
begin
  eps := 5/Wijd;
{ Create random sites }
  SetLength(rij,N);
  for k := 0 to N-1 do
  begin
    rij[k].x := Random;
    rij[k].y := Random;
  end;
{ Visualize the sites }
  Form1.Image1.Canvas.Pen.Color := clBlack;
  Form1.Image1.Canvas.Pen.Width := 2;
  for k := 0 to N-1 do
  begin
    i := x2i(rij[k].x);
    j := y2j(rij[k].y);
    Form1.Image1.Canvas.Brush.Color := clWhite;
    Form1.Image1.Canvas.Ellipse(i-3,j-3,i+3,j+3);
  end;
{ Contouring / Make Isolines }
  O := Omtrekken.Create;
  O.Afmetingen(Wijd,Hoog);
  O.Scherm := Form1.Image1.Picture.Bitmap;
  SetLength(rond,0);
{ Loop through all sites }
  for k := 0 to N-1 do
  begin
  { Loop through all pixels }
    for j := 0 to Hoog-1 do
    begin
      y := j2y(j);
      for i := 0 to Wijd-1 do
      begin
        O.funktie[i,j] := 0;
        x := i2x(i);
        OK := Voronoi(k,x,y);
        if OK then O.funktie[i,j] := 1;
      end;
    end;
  { Calculate Isolines }
    O.Rondom(false);
    r := rij[k];
    for L := 1 to O.Aantal do
    begin
      O.FanDataCompressie(L,2);
      O.Schetsen(L,clGreen,2);
      rond := O.Kromme(L);
    { Delaunay Triangulation modest attempt }
      Form1.Image1.Canvas.Pen.Color := clRed;
      m := Length(rond)-1;
      p.x := i2x(Round(rond[m].x));
      p.y := j2y(Round(rond[m].y));
      for m := 0 to Length(rond)-1 do
      begin
        q.x := i2x(Trunc(rond[m].x));
        q.y := j2y(Trunc(rond[m].y));
      { Avoiding too small line segments }
        if (abs(p.x-q.x) < eps) and (abs(p.y-q.y) < eps) then Continue; 
        D := sqr(q.x-p.x)+sqr(q.y-p.y);
        t := (r.x-p.x)*(q.x-p.x)+(r.y-p.y)*(q.y-p.y);
        t := t/D;
        s.x := p.x+t*(q.x-p.x);
        s.y := p.y+t*(q.y-p.y);
        p.x := q.x; p.y := q.y;
      { Avoiding perpendiculars to image boundary }
        if abs(s.x-xmin) < eps then Continue;
        if abs(s.y-ymin) < eps then Continue;
        if abs(s.x-xmax) < eps then Continue;
        if abs(s.y-ymax) < eps then Continue;
        Form1.Image1.Canvas.MoveTo(x2i(r.x),y2j(r.y));
        Form1.Image1.Canvas.LineTo(x2i(s.x),y2j(s.y));
      end;
    end;
  end;
  Writeln;
  Convex_hull(rij,rand);
  Form1.Image1.Canvas.Pen.Color := clBlue;
  for k := 0 to Length(rand)-1 do
  begin
    i := x2i(rij[rand[k].A].x);
    j := y2j(rij[rand[k].A].y);
    Form1.Image1.Canvas.MoveTo(i,j);
    i := x2i(rij[rand[k].B].x);
    j := y2j(rij[rand[k].B].y);
    Form1.Image1.Canvas.LineTo(i,j);
  end;
end;

procedure TForm1.Toetsdruk(Sender: TObject; var Key: Char);
{
  On KeyPress
}
begin
  ClearDevice;
  Tekenen(nodes);
  Form1.Image1.Picture.SaveToFile('voronoi.bmp');
end;

procedure TForm1.Scheppen(Sender: TObject);
{
  At moment of creation
}
begin
  Read_Parameters;
  xmin := -0.1; xmax := 1.1;
  ymin := -0.1; ymax := 1.1;
  TV(Form1.Image1);
  ClearDevice;
  Tekenen(nodes);
  Form1.Image1.Picture.SaveToFile('voronoi.bmp');
end;

END.