Voronoi diagram: Difference between revisions

Line 14:

=={{header|AutoHotkey}}==

Requires [https://www.autohotkey.com/boards/viewtopic.php?f=6&t=6517 GDIP Library]

<~~lang~~ ~~AutoHotkey~~>;------------------------------------------------------------------------

<syntaxhighlight lang="autohotkey">;------------------------------------------------------------------------

Gui, 1: +E0x20 +Caption +E0x80000 +LastFound +AlwaysOnTop +ToolWindow +OwnDialogs

Gui, 1: Show, NA

Line 91:

ExitApp

Return

;------------------------------------------------------------------------</~~lang~~>

;------------------------------------------------------------------------</syntaxhighlight>

=={{header|BASIC256}}==

<~~lang~~ ~~BASIC256~~>global ancho, alto

<syntaxhighlight lang="basic256">global ancho, alto

ancho = 500 : alto = 500

Line 137:

refresh

imgsave "Voronoi_diagram.jpg", "jpg"

end</~~lang~~>

end</syntaxhighlight>

Line 145:

Image is in PNM P6, written to stdout.

Run as <code>a.out > stuff.pnm</code>.

<~~lang~~ c>#include <stdio.h>

<syntaxhighlight lang="c">#include <stdio.h>

#include <stdlib.h>

#include <string.h>

Line 263:

gen_map();

return 0;

}</~~lang~~>

}</syntaxhighlight>

=={{header|C++}}==

[[File:voronoi_cpp.png|256px]]

<~~lang~~ cpp>

#include <windows.h>

#include <vector>

Line 459:

return 0;

}

</syntaxhighlight>

</lang>

=={{header|D}}==

<~~lang~~ d>import std.random, std.algorithm, std.range, bitmap;

<syntaxhighlight lang="d">import std.random, std.algorithm, std.range, bitmap;

struct Point { uint x, y; }

Line 503:

.generateVoronoi(imageWidth, imageHeight)

.savePPM6("voronoi.ppm");

}</~~lang~~>

}</syntaxhighlight>

=={{header|Delphi}}==

<~~lang~~ delphi>

uses System.Generics.Collections;

Line 614:

Canvas.Draw(0,0, img);

end;

</syntaxhighlight>

</lang>

=={{header|FreeBASIC}}==

<~~lang~~ freebasic>Dim Shared As Integer ancho = 500, alto = 500

<syntaxhighlight lang="freebasic">Dim Shared As Integer ancho = 500, alto = 500

Screenres ancho, alto, 8

Cls

Line 654:

Generar_Diagrama_Voronoi(ancho, alto, 25)

Bsave "Voronoi_diadram.bmp",0

Sleep</~~lang~~>

Sleep</syntaxhighlight>

=={{header|Go}}==

[[file:GoVoronoi.png|thumb|right|Output png]]

<~~lang~~ go>package main

<syntaxhighlight lang="go">package main

import (

Line 741:

fmt.Println(err)

}

}</~~lang~~>

}</syntaxhighlight>

=={{header|Haskell}}==

Uses the repa and repa-io libraries.

<~~lang~~ haskell>

-- Compile with: ghc -O2 -fllvm -fforce-recomp -threaded --make

{-# LANGUAGE BangPatterns #-}

Line 807:

writeImageToBMP "out.bmp" voro

</syntaxhighlight>

</lang>

=={{header|Icon}} and {{header|Unicon}}==

Line 813:

[[File:Voronoi-normal_unicon.PNG|right]]

[[File:Voronoi-taxi_unicon.PNG|right]]

<~~lang~~ ~~Icon~~>link graphics,printf,strings

<syntaxhighlight lang="icon">link graphics,printf,strings

record site(x,y,colour) # site data position and colour

Line 883:

every site := !siteL do # mark sites

DrawCircle(site.x,site.y,1)

end</~~lang~~>

end</syntaxhighlight>

Line 895:

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.

<~~lang~~ j>NB. (number of points) voronoi (shape)

<syntaxhighlight lang="j">NB. (number of points) voronoi (shape)

NB. Generates an array of indices of the nearest point

voronoi =: 4 :0

Line 903:

load'viewmat'

viewmat 25 voronoi 500 500</~~lang~~>

viewmat 25 voronoi 500 500</syntaxhighlight>

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:

This a direct reformulation of the explicit version.

<~~lang~~ j>Voronoi=. ,"0/&i./@:] (i. <./)@:(+/@:*:@:-"1)"1 _ ] ?@$~ 2 ,~ [

