### Author Topic: Voronoi  (Read 509 times)

0 Members and 1 Guest are viewing this topic.

#### spathi

• C= 64
• Posts: 68
• Karma: 5
##### Voronoi
« on: July 10, 2012 »

Voronoi diagrams are apparently a rather bonecrushing algorithm.  I forget the O notation but the best possible is pretty slow.  Adding recursion sped it up hugely.  I'm doing this for a reason but I thought it was interesting enough to share.

It seems like you could pretty easily cull the tree by running paths between different regions, bailing out on the second region, and building up a list, per centroid, of neighbors.  Probably the smart people already thought of this.

If you watch you'll see some very strange artifacts around some of the edges.  I'm not quite sure why they are in there, probably some sort of precision error.

Code: [Select]
`' VORONOI CREATOR PRO' BROKEN BY SPATHI MCZOQFOT AND THE WAREZIRD' GREETS TO SUPERPIRATES 612Global WIDTH=1024Global HEIGHT=768Graphics WIDTH,HEIGHTGlobal mode# = 0Type voronoipoint Field x#,y# Field r#,g#,b# Field id# ' bounding box for region Field ux#,uy#,lx#,ly# Method randomize() x = Rand(WIDTH) y = Rand(HEIGHT) ux = x uy = y lx = x ly = y r=Rand(255) g=Rand(255) b=Rand(255) End MethodEnd TypeGlobal vpointlist:TList = New TListFor Local i# = 1 To 32 Local tempvpoint:voronoipoint = New voronoipoint tempvpoint.randomize() tempvpoint.id = i vpointlist.addlast(tempvpoint)NextFunction closestvpoint:voronoipoint(x#, y#)  ' returns closest voronoi point for x and y Local closestpoint:voronoipoint = New voronoipoint Local closestdistance:Double = 10000 Local nextclosestdistance:Double = 10000 Local p:voronoipoint = New voronoipoint For p = EachIn vpointlist Local thisdistance:Float = Distance(x, y, p.x,p.y) If thisdistance < closestdistance nextclosestdistance = closestdistance closestdistance = thisdistance closestpoint = p EndIf Next Return closestpointEnd FunctionFunction thesame(a#,b#,c#,d#) If a=b And a=c And a=d Return True Else Return False EndIfEnd Function Global p1:voronoipoint = New voronoipoint Global p2:voronoipoint = New voronoipoint Global p3:voronoipoint = New voronoipoint Global p4:voronoipoint = New voronoipoint Global tempvor:voronoipoint = New voronoipoint 'Function voronoirecursive(ax, ay, bx, by, cx, cy, dx, dy)Function voronoirecursive(ux, uy, lx, ly, recursions#)If recursions < 5 And KeyDown(KEY_ESCAPE) recursions = 1000If recursions < 12 ' check all four points clockwise p1=closestvpoint(ux,uy) p2=closestvpoint(lx,uy) p3=closestvpoint(lx,ly) p4=closestvpoint(ux,ly) If thesame(p1.id, p2.id, p3.id, p4.id) Local midpointx# = ux + ((lx-ux)/2) Local midpointy# = uy + ((ly-uy)/2) tempvor=closestvpoint(midpointx,midpointy) SetColor p1.r,p1.g,p1.b DrawRect ux, uy, lx-ux, ly-uy SetColor 0,0,0 ' Increase extents of bounding box If ux < p1.ux p1.ux = ux If lx > p1.lx p1.lx = lx If uy < p1.uy p1.uy = uy If ly > p1.ly p1.ly = ly If mode = 2 Or mode = 3 drawhollowrect(ux,uy,lx,ly) If recursions < 7 Flip Return True Else midpointx# = ux + ((lx-ux)/2) midpointy# = uy + ((ly-uy)/2) voronoirecursive(ux, uy, midpointx, midpointy, recursions+1) voronoirecursive(midpointx, midpointy, lx, ly, recursions+1) voronoirecursive(ux, midpointy, midpointx, ly, recursions+1) voronoirecursive(midpointx, uy, lx, midpointy, recursions+1) EndIfEndIf  ' bailing out because recursions too highEnd FunctionFunction lefthalf:Object(data:Object) voronoirecursive(0,0,width/2,height,1)End FunctionFunction righthalf:Object(data:Object) voronoirecursive(width/2,0,width,height,1)End FunctionWhile Not KeyDown(KEY_ESCAPE)Local p:voronoipoint = New voronoipoint Cls voronoirecursive(0,0,WIDTH,HEIGHT,1) 'Local thread1:TThread=CreateThread(lefthalf,"") 'Local thread2:TThread=CreateThread(righthalf,"") Flip 'Local tv:voronoipoint = New voronoipoint 'For tv = EachIn vpointlist 'tv.randomize() 'Next Local tv:voronoipoint = New voronoipoint For tv = EachIn vpointlist SetColor 255,255,255 'drawhollowrect(tv.ux, tv.uy, tv.lx, tv.ly) Next Local ticks = 0 Repeat For tv = EachIn vpointlist SetColor 255,255,255 If mode = 1 Or mode = 3 drawhollowrect(tv.ux, tv.uy, tv.lx, tv.ly) If mode = 5 Or mode = 3 DrawRect tv.x-2,tv.y-2, 5,5 Next Flip ticks = ticks + 1 Until MouseDown(1) Or ticks > 200 For tv = EachIn vpointlist tv.randomize() Next mode = mode + 1 If mode > 5 mode = 0 Wend'get 4 points' if all the same, color according to closest and bail.' else subdivideFunction drawhollowrect(ux, uy, lx, ly) DrawLine ux, uy, lx, uy DrawLine lx, uy, lx, ly DrawLine lx, ly, ux, ly DrawLine ux, ly, ux, uyEnd FunctionFunction Distance(Point1X,Point1Y,Point2X,Point2Y)  'calculate the x/y distances  dX = Point1X - Point2X  dY = Point1Y - Point2Y  'calculate exact distance  'Sqr() always returns an absolute value  Return Sqr( (dx^2) + (dy^2) )End Function`
« Last Edit: July 11, 2012 by spathi »

#### Jim

• Founder Member
• Posts: 5257
• Karma: 394
##### Re: Voronoi
« Reply #1 on: July 10, 2012 »
K+ for code!
Challenge Trophies Won:

#### Shockwave

• good/evil
• Founder Member
• Posts: 17297
• Karma: 489
• evil/good
##### Re: Voronoi
« Reply #2 on: July 10, 2012 »
Thanks for sharing the code Spathi
Shockwave ^ Codigos
Challenge Trophies Won:

#### spathi

• C= 64
• Posts: 68
• Karma: 5
##### Re: Voronoi
« Reply #3 on: July 11, 2012 »
Can you think of any way to make it faster?

Originally I was walking the pixels brute force, but that was extremely slow-- [centroid number] distance checks for each pixel.  Adding the recursion made it far faster and it's now seemingly just as fast for huge images.

Perhaps I can use binning and check only the few closest centroids to the bin that a pixel is in.  That should decrease the number of distance checks gigantically.

#### spathi

• C= 64
• Posts: 68
• Karma: 5
##### Re: Voronoi
« Reply #4 on: July 11, 2012 »
Turned it into a screen saver / high toy.  (Doesn't actually screensave, my screensaver module broke a number of Blitz revisions ago...)

An exe is here:

https://www.dropbox.com/s/j71d12e7h43a3wc/voronoi.exe
« Last Edit: July 11, 2012 by spathi »