Voronoi diagram: Difference between revisions
Added Easylang
No edit summary |
(Added Easylang) |
||
| (48 intermediate revisions by 21 users not shown) | |||
Line 1:
{{task}}
A [[wp:Voronoi diagram|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]].
<br><br>
=={{header|AutoHotkey}}==
Requires [https://www.autohotkey.com/boards/viewtopic.php?f=6&t=6517 GDIP Library]
<syntaxhighlight lang="autohotkey">;------------------------------------------------------------------------
Gui, 1: +E0x20 +Caption +E0x80000 +LastFound +AlwaysOnTop +ToolWindow +OwnDialogs
Gui, 1: Show, NA
hwnd1 := WinExist()
OnExit, Exit
If !pToken := Gdip_Startup()
{
MsgBox, 48, gdiplus error!, Gdiplus failed to start. Please ensure you have gdiplus on your system
ExitApp
}
Width :=1400, Height := 1050
hbm := CreateDIBSection(Width, Height)
hdc := CreateCompatibleDC()
obm := SelectObject(hdc, hbm)
G := Gdip_GraphicsFromHDC(hdc)
Gdip_SetSmoothingMode(G, 4)
;------------------------------------------------------------------------
w := 300, h := 200
xmin := A_ScreenWidth/2-w/2 , xmax := A_ScreenWidth/2+w/2
ymin := A_ScreenHeight/2-h/2 , ymax := A_ScreenHeight/2+h/2
colors := ["C0C0C0","808080","FFFFFF","800000","FF0000","800080","FF00FF","008000"
,"00FF00","808000","FFFF00","000080","0000FF","008080","00FFFF"]
site := []
loop, 15
{
Random, x, % xmin, % xmax
Random, y, % ymin, % ymax
site[A_Index, "x"] := x
site[A_Index, "y"] := y
}
y:= ymin
while (y<=ymax)
{
x:=xmin
while (x<=xmax)
{
distance := []
for S, coord in site
distance[dist(x, y, coord.x, coord.y)] := S
CS := Closest_Site(distance)
pBrush := Gdip_BrushCreateSolid("0xFF" . colors[CS])
Gdip_FillEllipse(G, pBrush, x, y, 2, 2)
x++
}
UpdateLayeredWindow(hwnd1, hdc, 0, 0, Width, Height)
y++
}
pBrush := Gdip_BrushCreateSolid(0xFF000000)
for S, coord in site
Gdip_FillEllipse(G, pBrush, coord.x, coord.y, 4, 4)
UpdateLayeredWindow(hwnd1, hdc, 0, 0, Width, Height)
;------------------------------------------------------------------------
Gdip_DeleteBrush(pBrush)
SelectObject(hdc, obm)
DeleteObject(hbm)
DeleteDC(hdc)
Gdip_DeleteGraphics(G)
return
;------------------------------------------------------------------------
Dist(x1,y1,x2,y2){
return Sqrt((x2-x1)**2 + (y2-y1)**2)
}
;------------------------------------------------------------------------
Closest_Site(distance){
for d, i in distance
if A_Index = 1
min := d, site := i
else
min := min < d ? min : d
, site := min < d ? site : i
return site
}
;------------------------------------------------------------------------
Exit:
Gdip_Shutdown(pToken)
ExitApp
Return
;------------------------------------------------------------------------</syntaxhighlight>
=={{header|BASIC256}}==
{{trans|Python}}
<syntaxhighlight lang="basic256">global ancho, alto
ancho = 500 : alto = 500
clg
graphsize ancho, alto
function hypot(a, b)
return sqr(a^2+b^2)
end function
subroutine Generar_diagrama_Voronoi(ancho, alto, num_celdas)
dim nx(num_celdas+1)
dim ny(num_celdas+1)
dim nr(num_celdas+1)
dim ng(num_celdas+1)
dim nb(num_celdas+1)
for i = 0 to num_celdas
nx[i] = int(rand * ancho)
ny[i] = int(rand * alto)
nr[i] = int(rand * 256) + 1
ng[i] = int(rand * 256) + 1
nb[i] = int(rand * 256) + 1
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
color rgb(nr[j], ng[j], nb[j])
plot (x, y)
next x
next y
end subroutine
call Generar_diagrama_Voronoi(ancho, alto, 25)
refresh
imgsave "Voronoi_diagram.jpg", "jpg"
end</syntaxhighlight>
=={{header|C}}==
Line 10 ⟶ 145:
Image is in PNM P6, written to stdout.
Run as <code>a.out > stuff.pnm</code>.
<
#include <stdlib.h>
#include <string.h>
Line 128 ⟶ 263:
gen_map();
return 0;
}</
=={{header|C++}}==
[[File:voronoi_cpp.png|256px]]
<
#include <windows.h>
#include <vector>
Line 324 ⟶ 459:
return 0;
}
</syntaxhighlight>
=={{header|D}}==
{{trans|Go}}
<
struct Point { uint x, y; }
Line 368 ⟶ 503:
.generateVoronoi(imageWidth, imageHeight)
.savePPM6("voronoi.ppm");
}</
=={{header|Delphi}}==
<syntaxhighlight lang="delphi">
uses System.Generics.Collections;
procedure TForm1.Voronoi;
const
p = 3;
cells = 100;
size = 1000;
var
aCanvas : TCanvas;
px, py: array of integer;
color: array of Tcolor;
Img: TBitmap;
lastColor:Integer;
auxList: TList<TPoint>;
poligonlist : TDictionary<integer,TList<TPoint>>;
pointarray : array of TPoint;
n,i,x,y,k,j: Integer;
d1,d2: double;
function distance(x1,x2,y1,y2 :Integer) : Double;
begin
result := sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); ///Euclidian
// result := abs(x1 - x2) + abs(y1 - y2); // Manhattan
// result := power(power(abs(x1 - x2), p) + power(abs(y1 - y2), p), (1 / p)); // Minkovski
end;
begin
poligonlist := TDictionary<integer,TList<Tpoint>>.create;
n := 0;
Randomize;
img := TBitmap.Create;
img.Width :=1000;
img.Height :=1000;
setlength(px,cells);
setlength(py,cells);
setlength(color,cells);
for i:= 0 to cells-1 do
begin
px[i] := Random(size);
py[i] := Random(size);
color[i] := Random(16777215);
auxList := TList<Tpoint>.Create;
poligonlist.Add(i,auxList);
end;
for x := 0 to size - 1 do
begin
lastColor:= 0;
for y := 0 to size - 1 do
begin
n:= 0;
for i := 0 to cells - 1 do
begin
d1:= distance(px[i], x, py[i], y);
d2:= distance(px[n], x, py[n], y);
if d1 < d2 then
begin
n := i;
end;
end;
if n <> lastColor then
begin
poligonlist[n].Add(Point(x,y));
poligonlist[lastColor].Add(Point(x,y));
lastColor := n;
end;
end;
poligonlist[n].Add(Point(x,y));
poligonlist[lastColor].Add(Point(x,y));
lastColor := n;
end;
for j := 0 to cells -1 do
begin
SetLength(pointarray, poligonlist[j].Count);
for I := 0 to poligonlist[j].Count - 1 do
begin
if Odd(i) then
pointarray[i] := poligonlist[j].Items[i];
end;
for I := 0 to poligonlist[j].Count - 1 do
begin
if not Odd(i) then
pointarray[i] := poligonlist[j].Items[i];
end;
Img.Canvas.Pen.Color := color[j];
Img.Canvas.Brush.Color := color[j];
Img.Canvas.Polygon(pointarray);
Img.Canvas.Pen.Color := clBlack;
Img.Canvas.Brush.Color := clBlack;
Img.Canvas.Rectangle(px[j] -2, py[j] -2, px[j] +2, py[j] +2);
end;
Canvas.Draw(0,0, img);
end;
</syntaxhighlight>
=={{header|EasyLang}}==
[https://easylang.dev/show/#cod=fZBBboMwFET3PsVbVZAqjl2JXTlJxAIMqJYS0xqngttXtqlo2qgb+H4zns8w3pzhbX2faOmQAvBDuHnH/OEDRcuBlmc6DnSlkMLNNgwzNS+VGCePJUxkGC+75dzwVONb11sX0Eppjuikrf9o5o+mkibTlpUaFTdFHv0RLr8h0F+to0Zz4hs9+MrNS52rF24524YjS0nh1jyv5e60Iz2vKXyH+7b+DtoM7Q6luH+b6TL5WDlamw1ep8+BhRM6FldSVaw/T5vNDyagpNbpIVKqFDkx/oYHbVNyrpjycsM4RtVYby4DSlZCii8= Run it]
{{trans|BASIC256}}
<syntaxhighlight>
func hypo a b .
return sqrt (a * a + b * b)
.
nsites = 25
for i to nsites
nx[] &= randint 1001 - 1
ny[] &= randint 1001 - 1
nc[] &= randint 1000 - 1
.
for y = 0 to 1000
for x = 0 to 1000
dmin = 1 / 0
for i to nsites
d = hypo (nx[i] - x) (ny[i] - y)
if d < dmin
dmin = d
imin = i
.
.
color nc[imin]
move x / 10 - 0.05 y / 10 - 0.05
rect 0.11 0.11
.
.
color 000
for i to nsites
move nx[i] / 10 ny[i] / 10
circle 0.5
.
</syntaxhighlight>
=={{header|FreeBASIC}}==
{{trans|Python}}
<syntaxhighlight lang="freebasic">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</syntaxhighlight>
=={{header|Go}}==
[[file:GoVoronoi.png|thumb|right|Output png]]
<
import (
Line 454 ⟶ 776:
fmt.Println(err)
}
}</
=={{header|Haskell}}==
Uses the repa and repa-io libraries.
<
-- Compile with: ghc -O2 -fllvm -fforce-recomp -threaded --make
{-# LANGUAGE BangPatterns #-}
Line 520 ⟶ 842:
writeImageToBMP "out.bmp" voro
</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
Line 526 ⟶ 848:
[[File:Voronoi-normal_unicon.PNG|right]]
[[File:Voronoi-taxi_unicon.PNG|right]]
<
record site(x,y,colour) # site data position and colour
Line 596 ⟶ 918:
every site := !siteL do # mark sites
DrawCircle(site.x,site.y,1)
end</
{{libheader|Icon Programming Library}}
Line 602 ⟶ 924:
[http://www.cs.arizona.edu/icon/library/src/procs/graphics.icn graphics.icn provides graphics support]
[http://www.cs.arizona.edu/icon/library/src/procs/strings.icn strings.icn provides cat ]
=={{header|J}}==
Line 609 ⟶ 930:
A straightforward solution: generate random points and for each pixel find the index of the least distance. Note that the square root is avoided to improve performance.
<
NB. Generates an array of indices of the nearest point
voronoi =: 4 :0
Line 617 ⟶ 938:
load'viewmat'
viewmat 25 voronoi 500 500</
Another solution generates Voronoi cells from Delaunay triangulation. The page [[Voronoi diagram/J/Delaunay triangulation]] also contains a convex hull algorithm. This is a vector based approach instead of a pixel based approach and is about twice as fast for this task's example.
Line 625 ⟶ 946:
This a direct reformulation of the explicit version.
<
viewmat 25 Voronoi 500 500 [ load'viewmat'</
=={{header|Java}}==
{{libheader|Swing}} {{libheader|AWT}}
<
import java.awt.Graphics;
import java.awt.Graphics2D;
Line 817 ⟶ 1,028:
}
}
</syntaxhighlight>
=={{header|JavaScript}}==
Line 843 ⟶ 1,054:
[[File:VDjs310.png|200px|right|thumb|Output VDjs310.png]]
<syntaxhighlight lang="javascript"><!-- VoronoiD.html -->
<html>
<head><title>Voronoi diagram</title>
Line 906 ⟶ 1,116:
</body>
</html>
</syntaxhighlight>
{{Output}}
<pre>
Line 915 ⟶ 1,125:
=={{header|Julia}}==
First version generates an image with random colors as centroids for the voronoi tesselation:
<
using Images
function voronoi(w, h, n_centroids)
Line 929 ⟶ 1,139:
end
img = voronoi(800, 600, 200)
</syntaxhighlight>
Second version takes an image as an input, samples random centroids for the voronoi cells, and asignes every pixel within that cell the color of the centroid:
<
using TestImages, Images
function voronoi_img!(img, n_centroids)
Line 955 ⟶ 1,165:
img = testimage("mandrill")
voronoi_img!(img, 300)
</syntaxhighlight>
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.awt.Color
Line 1,009 ⟶ 1,219:
fun main(args: Array<String>) {
Voronoi(70, 700).isVisible = true
}</
=={{header|Liberty BASIC}}==
Line 1,016 ⟶ 1,226:
If no place on a vertical line is closer to the current site, then there's no point looking further left or right.
Don't bother square-rooting to get distances..
<syntaxhighlight lang="lb">
WindowWidth =600
WindowHeight =600
Line 1,108 ⟶ 1,318:
next y
end function
</syntaxhighlight>
=={{header|Lua}}==
{{libheader|LÖVE}}
{{works with|LÖVE|
{{trans|Python}}
<
function love.load( )
love.math.setRandomSeed( os.time( ) ) --set the random seed
Line 1,139 ⟶ 1,349:
table.insert( nx, love.math.random( 0, imgx ) )
table.insert( ny, love.math.random( 0, imgy ) )
table.insert( nr, love.math.random( 0,
table.insert( ng, love.math.random( 0,
table.insert( nb, love.math.random( 0,
end
love.graphics.setColor( {
love.graphics.setCanvas( canvas )
for y = 1, imgy do
Line 1,161 ⟶ 1,371:
end
--reset color
love.graphics.setColor( {
--draw points
for b = 1, num_cells do
Line 1,173 ⟶ 1,383:
function love.draw( )
--reset color
love.graphics.setColor( {
--draw diagram
love.graphics.draw( voronoiDiagram )
Line 1,180 ⟶ 1,390:
love.graphics.print( "space: regenerate\nesc: quit", 1, 1 )
--draw text
love.graphics.setColor( {
love.graphics.print( "space: regenerate\nesc: quit" )
end
Line 1,192 ⟶ 1,402:
end
end
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
DiagramPlot[{{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {2.1, 11.1}, {9.5, 14.9}, {13.2, 11.9}, {10.3, 12.3},
{6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, {5.3, 2.4}, {8.45, 4.7}, {11.5, 9.6}, {13.8, 7.3}, {12.9, 3.1}, {11, 1.1}}]</
[[File:mma_voronoi.png|Right]]
=={{header|МК-61/52}}==
<syntaxhighlight lang="text">0 П4
0 П5
ИП0 1 - x^2 ИП1 1 - x^2 + КвКор П3
Line 1,211 ⟶ 1,421:
КИП7 [x] С/П
КИП5 ИП5 ИП1 - x>=0 04
КИП4 ИП4 ИП0 - x>=0 02</
''Input'': Р0 - diagram width; Р1 - diagram height; Р0 - number of the points; РA - РE - coordinates and colors of the points in format ''C,XXYY'' (example: 3,0102).
Line 1,240 ⟶ 1,450:
|}
=={{header|
{{works with|
{{
<syntaxhighlight lang="nim">
from sequtils import newSeqWith
from random import rand, randomize
from times import now
import libgd
const
img_width = 400
img_height = 300
nSites = 20
proc dot(x, y: int): int = x * x + y * y
proc generateVoronoi(img: gdImagePtr) =
randomize(cast[int64](now()))
# random sites
let sx = newSeqWith(nSites, rand(img_width))
let sy = newSeqWith(nSites, rand(img_height))
# generate a random color for each site
let sc = newSeqWith(nSites, img.setColor(rand(255), rand(255), rand(255)))
# generate diagram by coloring each pixel with color of nearest site
for x in 0 ..< img_width:
for y in 0 ..< img_height:
var dMin = dot(img_width, img_height)
var sMin: int
for s in 0 ..< nSites:
if (let d = dot(sx[s] - x, sy[s] - y); d) < dMin:
(sMin, dMin) = (s, d)
img.setPixel(point=[x, y], color=sc[sMin])
# mark each site with a black box
let black = img.setColor(0x000000)
img.drawRectangle(
startCorner=[sx[s] - 2, sy[s] - 2],
endCorner=[sx[s] + 2, sy[s] + 2],
color=black,
fill=true)
proc main() =
withGd imageCreate(img_width, img_height, trueColor=true) as img:
img.generateVoronoi()
let png_out = open("outputs/voronoi_diagram.png", fmWrite)
img.writePng(png_out)
png_out.close()
main()
</syntaxhighlight>
=={{header|OCaml}}==
{{works with|ocaml|4.07.1}}
<syntaxhighlight lang="ocaml">let n_sites = 220
let size_x = 640
let size_y = 480
let sq2 ~x ~y =
(x * x + y * y)
let rand_int_range a b =
a + Random.int (b - a + 1)
let nearest_site ~site ~x ~y =
let ret = ref 0 in
let dist = ref 0 in
Array.iteri (fun k (sx, sy) ->
let d = sq2 (x - sx) (y - sy) in
if k = 0 || d < !dist then begin
dist := d;
ret := k;
end
) site;
!ret
let gen_map ~site ~rgb =
let nearest = Array.make (size_x * size_y) 0 in
let buf = Bytes.create (3 * size_x * size_y) in
for y = 0 to pred size_y do
for x = 0 to pred size_x do
nearest.(y * size_x + x) <-
nearest_site ~site ~x ~y;
done;
for i = 0 to pred (size_y * size_x) do
let j = i * 3 in
let r, g, b = rgb.(nearest.(i)) in
Bytes.set buf (j+0) (char_of_int r);
Bytes.set buf (j+1) (char_of_int g);
Bytes.set buf (j+2) (char_of_int b);
done;
Printf.printf "P6\n%d %d\n255\n" size_x size_y;
print_bytes buf;
;;
let () =
Random.self_init ();
let site =
Array.init n_sites (fun i ->
(Random.int size_x,
Random.int size_y))
in
let rgb =
Array.init n_sites (fun i ->
rand_int_range 40 160,
rand_int_range
in
gen_map ~site ~rgb</syntaxhighlight>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use Imager;
my %type = (
Taxicab => sub { my($px, $py, $x, $y) = @_; abs($px - $x) + abs($py - $y) },
Euclidean => sub { my($px, $py, $x, $y) = @_; ($px - $x)**2 + ($py - $y)**2 },
Minkowski => sub { my($px, $py, $x, $y) = @_; abs($px - $x)**3 + abs($py - $y)**3 },
);
my($xmax, $ymax) = (400, 400);
my @domains;
for (1..30) {
rgb => [int rand 255, int rand 255, int rand 255]
}
}
for my $type (keys %type) {
our $img = Imager->new(xsize => $xmax, ysize => $ymax, channels => 3);
voronoi($type, $xmax, $ymax, @domains);
$img->write(file => "voronoi-$type.png");
sub voronoi {
my($type, $xmax, $ymax, @d) = @_;
for my $x (0..$xmax) {
for my $y (0..$ymax) {
my $i = 0;
my $d = 10e6;
for (0..$#d) {
my $dd = &{$type{$type}}($d[$_]{'x'}, $d[$_]{'y'}, $x, $y);
if ($dd < $d) { $d = $dd; $i = $_ }
}
$img->setpixel(x => $x, y => $y, color => $d[$i]{rgb} );
}
}
}
sub dot {
my($radius, @d) = @_;
for (0..$#d) {
my $dx = $d[$_]{'x'};
my $dy = $d[$_]{'y'};
for my $x ($dx-$radius .. $dx+$radius) {
for my $y ($dy-$radius .. $dy+$radius) {
$img->setpixel(x => $x, y => $y, color => [0,0,0]);
}
}
}
}
}</syntaxhighlight>
[https://github.com/SqrtNegInf/Rosettacode-Perl5-Smoke/blob/master/ref/voronoi-Euclidean.png Euclidean Voronoi diagram] (offsite image)
=={{header|Phix}}==
{{trans|Liberty_BASIC}}
{{libheader|Phix/pGUI}}
{{libheader|Phix/online}}
Lifted the calculation strategy from Liberty Basic. <br>
Can resize, double or halve sites (press +/-), and toggle between Euclid, Manhattan, and Minkowski (press e/m/w).
You can run this online [http://phix.x10.mx/p2js/voronoi.htm here] (it' a bit slow tho).
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\VoronoiDiagram.exw
-- ===============================
--
-- Can resize, double or halve the number of sites (press +/-), and toggle
-- between Euclid, Manhattan, and Minkowski (press e/m/w).
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #000000;">pGUI</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">Ihandle</span> <span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">timer</span>
<span style="color: #004080;">cdCanvas</span> <span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdcanvas</span>
<span style="color: #000080;font-style:italic;">-- Stop any current drawing process before starting a new one:
-- Without this it /is/ going to crash, if it tries to finish
-- drawing all 100 sites, when there are now only 50, for eg.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">timer_active</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nsites</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">200</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">last_width</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">last_height</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">siteX</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">siteY</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">siteC</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">EUCLID</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">MANHATTAN</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">MINKOWSKI</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">dmodes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"Euclid"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Manhattan"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Minkowski"</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">dmode</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">EUCLID</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">drawn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- (last dmode actually shown)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">distance</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">y2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span>
<span style="color: #000000;">x1</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">x2</span>
<span style="color: #000000;">y1</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">y2</span>
<span style="color: #008080;">switch</span> <span style="color: #000000;">dmode</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">EUCLID</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">y1</span> <span style="color: #000080;font-style:italic;">-- (no need for sqrt)</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">MANHATTAN</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">MINKOWSKI</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- ("" power(d,1/3))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">switch</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">d</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nearestIndex</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dist</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">checkRow</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">site</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">height</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">dxSquared</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">x1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siteX</span><span style="color: #0000FF;">[</span><span style="color: #000000;">site</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">x</span>
<span style="color: #008080;">switch</span> <span style="color: #000000;">dmode</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">EUCLID</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dxSquared</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x1</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">MANHATTAN</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dxSquared</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">MINKOWSKI</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dxSquared</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">switch</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">height</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- atom dSquared = distance(siteX[site],siteY[site],x,y) -- (sub-optimal..)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">dSquared</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">y1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siteY</span><span style="color: #0000FF;">[</span><span style="color: #000000;">site</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">y</span>
<span style="color: #008080;">switch</span> <span style="color: #000000;">dmode</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">EUCLID</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dSquared</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dxSquared</span><span style="color: #0000FF;">+</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">y1</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">MANHATTAN</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dSquared</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dxSquared</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">MINKOWSKI</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dSquared</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dxSquared</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">switch</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dSquared</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dSquared</span>
<span style="color: #000000;">nearestIndex</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">site</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">redraw_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/*ih*/</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">width</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">height</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupGetIntInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DRAWSIZE"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">width</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">last_width</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">height</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">last_height</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">nsites</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">siteX</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nsites</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">nsites</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">siteX</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">width</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nsites</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">siteY</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">height</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nsites</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">siteC</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">#FFFFFF</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nsites</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">last_width</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">width</span>
<span style="color: #000000;">last_height</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">height</span>
<span style="color: #000000;">drawn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">drawn</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">dmode</span> <span style="color: #000080;font-style:italic;">-- (prevent double-draw, and)</span>
<span style="color: #008080;">and</span> <span style="color: #008080;">not</span> <span style="color: #000000;">timer_active</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (drawing when rug moved..)</span>
<span style="color: #000000;">drawn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dmode</span>
<span style="color: #7060A8;">cdCanvasActivate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasClear</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">t1</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">0.25</span>
<span style="color: #000000;">nearestIndex</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">height</span><span style="color: #0000FF;">),</span><span style="color: #000000;">width</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">dist</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">height</span><span style="color: #0000FF;">),</span><span style="color: #000000;">width</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- fill distance table with distances from the first site</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">x1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siteX</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">y1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siteY</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">width</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">height</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">distance</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">timer_active</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--for other towns</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nsites</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- look left</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">siteX</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">checkRow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">height</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- look right</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">siteX</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">width</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">checkRow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">height</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">timer_active</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">IupSetStrAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Voronoi diagram (generating - %3.2f%%)"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">nsites</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">IupFlush</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">0.25</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">height</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nearest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nearestIndex</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">width</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nearestIndex</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]<></span><span style="color: #000000;">nearest</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">siteC</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nearest</span><span style="color: #0000FF;">])</span>
<span style="color: #7060A8;">cdCanvasLine</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nearest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nearestIndex</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">timer_active</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">siteC</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nearest</span><span style="color: #0000FF;">])</span>
<span style="color: #7060A8;">cdCanvasLine</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">width</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">timer_active</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_BLACK</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nsites</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">cdCanvasSector</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">siteX</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">siteY</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">360</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">cdCanvasFlush</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupSetStrAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Voronoi diagram - %s, %dx%d, %d sites, %3.2fs"</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">dmodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dmode</span><span style="color: #0000FF;">],</span><span style="color: #000000;">width</span><span style="color: #0000FF;">,</span><span style="color: #000000;">height</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nsites</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">map_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cdcanvas</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">cdCreateCanvas</span><span style="color: #0000FF;">(</span><span style="color: #004600;">CD_IUP</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cddbuffer</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">cdCreateCanvas</span><span style="color: #0000FF;">(</span><span style="color: #004600;">CD_DBUFFER</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdcanvas</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasSetBackground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_WHITE</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_BLACK</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">key_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/*ih*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #004600;">K_ESC</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_CLOSE</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">wasdmode</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dmode</span>
<span style="color: #008080;">switch</span> <span style="color: #000000;">c</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">case</span> <span style="color: #008000;">'+'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">nsites</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">case</span> <span style="color: #008000;">'-'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">nsites</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nsites</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">case</span> <span style="color: #008000;">'E'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'e'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dmode</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">EUCLID</span>
<span style="color: #008080;">case</span> <span style="color: #008000;">'M'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'m'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dmode</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">MANHATTAN</span>
<span style="color: #008080;">case</span> <span style="color: #008000;">'W'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'w'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">dmode</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">MINKOWSKI</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">switch</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dmode</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">wasdmode</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">nsites</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">siteX</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- give any current drawing process 0.1s to abandon:</span>
<span style="color: #000000;">timer_active</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #7060A8;">IupStoreAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">timer</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"YES"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- IupUpdate(canvas)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_CONTINUE</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">timer_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/*ih*/</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">timer_active</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #7060A8;">IupStoreAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">timer</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"RUN"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"NO"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupUpdate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_IGNORE</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupOpen</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">canvas</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupCanvas</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"RASTERSIZE=600x400"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupSetCallbacks</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"MAP_CB"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"map_cb"</span><span style="color: #0000FF;">),</span>
<span style="color: #008000;">"ACTION"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"redraw_cb"</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">timer</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupTimer</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"timer_cb"</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (inactive)</span>
<span style="color: #000000;">dlg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupDialog</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span><span style="color: #008000;">`TITLE="Voronoi diagram"`</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupSetCallback</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"KEY_CB"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"key_cb"</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">IupShow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"RASTERSIZE"</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- release the minimum limitation</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">IupMainLoop</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
=={{header|Processing}}==
{{trans|Python}}
<syntaxhighlight lang="java">void setup() {
size(500, 500);
generateVoronoiDiagram(width, height, 25);
saveFrame("VoronoiDiagram.png");
}
void generateVoronoiDiagram(int w, int h, int num_cells) {
int nx[] = new int[num_cells];
int ny[] = new int[num_cells];
int nr[] = new int[num_cells];
int ng[] = new int[num_cells];
int nb[] = new int[num_cells];
for (int n=0; n < num_cells; n++) {
nx[n]=int(random(w));
ny[n]=int(random(h));
nr[n]=int(random(256));
ng[n]=int(random(256));
nb[n]=int(random(256));
for (int y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
float dmin = dist(0, 0, w - 1, h - 1);
int j = -1;
for (int i=0; i < num_cells; i++) {
float d = dist(0, 0, nx[i] - x, ny[i] - y);
if (d < dmin) {
dmin = d;
j = i;
}
}
set(x, y, color(nr[j], ng[j], nb[j]));
}
}
}
}
</syntaxhighlight>
==={{header|Processing Python mode}}===
{{trans|Python}}
<syntaxhighlight lang="python">def setup():
size(500, 500)
generate_voronoi_diagram(width, height, 25)
saveFrame("VoronoiDiagram.png")
def generate_voronoi_diagram(w, h, num_cells):
nx, ny, nr, ng, nb = [], [], [], [], []
for i in range(num_cells):
nx.append(int(random(w)))
ny.append(int(random(h)))
nr.append(int(random(256)))
ng.append(int(random(256)))
nb.append(int(random(256)))
for y in range(h):
for x in range(w):
dmin = dist(0, 0, w - 1, h - 1)
j = -1
for i in range(num_cells):
d = dist(0, 0, nx[i] - x, ny[i] - y)
if d < dmin:
dmin = d
j = i
set(x, y, color(nr[j], ng[j], nb[j]))
</syntaxhighlight>
=={{header|Prolog}}==
Line 1,496 ⟶ 1,912:
<
voronoi :-
V is random(20) + 20,
Line 1,557 ⟶ 1,973:
minkowski_3(X1, Y1, X2, Y2, D) :-
D is (abs(X2 - X1)**3 + abs(Y2-Y1)**3)**0.33.
</syntaxhighlight>
[[File:prolog_manhattan.png|320px]]
[[File:prolog_euclide.png|320px]]
Line 1,566 ⟶ 1,982:
===Euclidean===
[[File:Voronoi_PureBasic.png|320px|thumb|center|Voronoi Diagram in PureBasic]]
<
x.i: y.i
Colour.i: FillColour.i
Line 1,635 ⟶ 2,051:
If file$ <> ""
SaveImage(img, file$, #PB_ImagePlugin_PNG)
EndIf</
===Taxicab===
[[File:Voronoi_Diagram_in_PureBasic_(Taxicab).png|320px|thumb|center|Voronoi Diagram in PureBasic]]
<
x.i: y.i
Colour.i: FillColour.i
Line 1,706 ⟶ 2,122:
If file$ <> ""
SaveImage(img, file$, #PB_ImagePlugin_PNG)
EndIf</
=={{header|Python}}==
<
import random
import math
Line 1,742 ⟶ 2,158:
image.show()
generate_voronoi_diagram(500, 500, 25)</
{{out}}
[[File:Voronoi_python.png|500px|thumb|center|Voronoi Diagram in Python]]
Alternatively, vectorized code leveraging numpy and scipy is 2x shorter and 10x faster, as seen below.
Note that for large numbers of points, using a KDTree will be much faster thanks to lookups in log(N) time rather than N comparisons at every coordinate. The code below has running time O(X*Y*log(N)), whereas the code above has running time O(X*Y*N). For 1000 points, the code below is 250x faster than the above.
Alternative metrics can be supported by using a [https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html#sklearn.neighbors.KDTree.query scikit-learn KDTree ].
<syntaxhighlight lang="python">
import numpy as np
from PIL import Image
from scipy.spatial import KDTree
def generate_voronoi_diagram(X, Y, num_cells):
# Random colors and points
colors = np.random.randint((256, 256, 256), size=(num_cells, 3), dtype=np.uint8)
points = np.random.randint((Y, X), size=(num_cells, 2))
# Construct a list of all possible (y,x) coordinates
idx = np.indices((Y, X))
coords = np.moveaxis(idx, 0, -1).reshape((-1, 2))
# Find the closest point to each coordinate
_d, labels = KDTree(points).query(coords)
labels = labels.reshape((Y, X))
# Export an RGB image
rgb = colors[labels]
img = Image.fromarray(rgb, mode='RGB')
img.save('VoronoiDiagram.png', 'PNG')
img.show()
return rgb
</syntaxhighlight>
=={{header|QB64}}==
{{trans|Liberty Basic}}
<syntaxhighlight lang="qb64">_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</syntaxhighlight>
=={{header|R}}==
Line 1,761 ⟶ 2,281:
[[File:VDR310.png|200px|right|thumb|Output VDR310.png]]
<syntaxhighlight lang="r">
## HF#1 Random Hex color
randHclr <- function() {
Line 1,813 ⟶ 2,333:
pVoronoiD(10,"","",2) ## Manhattan metric
pVoronoiD(10,"","",3) ## Minkovski metric
</syntaxhighlight>
{{Output}}
<pre>
Line 1,836 ⟶ 2,356:
First approach
<
#lang racket
Line 1,864 ⟶ 2,384:
(define c (argmin (curryr (metric) x) centroids))
(dict-set res c (cons x (dict-ref res c)))))
</syntaxhighlight>
Different metrics
<
(define (euclidean-distance a b)
(for/sum ([x (in-vector a)] [y (in-vector b)])
Line 1,877 ⟶ 2,397:
(define metric (make-parameter euclidean-distance))
</syntaxhighlight>
[[File:voronoi2.png|200px|thumb|right|The contour plot of the classification function.]]
Line 1,885 ⟶ 2,405:
Alternative approach
<
;; Plots the Voronoi diagram as a contour plot of
;; the classification function built for a set of points
Line 1,910 ⟶ 2,430:
(λ (x)
(hash-ref tbl (argmin (curry (metric) x) centroids))))
</syntaxhighlight>
{{out}}
<
(define pts
(for/list ([i 50]) (vector (random) (random))))
Line 1,935 ⟶ 2,455:
#:alphas '(1))
(points3d pts3d #:sym 'fullcircle3)))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.09}}
{{trans|Python}}
Perhaps "Inspired by Python" would be more accurate.
Generates a Euclidean, a Taxicab and a Minkowski Voronoi diagram using the same set of domain points and colors.
<syntaxhighlight lang="raku" line>use Image::PNG::Portable;
my @bars = '▁▂▃▅▆▇▇▆▅▃▂▁'.comb;
my %type = ( # Voronoi diagram type distance calculation
'Taxicab' => sub ($px, $py, $x, $y) { ($px - $x).abs + ($py - $y).abs },
'Euclidean' => sub ($px, $py, $x, $y) { ($px - $x)² + ($py - $y)² },
'Minkowski' => sub ($px, $py, $x, $y) { ($px - $x)³.abs + ($py - $y)³.abs },
);
my $width = 400;
my $height = 400;
my $dots = 30;
my @domains = map { Hash.new(
'x' => (5..$width-5).roll,
'y' => (5..$height-5).roll,
'rgb' => [(64..255).roll xx 3]
) }, ^$dots;
for %type.keys -> $type {
print "\nGenerating $type diagram... ", ' ' x @bars;
my $img = voronoi(@domains, :w($width), :h($height), :$type);
@domains.map: *.&dot($img);
$img.write: "Voronoi-{$type}-perl6.png";
}
sub voronoi (@domains, :$w, :$h, :$type) {
my $png = Image::PNG::Portable.new: :width($w), :height($h);
(^$w).race.map: -> $x {
print "\b" x 2+@bars, @bars.=rotate(1).join , ' ';
for ^$h -> $y {
my ($, $i) = min @domains.map: { %type{$type}(%($_)<x>, %($_)<y>, $x, $y), $++ };
$png.set: $x, $y, |@domains[$i]<rgb>
}
}
$png
}
sub dot (%h, $png, $radius = 3) {
for (%h<x> X+ -$radius .. $radius) X (%h<y> X+ -$radius .. $radius) -> ($x, $y) {
$png.set($x, $y, 0, 0, 0) if ( %h<x> - $x + (%h<y> - $y) * i ).abs <= $radius;
}
}
</syntaxhighlight>
See [https://github.com/thundergnat/rc/blob/master/img/Voronoi-Euclidean-perl6.png Euclidean], [https://github.com/thundergnat/rc/blob/master/img/Voronoi-Taxicab-perl6.png Taxicab] & [https://github.com/thundergnat/rc/blob/master/img/Voronoi-Minkowski-perl6.png Minkowski] Voronoi diagram example images.
=={{header|Red}}==
<syntaxhighlight lang="red">Red [
Source: https://github.com/vazub/rosetta-red
Tabs: 4
Needs: 'View
]
comment {
This is a naive and therefore inefficient approach. For production-related tasks,
a proper full implementation of Fortune's algorithm should be preferred.
}
canvas: 500x500
num-points: 50
diagram-l1: make image! canvas
diagram-l2: make image! canvas
distance: function [
"Find Taxicab (d1) and Euclidean (d2) distances between two points"
pt1 [pair!]
pt2 [pair!]
][
d1: (absolute (pt1/x - pt2/x)) + absolute (pt1/y - pt2/y)
d2: square-root ((pt1/x - pt2/x) ** 2 + ((pt1/y - pt2/y) ** 2))
reduce [d1 d2]
]
;-- Generate random origin points with respective region colors
points: collect [
random/seed now/time/precise
loop num-points [
keep random canvas
keep random white
]
]
;-- Color each pixel, based on region it belongs to
repeat y canvas/y [
repeat x canvas/x [
coord: as-pair x y
min-dist: distance 1x1 canvas
color-l1: color-l2: none
foreach [point color] points [
d: distance point coord
if d/1 < min-dist/1 [min-dist/1: d/1 color-l1: color]
if d/2 < min-dist/2 [min-dist/2: d/2 color-l2: color]
]
poke diagram-l1 coord color-l1
poke diagram-l2 coord color-l2
]
]
;-- Draw origin points for regions
foreach [point color] points [
draw diagram-l1 compose [circle (point) 1]
draw diagram-l2 compose [circle (point) 1]
]
;-- Put results on screen
view [
title "Voronoi Diagram"
image diagram-l1 image diagram-l2
]
</syntaxhighlight>
=={{header|ReScript}}==
<syntaxhighlight lang="rescript">let n_sites = 60
let size_x = 640
let size_y = 480
let rand_int_range = (a, b) => a + Random.int(b - a + 1)
let dist_euclidean = (x, y) => { (x * x + y * y) }
let dist_minkowski = (x, y) => { (x * x * x + y * y * y) }
let dist_taxicab = (x, y) => { abs(x) + abs(y) }
let dist_f = dist_euclidean
let dist_f = dist_minkowski
let dist_f = dist_taxicab
let nearest_site = (site, x, y) => {
let ret = ref(0)
let dist = ref(0)
Js.Array2.forEachi(site, ((sx, sy), k) => {
let d = dist_f((x - sx), (y - sy))
if (k == 0 || d < dist.contents) {
dist.contents = d
ret.contents = k
}
})
ret.contents
}
let gen_map = (site, rgb) => {
let nearest = Belt.Array.make((size_x * size_y), 0)
let buf = Belt.Array.make((3 * size_x * size_y), 0)
for y in 0 to size_y - 1 {
for x in 0 to size_x - 1 {
nearest[y * size_x + x] = nearest_site(site, x, y)
}
}
for i in 0 to (size_y * size_x) - 1 {
let j = i * 3
let (r, g, b) = rgb[nearest[i]]
buf[j+0] = r
buf[j+1] = g
buf[j+2] = b
}
Printf.printf("P3\n%d %d\n255\n", size_x, size_y)
Js.Array2.forEach(buf, (d) => Printf.printf("%d\n", d))
}
{
Random.self_init ();
let site =
Belt.Array.makeBy(n_sites, (i) => {
(Random.int(size_x),
Random.int(size_y))
})
let rgb =
Belt.Array.makeBy(n_sites, (i) => {
(rand_int_range( 50, 120),
rand_int_range( 80, 180),
rand_int_range(140, 240))
})
gen_map(site, rgb)
}
</syntaxhighlight>
=={{header|Ring}}==
<
# Project : Voronoi diagram
load "guilib.ring"
Line 2,063 ⟶ 2,770:
next
return number(str)
</syntaxhighlight>
Output image:
https://www.dropbox.com/s/bjv9dhd0esnnokx/Voronoi.jpg?dl=0
=={{header|Ruby}}==
Uses [[Raster graphics operations/Ruby]]
[[File:voronoi_rb.png|thumb|right|Sample output from Ruby program]]
<syntaxhighlight lang="ruby"># frozen_string_literal: true
require_relative 'raster_graphics'
class ColourPixel < Pixel
Line 2,084 ⟶ 2,790:
def distance_to(px, py)
Math
end
end
width
height = 200
npoints = 20
pixmap = Pixmap.new(width, height)
@bases = npoints.times.collect do |
ColourPixel.new(
)
end
pixmap.each_pixel do |x, y|
nearest = @bases.min_by { |base| base.distance_to(x, y) }
pixmap[x, y] = nearest.colour
end
@bases.each do |base|
pixmap[base.x, base.y] = RGBColour::BLACK
pixmap.draw_circle(base, 2, RGBColour::BLACK)
end
pixmap.save_as_png(
{{libheader|RubyGems}}
{{libheader|JRubyArt}}
JRubyArt is a port of processing to ruby
<syntaxhighlight lang="ruby"># frozen_string_literal: true
Tile = Struct.new(:x, :y, :color) do
def sq_dist(a, b)
(x - a)**2 + (y - b)**2
end
end
attr_reader :tiles
def settings
size 500, 500
end
def setup
sketch_title 'Voronoi Diagram'
load_pixels
color_mode(HSB, 1.0)
@tiles = generate_tiles(30)
draw_voronoi
update_pixels
draw_voronoi_centers
end
def generate_tiles(num)
(0..num).map { Tile.new(rand(width), rand(height), color(rand, 1.0, 1.0)) }
end
def draw_voronoi
grid(width, height) do |x, y|
closest = tiles.min_by { |tile| tile.sq_dist(x, y) }
pixels[x + y * width] = closest.color
end
end
def draw_voronoi_centers
tiles.each do |center|
no_stroke
fill 0
ellipse(center.x, center.y, 4, 4)
end
end
</syntaxhighlight>
=={{header|Run BASIC}}==
<
#g flush()
spots = 100
Line 2,186 ⟶ 2,942:
end if
next y
end function</
=={{header|Rust}}==
Line 2,194 ⟶ 2,950:
The entire code, including the Crate.toml and a precompiled binary for Windows x86_64, can be found at https://github.com/ctrlcctrlv/interactive-voronoi/
<
extern crate opengl_graphics;
extern crate graphics;
Line 2,374 ⟶ 3,130:
);
}
</syntaxhighlight>
=={{header|Scala}}==
===Java Swing Interoperability===
{{libheader|Scala Java Swing interoperability}}
{{works with|Scala|2.13}}
<syntaxhighlight lang="scala">import java.awt.geom.Ellipse2D
import java.awt.image.BufferedImage
import java.awt.{Color, Graphics, Graphics2D}
import scala.math.sqrt
object Voronoi extends App {
private val (cells, dim) = (100, 1000)
private val rand = new scala.util.Random
private val color = Vector.fill(cells)(rand.nextInt(0x1000000))
private val image = new BufferedImage(dim, dim, BufferedImage.TYPE_INT_RGB)
private val g: Graphics2D = image.createGraphics()
private val px = Vector.fill(cells)(rand.nextInt(dim))
private val py = Vector.fill(cells)(rand.nextInt(dim))
for (x <- 0 until dim;
y <- 0 until dim) {
var n = 0
def distance(x1: Int, x2: Int, y1: Int, y2: Int) =
sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2).toDouble) // Euclidian
for (i <- px.indices
if distance(px(i), x, py(i), y) < distance(px(n), x, py(n), y))
n = i
image.setRGB(x, y, color(n))
}
g.setColor(Color.BLACK)
for (i <- px.indices) g.fill(new Ellipse2D.Double(px(i) - 2.5, py(i) - 2.5, 5, 5))
new javax.swing.JFrame("Voronoi Diagram") {
override def paint(g: Graphics): Unit = {g.drawImage(image, 0, 0, this); ()}
setBounds(0, 0, dim, dim)
setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE)
setLocationRelativeTo(null)
setResizable(false)
setVisible(true)
}
}</syntaxhighlight>
=={{header|Seed7}}==
[[file:Seed7Voronoi.png|thumb|right]]
<
include "draw.s7i";
include "keybd.s7i";
Line 2,429 ⟶ 3,232:
KEYBOARD := GRAPH_KEYBOARD;
readln(KEYBOARD);
end func;</
Original source: [http://seed7.sourceforge.net/algorith/graphic.htm#voronoi]
Line 2,435 ⟶ 3,238:
=={{header|Sidef}}==
{{trans|Python}}
<
func generate_voronoi_diagram(width, height, num_cells) {
var img = %
var (nx,ny,nr,ng,nb) = 5.of { [] }...
for i in (^num_cells) {
nx << rand(^width)
ny << rand(^height)
Line 2,449 ⟶ 3,252:
}
for y
var j = (^num_cells -> min_by {|i| hypot(nx[i]-x, ny[i]-y) })
img.setpixel(x => x, y
}
return img
Line 2,464 ⟶ 3,260:
var img = generate_voronoi_diagram(500, 500, 25)
img.write(file => 'VoronoiDiagram.png')</
Output image: [https://github.com/trizen/rc/blob/master/img/voronoi-diagram-sidef.png Voronoi diagram]
=={{header|Tcl}}==
{{libheader|Tk}}
<
proc r to {expr {int(rand()*$to)}}; # Simple helper
Line 2,502 ⟶ 3,299:
# To display while generating, uncomment this line and the other one so commented
#update
voronoi demo 60</
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|DOME}}
<syntaxhighlight lang="wren">import "graphics" for Canvas, Color
import "dome" for Window
import "random" for Random
class Game {
static init() {
Window.title = "Voronoi diagram"
var cells = 70
var size = 700
Window.resize(size, size)
Canvas.resize(size, size)
voronoi(cells, size)
}
static update() {}
static draw(alpha) {}
static distSq(x1, x2, y1, y2) { (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) }
static voronoi(cells, size) {
var r = Random.new()
var px = List.filled(cells, 0)
var py = List.filled(cells, 0)
var cl = List.filled(cells, 0)
for (i in 0...cells) {
px[i] = r.int(size)
py[i] = r.int(size)
cl[i] = Color.rgb(r.int(256), r.int(256), r.int(256))
}
for (x in 0...size) {
for (y in 0...size) {
var n = 0
for (i in 0...cells) {
if (distSq(px[i], x, py[i], y) < distSq(px[n], x, py[n], y)) n = i
}
Canvas.pset(x, y, cl[n])
}
}
for (i in 0...cells) {
Canvas.circlefill(px[i], py[i], 2, Color.black)
}
}
}</syntaxhighlight>
=={{header|XPL0}}==
[[File:VoronoiXPL0.gif|right]]
<
def N = 15; \number of sites
Line 2,527 ⟶ 3,372:
I:= ChIn(1); \wait for keystroke
SetVid($03); \restore normal text screen
]</
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">
clear screen
sites = 200
xEdge = 600
yEdge = 400
open window xEdge, yEdge
dim townX(sites), townY(sites), col$(sites)
for i =1 to sites
townX(i) =int(xEdge *ran(1))
townY(i) =int(yEdge *ran(1))
col$(i) = str$(int(256 * ran(1))) + ", " + str$(int(256 * ran(1))) + ", " + str$(int(256 * ran(1)))
color col$(i)
fill circle townX(i), townY(i), 2
next i
dim nearestIndex(xEdge, yEdge)
dim dist(xEdge, yEdge)
//fill distance table with distances from the first site
for x = 0 to xEdge - 1
for y = 0 to yEdge - 1
dist(x, y) = (townX(1) - x) ^ 2 + (townY(1) - y) ^ 2
nearestIndex(x, y) = 1
next y
next x
color 0,0,255
//for other towns
for i = 2 to sites
//display some progress
//print at(0,20) "computing: ", (i/sites*100) using "###.#", " %"
//look left
for x = townX(i) to 0 step -1
if not(checkRow(i, x,0, yEdge - 1)) break
next x
//look right
for x = townX(i) + 1 to xEdge - 1
if not(checkRow(i, x, 0, yEdge - 1)) break
next x
next i
for x = 0 to xEdge - 1
for y =0 to yEdge - 1
color col$(nearestIndex(x, y))
startY = y
nearest = nearestIndex(x, y)
for y = y + 1 to yEdge
if nearestIndex(x, y) <> nearest then y = y - 1 : break : end if
next y
line x, startY, x, y + 1
next y
next x
color 0,0,0
for i =1 to sites
fill circle townX( i), townY( i), 2
next i
print peek("millisrunning"), " ms"
sub checkRow(site, x, startY, endY)
local dxSquared, y, check
dxSquared = (townX(site) - x) ^ 2
for y = startY to endY
dSquared = (townY(site) - y) ^ 2 + dxSquared
if dSquared <= dist(x, y) then
dist(x, y) = dSquared
nearestIndex(x, y) = site
check = 1
end if
next y
return check
end sub</syntaxhighlight>
{{trans|Python}}
<syntaxhighlight lang="yabasic">width = 500 : height = 500
open window width, height
export sub hypot(a, b)
return (sqrt(a^2+b^2))
end sub
sub generate_voronoi_diagram(width, height, num_cells)
local nx(num_cells), ny(num_cells), nr(num_cells), ng(num_cells), nb(num_cells)
for i = 1 to num_cells
nx(i) = ran(width)
ny(i) = ran(height)
nr(i) = ran(256)
ng(i) = ran(256)
nb(i) = ran(256)
next
for y = 1 to height
for x = 1 to width
dmin = hypot(width-1, height-1)
j = -1
for i = 1 to num_cells
d = hypot(nx(i)-x, ny(i)-y)
if d < dmin dmin = d : j = i
next
color nr(j), ng(j), ng(j)
dot x, y
next
next
end sub
generate_voronoi_diagram(width, height, 25)</syntaxhighlight>
=={{header|zkl}}==
Line 2,533 ⟶ 3,493:
{{trans|Python}}
[[File:VoronoiDiagram.zkl.jpg|250px|thumb|right]]
<
image,imgx,imgy:=PPM(width,height),width,height;
nx:=num_cells.pump(List,(0).random.fp(imgx));
Line 2,551 ⟶ 3,511:
}
image
}</
<
{{omit from|GUISS}}
| |||