<syntaxhighlight lang="j">Voronoi=. ,"0/&i./@:] (i. <./)@:(+/@:*:@:-"1)"1 _ ] ?@$~ 2 ,~ [

viewmat 25 Voronoi 500 500 [ load'viewmat'</~~lang~~>

viewmat 25 Voronoi 500 500 [ load'viewmat'</syntaxhighlight>

=={{header|Java}}==

<~~lang~~ java>import java.awt.Color;

<syntaxhighlight lang="java">import java.awt.Color;

import java.awt.Graphics;

import java.awt.Graphics2D;

Line 993:

}

</syntaxhighlight>

</lang>

=={{header|JavaScript}}==

Line 1,019:

[[File:VDjs310.png|200px|right|thumb|Output VDjs310.png]]

<~~lang~~ javascript>

<html>

<head><title>Voronoi diagram</title>

Line 1,081:

</body>

</html>

</syntaxhighlight>

</lang>

<pre>

Line 1,090:

=={{header|Julia}}==

First version generates an image with random colors as centroids for the voronoi tesselation:

<~~lang~~ julia>

using Images

function voronoi(w, h, n_centroids)

Line 1,104:

end

img = voronoi(800, 600, 200)

</syntaxhighlight>

</lang>

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:

<~~lang~~ julia>

using TestImages, Images

function voronoi_img!(img, n_centroids)

Line 1,130:

img = testimage("mandrill")

voronoi_img!(img, 300)

</syntaxhighlight>

</lang>

=={{header|Kotlin}}==

<~~lang~~ scala>// version 1.1.3

<syntaxhighlight lang="scala">// version 1.1.3

import java.awt.Color

Line 1,184:

fun main(args: Array<String>) {

Voronoi(70, 700).isVisible = true

}</~~lang~~>

}</syntaxhighlight>

=={{header|Liberty BASIC}}==

Line 1,191:

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..

WindowWidth =600

WindowHeight =600

Line 1,283:

next y

end function

</syntaxhighlight>

</lang>

=={{header|Lua}}==

Line 1,289:

<~~lang~~ lua>

function love.load( )

love.math.setRandomSeed( os.time( ) ) --set the random seed

Line 1,367:

end

</syntaxhighlight>

</lang>

=={{header|Mathematica}}/{{header|Wolfram Language}}==

<~~lang~~ ~~Mathematica~~>Needs["ComputationalGeometry`"]

<syntaxhighlight lang="mathematica">Needs["ComputationalGeometry`"]

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}}]</~~lang~~>

{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}}]</syntaxhighlight>

[[File:mma_voronoi.png|Right]]

=={{header|МК-61/52}}==

<lang>0 П4

<syntaxhighlight lang="text">0 П4

0 П5

ИП0 1 - x^2 ИП1 1 - x^2 + КвКор П3

Line 1,386:

КИП7 [x] С/П

КИП5 ИП5 ИП1 - x>=0 04

КИП4 ИП4 ИП0 - x>=0 02</~~lang~~>

КИП4 ИП4 ИП0 - x>=0 02</syntaxhighlight>

''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:

<~~lang~~ nim>

from sequtils import newSeqWith

from random import rand, randomize

Line 1,472:

main()

</syntaxhighlight>

</lang>

=={{header|OCaml}}==

<~~lang~~ ocaml>let n_sites = 220

<syntaxhighlight lang="ocaml">let n_sites = 220

let size_x = 640

