Voronoi diagram

[matthew]

I originally wrote this some years ago but never got around to posting it on the forum. It's based on the routines that you can find on the Rosetta Code site here. You can find out more about the mathematics involved on the appropriate Wikipedia page here. It's a bit slow at the moment but it can be probably be optimised like a lot of the other versions on the Rosetta Code site are.

Randomize(PerformanceCounter() )

const p = 3, sites = 25
dim screenWidth = WindowWidth(), screenHeight = WindowHeight()
dim townX(sites), townY(sites), colR(sites), colG(sites), colB(sites)
dim i, x, y, n

sub Create2DScreen()

    glMatrixMode(GL_PROJECTION)
    glLoadIdentity()
    glOrtho(0.0, screenWidth, screenHeight, 0.0, 0.0, 1.0)
    glDisabLe(GL_DEPTH_TEST)
    glDrawBuffer(GL_FRONT)
	glMatrixmode(GL_MODELVIEW)
	glLoadIdentity()
	glTranslatef(0.375, 0.375, 0.0)
    glClearColor(0.0, 0.0, 0.0, 0.0)
    glClear(GL_COLOR_BUFFER_BIT)

endsub

function VoronoiDistance(x1, x2, y1, y2)

    dim distance#
    
    ' Euclidian
    distance# = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
    ' Manhattan
    ' distance# = abs(x1 - x2) + abs(y1 - y2)
    ' Minkowski
	' distance# = pow( (pow(abs(x1 - x2), p) + pow(abs(y1 - y2), p)), (1 / p) )
    
    return distance#
    
end function


sub DrawVoronoi()

    for i = 0 to sites
        townX(i) = rnd() % screenWidth
        townY(i) = rnd() % screenHeight
        colR(i) = rnd() % 255
        colG(i) = rnd() % 255
        colB(i) = rnd() % 255
    next
    
    for x = 0 to screenWidth
        for y = 0 to screenHeight
            n = 0
            for i = 0 to sites
                if (VoronoiDistance(townX(i), x, townY(i), y) < VoronoiDistance(townX(n), x, townY(n), y)) then
                    n = i
                endif
            next
            glBegin(GL_POINTS)
                glColor3ub(colR(n), colG(n), colB(n))
                glVertex2i(x, y)
            glEnd()
        next
		glFlush()
    next

    glPointSize(5)

    for i = 0 to sites
        glBegin(GL_POINTS)
            glColor3ub(0, 0, 0)
            glVertex2i(townX(i), townY(i))
        glEnd()
    next
    
	glFlush()
    beep()

endsub

Create2DScreen()
DrawVoronoi()