Author Topic: Delaunay Triangulisation  (Read 2842 times)

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10656
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Delaunay Triangulisation
« on: 2008-Aug-08 »
http://www.glbasic.com/showroom.php?game=Delaunay
Might be useful for some project. You insert a set of points and get triangles read to use with POLYVECTOR or X_OBJADDVERTEX.

Offline Quentin

  • Prof. Inline
  • *****
  • Posts: 899
    • View Profile
Re: Delaunay Triangulisation
« Reply #1 on: 2008-Aug-08 »
looks very useful, thanks

perhaps a "snap-to-grid" function is a good idea with free defineable grid size and grid lines shown on the screen

[edit]
and of course, an undo function  :good:

ok I will scram away quickly ;)

[edit]
snap to grid is included now in main.gbas.
At description of command DIMDEL there is a nice example for an undo function when placing stars on the screen. I thougt I could use this with some small modifications to undo the nearest point in your program. I works so far and I hope its useful.
Sorry for bungling your code Gernot  :whistle:

new functions in DELAUNY.GBAS

Code: GLBasic [Select]
// ------------------------------------------------------------- //
// ---  DTRINEAREST  ---
// ------------------------------------------------------------- //
FUNCTION DTriNearest: pts[] AS DTRI_PT, x, y

        LOCAL best, bestdist, dist, i,dx,dy
       
        best = -1
        FOR i = 0 TO BOUNDS(pts[], 0) - 1
                dx = x - pts[i].x
                dy = y - pts[i].y
                dist = SQR(dx*dx + dy*dy)
                IF i = 0 OR dist < bestdist
                        bestdist = dist
                        best = i
                ENDIF
        NEXT
        RETURN best

ENDFUNCTION // DTRINEAREST


// ------------------------------------------------------------- //
// ---  DTRIDELETE  ---
// ------------------------------------------------------------- //
FUNCTION DTriDelete: pts[] AS DTRI_PT, x, y
        LOCAL i
        i = DTriNearest(pts[], x, y)
        IF i >= 0 THEN DIMDEL pts[], i
ENDFUNCTION // DTRIDELETE
 


new coding for MAIN.GBAS

Code: GLBasic [Select]
LOCAL pts[] AS DTRI_PT
LOCAL tri[] AS DTRI_TRI
LOCAL ord[]

LOCAL gridsize = 20
LOCAL sx, sy, i
LOCAL b2_pressed

GETSCREENSIZE sx, sy

WHILE TRUE
        MOUSESTATE mx, my, b1, b2
        PRINT "X" , mx, my

        IF b1
                LOCAL p AS DTRI_PT
                p.x = INTEGER(mx/gridsize) * gridsize + gridsize * .5
                p.y = INTEGER(my/gridsize) * gridsize + gridsize * .5
                DIMPUSH pts[], p
                DTriConvexHull(pts[], ord[])
                DTriDoDelaunay(pts[], ord[], tri[])

                WHILE MOUSEAXIS(3); SLEEP 5; WEND
        ENDIF
       
        // undo with right mouse button
        IF b2
                IF b2_pressed = FALSE
                        b2_pressed = TRUE
                        DTriDelete(pts[], mx, my)
                        DTriConvexHull(pts[], ord[])
                        DTriDoDelaunay(pts[], ord[], tri[])
                ENDIF
        ELSE
                b2_pressed = FALSE
        ENDIF

        // draw the grid
        FOR i = gridsize TO sx STEP gridsize
                DRAWLINE i, 0, i, sy, RGB(96, 96, 96)
        NEXT
        FOR i = gridsize TO sy STEP gridsize
                DRAWLINE 0, i, sx, i, RGB(96, 96, 96)
        NEXT

        // draw triangles
        LOCAL col = RGB(0,255,0)
        FOREACH t IN tri[]
                DRAWLINE pts[t.k1].x, pts[t.k1].y,  pts[t.k2].x, pts[t.k2].y, col
                DRAWLINE pts[t.k3].x, pts[t.k3].y,  pts[t.k2].x, pts[t.k2].y, col
                DRAWLINE pts[t.k1].x, pts[t.k1].y,  pts[t.k3].x, pts[t.k3].y, col
        NEXT
        // draw convex hull
        col = RGB(64,64,255)
        FOR i=0 TO LEN(ord[])-2
                DRAWLINE pts[ord[i]].x, pts[ord[i]].y,  pts[ord[i+1]].x, pts[ord[i+1]].y, col
        NEXT
        // draw nodes
        FOREACH p IN pts[]
                DRAWRECT p.x-4, p.y-4, 8,8,RGB(255,255,255)
        NEXT

        SHOWSCREEN
WEND
 
« Last Edit: 2008-Aug-08 by Quentin »