Line 1,536:

rand_int_range 20 140))

in

gen_map ~site ~rgb</~~lang~~>

gen_map ~site ~rgb</syntaxhighlight>

=={{header|Perl}}==

<~~lang~~ perl>use strict;

<syntaxhighlight lang="perl">use strict;

use warnings;

use Imager;

Line 1,593:

}

}</~~lang~~>

}</syntaxhighlight>

[https://github.com/SqrtNegInf/Rosettacode-Perl5-Smoke/blob/master/ref/voronoi-Euclidean.png Euclidean Voronoi diagram] (offsite image)

Line 1,603:

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).

--

-- demo\rosetta\VoronoiDiagram.exw

Line 1,805:

main()

=={{header|Processing}}==

<~~lang~~ ~~Java~~>void setup() {

<syntaxhighlight lang="java">void setup() {

size(500, 500);

generateVoronoiDiagram(width, height, 25);

Line 1,843:

}

</syntaxhighlight>

</lang>

==={{header|Processing Python mode}}===

<~~lang~~ ~~Python~~>def setup():

<syntaxhighlight lang="python">def setup():

size(500, 500)

generate_voronoi_diagram(width, height, 25)

Line 1,870:

j = i

set(x, y, color(nr[j], ng[j], nb[j]))

</syntaxhighlight>

</lang>

=={{header|Prolog}}==

Line 1,877:

<~~lang~~ ~~Prolog~~>:- dynamic pt/6.

<syntaxhighlight lang="prolog">:- dynamic pt/6.

voronoi :-

V is random(20) + 20,

Line 1,938:

minkowski_3(X1, Y1, X2, Y2, D) :-

D is (abs(X2 - X1)**3 + abs(Y2-Y1)**3)**0.33.

</syntaxhighlight>

</lang>

[[File:prolog_manhattan.png|320px]]

[[File:prolog_euclide.png‎|320px]]

Line 1,947:

===Euclidean===

[[File:Voronoi_PureBasic.png‎|320px|thumb|center|Voronoi Diagram in PureBasic]]

<~~lang~~ ~~PureBasic~~>Structure VCoo

<syntaxhighlight lang="purebasic">Structure VCoo

x.i: y.i

Colour.i: FillColour.i

Line 2,016:

If file$ <> ""

SaveImage(img, file$, #PB_ImagePlugin_PNG)

EndIf</~~lang~~>

EndIf</syntaxhighlight>

===Taxicab===

[[File:Voronoi_Diagram_in_PureBasic_(Taxicab).png‎|320px|thumb|center|Voronoi Diagram in PureBasic]]

<~~lang~~ ~~PureBasic~~>Structure VCoo

<syntaxhighlight lang="purebasic">Structure VCoo

x.i: y.i

Colour.i: FillColour.i

Line 2,087:

If file$ <> ""

SaveImage(img, file$, #PB_ImagePlugin_PNG)

EndIf</~~lang~~>

EndIf</syntaxhighlight>

=={{header|Python}}==

This implementation takes in a list of points, each point being a tuple and returns a dictionary consisting of all the points at a given site.

<~~lang~~ python>from PIL import Image

<syntaxhighlight lang="python">from PIL import Image

import random

import math

Line 2,123:

image.show()

generate_voronoi_diagram(500, 500, 25)</~~lang~~>

generate_voronoi_diagram(500, 500, 25)</syntaxhighlight>

[[File:Voronoi_python.png|500px|thumb|center|Voronoi Diagram in Python]]

Line 2,129:

=={{header|QB64}}==

<~~lang~~ qb64>_Title "Voronoi Diagram"

<syntaxhighlight lang="qb64">_Title "Voronoi Diagram"

Dim As Integer pnt, px, py, i, x, y, adjct, sy, ly

Line 2,197:

End If

End Function</~~lang~~>

End Function</syntaxhighlight>

=={{header|R}}==

Line 2,214:

[[File:VDR310.png|200px|right|thumb|Output VDR310.png]]

## HF#1 Random Hex color

randHclr <- function() {

Line 2,266:

pVoronoiD(10,"","",2) ## Manhattan metric

pVoronoiD(10,"","",3) ## Minkovski metric

</syntaxhighlight>

</lang>

<pre>

Line 2,289:

First approach

<~~lang~~ racket>

#lang racket

Line 2,317:

(define c (argmin (curryr (metric) x) centroids))

(dict-set res c (cons x (dict-ref res c)))))

</syntaxhighlight>

</lang>

Different metrics

<~~lang~~ racket>

(define (euclidean-distance a b)

(for/sum ([x (in-vector a)] [y (in-vector b)])

Line 2,330:

(define metric (make-parameter euclidean-distance))

</syntaxhighlight>

</lang>

[[File:voronoi2.png|200px|thumb|right|The contour plot of the classification function.]]

Line 2,338:

Alternative approach

<~~lang~~ racket>

;; Plots the Voronoi diagram as a contour plot of

;; the classification function built for a set of points

Line 2,363:

(λ (x)

(hash-ref tbl (argmin (curry (metric) x) centroids))))

</syntaxhighlight>

</lang>

<~~lang~~ racket>

(define pts

(for/list ([i 50]) (vector (random) (random))))

Line 2,388:

#:alphas '(1))

(points3d pts3d #:sym 'fullcircle3)))

</syntaxhighlight>

</lang>

=={{header|Raku}}==

Line 2,398:

Generates a Euclidean, a Taxicab and a Minkowski Voronoi diagram using the same set of domain points and colors.

<lang ~~perl6~~>use Image::PNG::Portable;

<syntaxhighlight lang="raku" line>use Image::PNG::Portable;

my @bars = '▁▂▃▅▆▇▇▆▅▃▂▁'.comb;

Line 2,442:

}

</syntaxhighlight>

</lang>

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}}==

<~~lang~~ red>Red [

<syntaxhighlight lang="red">Red [

Source: https://github.com/vazub/rosetta-red

Tabs: 4

Line 2,509:

image diagram-l1 image diagram-l2

]

</syntaxhighlight>

</lang>

=={{header|ReScript}}==

<~~lang~~ rescript>let n_sites = 60

<syntaxhighlight lang="rescript">let n_sites = 60

let size_x = 640

Line 2,578:

gen_map(site, rgb)

}

</syntaxhighlight>

</lang>

=={{header|Ring}}==

<~~lang~~ ring>

# Project : Voronoi diagram

Line 2,703:

return number(str)

</syntaxhighlight>

</lang>

Output image:

Line 2,711:

Uses [[Raster graphics operations/Ruby]]

[[File:voronoi_rb.png|thumb|right|Sample output from Ruby program]]

<~~lang~~ ruby># frozen_string_literal: true

<syntaxhighlight lang="ruby"># frozen_string_literal: true

require_relative 'raster_graphics'

Line 2,749:

end

pixmap.save_as_png('voronoi_rb.png')</~~lang~~>

pixmap.save_as_png('voronoi_rb.png')</syntaxhighlight>

JRubyArt is a port of processing to ruby

<~~lang~~ ruby># frozen_string_literal: true

<syntaxhighlight lang="ruby"># frozen_string_literal: true

Tile = Struct.new(:x, :y, :color) do

Line 2,798:

</syntaxhighlight>

</lang>

=={{header|Run BASIC}}==

<~~lang~~ runbasic>graphic #g, 400,400

<syntaxhighlight lang="runbasic">graphic #g, 400,400

#g flush()

spots = 100

Line 2,875:

end if

next y

end function</~~lang~~>

end function</syntaxhighlight>

=={{header|Rust}}==

Line 2,883:

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/

<~~lang~~ ~~Rust~~>extern crate piston;

<syntaxhighlight lang="rust">extern crate piston;

extern crate opengl_graphics;

extern crate graphics;

Line 3,063:

);

}

