Codesnippets > Math

Delaunay Triangulisation

(1/1)

Kitty Hello:
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.

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

and of course, an undo function  :good:

ok I will scram away quickly ;)

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

--- End code ---

new coding for MAIN.GBAS

--- Code: (glbasic) ---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

--- End code ---