## Voronoi diagrams

angros47
Posts: 1539
Joined: Jun 21, 2005 19:04

### Voronoi diagrams

Do you know what a Voronoi diagram is?
http://en.wikipedia.org/wiki/Voronoi_diagram

Basically, a number of points are chosen (1000, in my example, but you can change it at your will), and every pixel will get the color of the closest point.

The resulting effect may resemble a crystal, or a scaly skin, and could be useful for texture generation.

Code: Select all

const MaxAreas=1000
randomize timer

type voronoi
x as integer
y as integer
c as integer
end type

Screenres 800,600,32

dim areas(maxareas) as voronoi

for i as integer=0 to maxareas
areas(i).x=rnd(1)*800
areas(i).y=rnd(1)*600
areas(i).c=rgb(rnd(1)*256,rnd(1)*256,rnd(1)*256)
next

dim as unsigned integer ptr target=screenptr

screenlock

for y as integer=1 to 600
for x as integer=1 to 800
dim as integer dist=800*600,d,dx,dy
for i as integer=0 to maxareas
dx=areas(i).x-x
dy=areas(i).y-y
d=dx*dx+dy*dy
if d<dist then dist=d:*target=areas(i).c
next
target+=1

next

next

screenunlock

sleep

relsoft
Posts: 1767
Joined: May 27, 2005 10:34
Location: Philippines
Contact:
Cool!!!
These textures is made using that algo:

http://blackpawn.com/texts/cellular/default.html
BasicCoder2
Posts: 3404
Joined: Jan 01, 2009 7:03
I tried it using an image.

I haven't worked out how to space the sample points as a grid.

One thing that interests me is how to segment an image into a few colors.

Code: Select all

Const MaxAreas=6000
Randomize Timer

Type voronoi
x As Integer
y As Integer
c As Integer
End Type

Screenres 640,480,32

Dim areas(maxareas) As voronoi

Dim As Unsigned Integer Ptr target=screenptr

For i As Integer=0 To maxareas
areas(i).x=Rnd(1)*640
areas(i).y=Rnd(1)*480
areas(i).c=point(areas(i).x,areas(i).y)
Next

screenlock

For y As Integer=1 To 480
For x As Integer=1 To 640
Dim As Integer dist=640*480,d,dx,dy
For i As Integer=0 To maxareas
dx=areas(i).x-x
dy=areas(i).y-y
d=dx*dx+dy*dy
If d<dist Then dist=d:*target=areas(i).c
Next
target+=1
Next
Next

screenunlock

Sleep
j_milton
Posts: 458
Joined: Feb 11, 2010 17:35

### Re: Voronoi diagrams

angros47 wrote:Do you know what a Voronoi diagram is?
http://en.wikipedia.org/wiki/Voronoi_diagram

Basically, a number of points are chosen (1000, in my example, but you can change it at your will), and every pixel will get the color of the closest point.

The resulting effect may resemble a crystal, or a scaly skin, and could be useful for texture generation.

Thanks for reminding me of this. I had actually encountered them in University Computer Sci., but that was.... years ago.

I am now using it to design random room shapes in the "dungeon" of a "Roguelike" game I am working on.

Interesting aside: This algorithm has saved hundreds,maybe thousands of lives. It was used (with pen and paper, not a computer) by John Snow in 1854 to identify cholera contaminated public water taps in London England that were the cause of an epidemic of fatal illness
kiyotewolf
Posts: 1009
Joined: Oct 11, 2008 7:42
Location: ABQ, NM
Contact:
I'm so going to use this.

This is really really neat.

I've only seen this feature on such programs as Photoshop.

~Kiyote!

Can I use this as a filter in my paint program (that I'm writing). ?
Pritchard
Posts: 5492
Joined: Sep 12, 2005 20:06
Location: Ohio, USA
Hey, these are really cool.

I was laying down looking at the clouds today, and I thought to myself, "Couldn't a Veroni diagram-based algorithm simulate this perfectly?"

Anyone want to take the challenge?
angros47
Posts: 1539
Joined: Jun 21, 2005 19:04
You can simulate a cloud better by using a Perlin noise algorithm:

Code: Select all

const iter=20
const v=8

function col (x as integer,y as integer) as unsigned integer
return point(x,y) and 255
end function

screenres 800,600,32

for i as integer=0 to 5
circle (rnd(1)*800,rnd(1)*600),rnd(1)*300,,,,rnd(1)*2.0,F
next

dim size as integer=iter+1
dim c as unsigned integer

for i as integer=1 to iter
for x as integer =0 to 800 step size
for y as integer =0 to 600 step size
c=(col(x,y)+col(x+size,y)+col(x,y)+col(x+size,y+size))/4
if c>v then c=c-rnd(1)*v
if c<256-v then c=c+rnd(1)*v
line (x,y)-(x+size-1,y+size-1),rgb(c,c,c),bf
next
next
size=size-1
sleep
next
sleep
duke4e
Posts: 717
Joined: Dec 04, 2005 0:16
Location: Varazdin, Croatia, Europe
Contact:
I don't think this is Perlin noise.