</syntaxhighlight>

</lang>

=={{header|Scala}}==

Line 3,069:

<~~lang~~ ~~Scala~~>import java.awt.geom.Ellipse2D

<syntaxhighlight lang="scala">import java.awt.geom.Ellipse2D

import java.awt.image.BufferedImage

import java.awt.{Color, Graphics, Graphics2D}

Line 3,110:

}

}</~~lang~~>

}</syntaxhighlight>

=={{header|Seed7}}==

[[file:Seed7Voronoi.png|thumb|right]]

<~~lang~~ seed7>$ include "seed7_05.s7i";

<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";

include "draw.s7i";

include "keybd.s7i";

Line 3,165:

KEYBOARD := GRAPH_KEYBOARD;

readln(KEYBOARD);

end func;</~~lang~~>

end func;</syntaxhighlight>

Original source: [http://seed7.sourceforge.net/algorith/graphic.htm#voronoi]

Line 3,171:

=={{header|Sidef}}==

<~~lang~~ ruby>require('Imager')

<syntaxhighlight lang="ruby">require('Imager')

func generate_voronoi_diagram(width, height, num_cells) {

Line 3,193:

var img = generate_voronoi_diagram(500, 500, 25)

img.write(file => 'VoronoiDiagram.png')</~~lang~~>

img.write(file => 'VoronoiDiagram.png')</syntaxhighlight>

Output image: [https://github.com/trizen/rc/blob/master/img/voronoi-diagram-sidef.png Voronoi diagram]

=={{header|Tcl}}==

<~~lang~~ tcl>package require Tk

<syntaxhighlight lang="tcl">package require Tk

proc r to {expr {int(rand()*$to)}}; # Simple helper

Line 3,232:

# To display while generating, uncomment this line and the other one so commented

#update

voronoi demo 60</~~lang~~>

voronoi demo 60</syntaxhighlight>

=={{header|Wren}}==

<~~lang~~ ecmascript>import "graphics" for Canvas, Color

<syntaxhighlight lang="ecmascript">import "graphics" for Canvas, Color

import "dome" for Window

import "random" for Random

Line 3,280:

}

}</~~lang~~>

}</syntaxhighlight>

