Voronoi diagram: Difference between revisions
Added Easylang
(added ReScript) |
(Added Easylang) |
||
| (6 intermediate revisions by 3 users not shown) | |||
Line 14:
=={{header|AutoHotkey}}==
Requires [https://www.autohotkey.com/boards/viewtopic.php?f=6&t=6517 GDIP Library]
<
Gui, 1: +E0x20 +Caption +E0x80000 +LastFound +AlwaysOnTop +ToolWindow +OwnDialogs
Gui, 1: Show, NA
Line 91:
ExitApp
Return
;------------------------------------------------------------------------</
=={{header|BASIC256}}==
{{trans|Python}}
<
ancho = 500 : alto = 500
Line 137:
refresh
imgsave "Voronoi_diagram.jpg", "jpg"
end</
Line 145:
Image is in PNM P6, written to stdout.
Run as <code>a.out > stuff.pnm</code>.
<
#include <stdlib.h>
#include <string.h>
Line 263:
gen_map();
return 0;
}</
=={{header|C++}}==
[[File:voronoi_cpp.png|256px]]
<
#include <windows.h>
#include <vector>
Line 459:
return 0;
}
</syntaxhighlight>
=={{header|D}}==
{{trans|Go}}
<
struct Point { uint x, y; }
Line 503:
.generateVoronoi(imageWidth, imageHeight)
.savePPM6("voronoi.ppm");
}</
=={{header|Delphi}}==
<
uses System.Generics.Collections;
Line 614:
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}}
<
Screenres ancho, alto, 8
Cls
Line 654 ⟶ 690:
Generar_Diagrama_Voronoi(ancho, alto, 25)
Bsave "Voronoi_diadram.bmp",0
Sleep</
=={{header|Go}}==
[[file:GoVoronoi.png|thumb|right|Output png]]
<
import (
Line 741 ⟶ 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 807 ⟶ 842:
writeImageToBMP "out.bmp" voro
</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
Line 813 ⟶ 848:
[[File:Voronoi-normal_unicon.PNG|right]]
[[File:Voronoi-taxi_unicon.PNG|right]]
<
record site(x,y,colour) # site data position and colour
Line 883 ⟶ 918:
every site := !siteL do # mark sites
DrawCircle(site.x,site.y,1)
end</
{{libheader|Icon Programming Library}}
Line 895 ⟶ 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 903 ⟶ 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 911 ⟶ 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 993 ⟶ 1,028:
}
}
</syntaxhighlight>
=={{header|JavaScript}}==
Line 1,019 ⟶ 1,054:
[[File:VDjs310.png|200px|right|thumb|Output VDjs310.png]]
<
<html>
<head><title>Voronoi diagram</title>
Line 1,081 ⟶ 1,116:
</body>
</html>
</syntaxhighlight>
{{Output}}
<pre>
Line 1,090 ⟶ 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 1,104 ⟶ 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 1,130 ⟶ 1,165:
img = testimage("mandrill")
voronoi_img!(img, 300)
</syntaxhighlight>
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.awt.Color
Line 1,184 ⟶ 1,219:
fun main(args: Array<String>) {
Voronoi(70, 700).isVisible = true
}</
=={{header|Liberty BASIC}}==
Line 1,191 ⟶ 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,283 ⟶ 1,318:
next y
end function
</syntaxhighlight>
=={{header|Lua}}==
Line 1,289 ⟶ 1,324:
{{works with|LÖVE|11.3}}
{{trans|Python}}
<
function love.load( )
love.math.setRandomSeed( os.time( ) ) --set the random seed
Line 1,367 ⟶ 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,386 ⟶ 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,418 ⟶ 1,453:
{{works with|nim|0.19.4}}
{{libheader|nim-libgd}}
<
from sequtils import newSeqWith
from random import rand, randomize
Line 1,472 ⟶ 1,507:
main()
</syntaxhighlight>
=={{header|OCaml}}==
{{works with|ocaml|4.07.1}}
<
let size_x = 640
Line 1,536 ⟶ 1,571:
rand_int_range 20 140))
in
gen_map ~site ~rgb</
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use Imager;
Line 1,593 ⟶ 1,628:
}
}
}</
[https://github.com/SqrtNegInf/Rosettacode-Perl5-Smoke/blob/master/ref/voronoi-Euclidean.png Euclidean Voronoi diagram] (offsite image)
Line 1,603 ⟶ 1,638:
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).
<!--<
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\VoronoiDiagram.exw
Line 1,805 ⟶ 1,840:
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</
=={{header|Processing}}==
{{trans|Python}}
<
size(500, 500);
generateVoronoiDiagram(width, height, 25);
Line 1,843 ⟶ 1,878:
}
}
</syntaxhighlight>
==={{header|Processing Python mode}}===
{{trans|Python}}
<
size(500, 500)
generate_voronoi_diagram(width, height, 25)
Line 1,870 ⟶ 1,905:
j = i
set(x, y, color(nr[j], ng[j], nb[j]))
</syntaxhighlight>
=={{header|Prolog}}==
Line 1,877 ⟶ 1,912:
<
voronoi :-
V is random(20) + 20,
Line 1,938 ⟶ 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,947 ⟶ 1,982:
===Euclidean===
[[File:Voronoi_PureBasic.png|320px|thumb|center|Voronoi Diagram in PureBasic]]
<
x.i: y.i
Colour.i: FillColour.i
Line 2,016 ⟶ 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 2,087 ⟶ 2,122:
If file$ <> ""
SaveImage(img, file$, #PB_ImagePlugin_PNG)
EndIf</
=={{header|Python}}==
<
import random
import math
Line 2,123 ⟶ 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}}
<
Dim As Integer pnt, px, py, i, x, y, adjct, sy, ly
Line 2,197 ⟶ 2,264:
End If
Next
End Function</
=={{header|R}}==
Line 2,214 ⟶ 2,281:
[[File:VDR310.png|200px|right|thumb|Output VDR310.png]]
<syntaxhighlight lang="r">
## HF#1 Random Hex color
randHclr <- function() {
Line 2,266 ⟶ 2,333:
pVoronoiD(10,"","",2) ## Manhattan metric
pVoronoiD(10,"","",3) ## Minkovski metric
</syntaxhighlight>
{{Output}}
<pre>
Line 2,289 ⟶ 2,356:
First approach
<
#lang racket
Line 2,317 ⟶ 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 2,330 ⟶ 2,397:
(define metric (make-parameter euclidean-distance))
</syntaxhighlight>
[[File:voronoi2.png|200px|thumb|right|The contour plot of the classification function.]]
Line 2,338 ⟶ 2,405:
Alternative approach
<
;; Plots the Voronoi diagram as a contour plot of
;; the classification function built for a set of points
Line 2,363 ⟶ 2,430:
(λ (x)
(hash-ref tbl (argmin (curry (metric) x) centroids))))
</syntaxhighlight>
{{out}}
<
(define pts
(for/list ([i 50]) (vector (random) (random))))
Line 2,388 ⟶ 2,455:
#:alphas '(1))
(points3d pts3d #:sym 'fullcircle3)))
</syntaxhighlight>
=={{header|Raku}}==
Line 2,398 ⟶ 2,465:
Generates a Euclidean, a Taxicab and a Minkowski Voronoi diagram using the same set of domain points and colors.
<syntaxhighlight lang="raku"
my @bars = '▁▂▃▅▆▇▇▆▅▃▂▁'.comb;
Line 2,442 ⟶ 2,509:
}
}
</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}}==
<
Source: https://github.com/vazub/rosetta-red
Tabs: 4
Line 2,509 ⟶ 2,576:
image diagram-l1 image diagram-l2
]
</syntaxhighlight>
=={{header|ReScript}}==
<
let size_x = 640
Line 2,578 ⟶ 2,645:
gen_map(site, rgb)
}
</syntaxhighlight>
=={{header|Ring}}==
<
# Project : Voronoi diagram
Line 2,703 ⟶ 2,770:
next
return number(str)
</syntaxhighlight>
Output image:
Line 2,711 ⟶ 2,778:
Uses [[Raster graphics operations/Ruby]]
[[File:voronoi_rb.png|thumb|right|Sample output from Ruby program]]
<
require_relative 'raster_graphics'
Line 2,749 ⟶ 2,816:
end
pixmap.save_as_png('voronoi_rb.png')</
{{libheader|RubyGems}}
{{libheader|JRubyArt}}
JRubyArt is a port of processing to ruby
<
Tile = Struct.new(:x, :y, :color) do
Line 2,798 ⟶ 2,865:
</syntaxhighlight>
=={{header|Run BASIC}}==
<
#g flush()
spots = 100
Line 2,875 ⟶ 2,942:
end if
next y
end function</
=={{header|Rust}}==
Line 2,883 ⟶ 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 3,063 ⟶ 3,130:
);
}
</syntaxhighlight>
=={{header|Scala}}==
Line 3,069 ⟶ 3,136:
{{libheader|Scala Java Swing interoperability}}
{{works with|Scala|2.13}}
<
import java.awt.image.BufferedImage
import java.awt.{Color, Graphics, Graphics2D}
Line 3,110 ⟶ 3,177:
}
}</
=={{header|Seed7}}==
[[file:Seed7Voronoi.png|thumb|right]]
<
include "draw.s7i";
include "keybd.s7i";
Line 3,165 ⟶ 3,232:
KEYBOARD := GRAPH_KEYBOARD;
readln(KEYBOARD);
end func;</
Original source: [http://seed7.sourceforge.net/algorith/graphic.htm#voronoi]
Line 3,171 ⟶ 3,238:
=={{header|Sidef}}==
{{trans|Python}}
<
func generate_voronoi_diagram(width, height, num_cells) {
Line 3,193 ⟶ 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 3,232 ⟶ 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}}
<
import "dome" for Window
import "random" for Random
Line 3,280 ⟶ 3,347:
}
}
}</
=={{header|XPL0}}==
[[File:VoronoiXPL0.gif|right]]
<
def N = 15; \number of sites
Line 3,305 ⟶ 3,372:
I:= ChIn(1); \wait for keystroke
SetVid($03); \restore normal text screen
]</
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">
clear screen
Line 3,385 ⟶ 3,452:
next y
return check
end sub</
{{trans|Python}}
<
open window width, height
Line 3,420 ⟶ 3,487:
end sub
generate_voronoi_diagram(width, height, 25)</
=={{header|zkl}}==
Line 3,426 ⟶ 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 3,444 ⟶ 3,511:
}
image
}</
<
{{omit from|GUISS}}
| |||