=={{header|XPL0}}==

[[File:VoronoiXPL0.gif|right]]

<~~lang~~ ~~XPL0~~>include c:\cxpl\codes; \intrinsic 'code' declarations

<syntaxhighlight lang="xpl0">include c:\cxpl\codes; \intrinsic 'code' declarations

def N = 15; \number of sites

Line 3,305:

I:= ChIn(1); \wait for keystroke

SetVid($03); \restore normal text screen

]</~~lang~~>

]</syntaxhighlight>

=={{header|Yabasic}}==

clear screen

Line 3,385:

next y

return check

end sub</~~lang~~>

end sub</syntaxhighlight>

<~~lang~~ ~~Yabasic~~>width = 500 : height = 500

<syntaxhighlight lang="yabasic">width = 500 : height = 500

open window width, height

Line 3,420:

end sub

generate_voronoi_diagram(width, height, 25)</~~lang~~>

generate_voronoi_diagram(width, height, 25)</syntaxhighlight>

=={{header|zkl}}==

Line 3,426:

[[File:VoronoiDiagram.zkl.jpg|250px|thumb|right]]

<~~lang~~ zkl>fcn generate_voronoi_diagram(width,height,num_cells){

<syntaxhighlight lang="zkl">fcn generate_voronoi_diagram(width,height,num_cells){

image,imgx,imgy:=PPM(width,height),width,height;

nx:=num_cells.pump(List,(0).random.fp(imgx));

Line 3,444:

}

image

}</~~lang~~>

}</syntaxhighlight>

<~~lang~~ zkl>generate_voronoi_diagram(500,500,25).write(File("VoronoiDiagram.ppm","wb"));</~~lang~~>

<syntaxhighlight lang="zkl">generate_voronoi_diagram(500,500,25).write(File("VoronoiDiagram.ppm","wb"));</syntaxhighlight>