## Delaunay triangulation

Started by Santiago, May 02, 2023, 23:47:23

#### Santiago

Hi, I decided to do the Delaunay triangulation in Blitz3D.

I share what I am doing, at the moment incomplete, but I am advancing step by step.

maybe it will help someone too.

`; trying to solve the Delaunay sistem to have a surface of triangles from a line of points.Graphics 1800,1000,0,2SetFont (LoadFont("Blitz",20))Global c_edgesGlobal c_pointsGlobal c_trianglesWhile Not KeyHit(1) mx = MouseX() my = MouseY() mhl = MouseHit(1) mhr = MouseHit(2) If mhl = 1 Then  create_point(mx,my) Color 0,0,0 Rect 0,0,100,100,1 c_edges = update_edges() c_points = draw_points() update_triangles() Color 255,255,255 Text 10,10,c_points + " Points" Text 10,30,c_edges + " Edges" Text 10,50,c_triangles + " Triangles" Flip WendEnd; triangles, Type triangle Field id Field p_id[3] Field x#[3] Field y#[3] Field cx# Field cy# Field radius# End TypeFunction update_triangles() c_triangles = 0 For t.triangle = Each triangle t\radius = Sqr((t\x[1]-t\cx)*(t\x[1]-t\cx) + (t\y[1]-t\cy)*(t\y[1]-t\cy)) c_triangles = c_triangles + 1 Color 255,255,0 a=1 Rect t\cx-a,t\cy-a,a*2+1,a*2+1,1 Text t\cx+5,t\cy,t\id + " r:" + t\radius Color 150,100,0 r#= t\radius# Oval t\cx-r,t\cy-r,r*2,r*2,0 Next End Function;edgesType edge Field id Field x#[2] Field y#[2] Field cx# Field cy# Field valid End TypeFunction update_edges() c_edges = 0 For e.edge = Each edge c_edges = c_edges + 1 Color 0,0,150 x1# = e\x[1] y1# = e\y[1] x2# = e\x[2] y2# = e\y[2] For d.edge = Each edge If d\id <> e\id Then x3#= d\x[1] y3#= d\y[1] x4#= d\x[2] y4#= d\y[2] End If Next Line x1,y1,x2,y2 Color 100,100,255 a=2 Rect e\cx-a,e\cy-a,a*2+1,a*2+1,1 ;Color 255,255,255 Text e\cx+5,e\cy,e\id Next Return c_edges End Function;points, future vertexType point Field id Field x# Field y# End TypeFunction draw_points() c_points = 0 For p.point = Each point c_points = c_points + 1 Color 255,255,255 a=3 Rect p\x-a,p\y-a,a*2+1,a*2+1,1 Text p\x+5,p\y,p\id Next Return c_points End FunctionFunction create_point(x,y) c_points = c_points + 1 p.point = New point p\id = c_points p\x = x p\y = y For d.point = Each point ;si no es el mismo If p\x <> d\x And p\y <> d\y And p\x <> 0 And p\y <> 0 Then x1# = p\x y1# = p\y x2# = d\x y2# = d\y cx# = (x1 + x2) /2 cy# = (y1 + y2) /2 e.edge = New edge c_edges = c_edges + 1 e\id = c_edges e\cx# = cx# e\cy# = cy# e\x[1] = x1 e\y[1] = y1 e\x[2] = x2 e\y[2] = y2 End If Next If c_points > 2 Then For p2.point = Each point For p3.point = Each point ;if is not the same point 1 2 and 3.... If p\id <> p2\id And p\id <>  p3\id And p2\id <> p3\id Then If p2\id > p3\id And p\id > p2\id Then t.triangle = New triangle c_triangles = c_triangles + 1 t\id = c_triangles t\p_id[1] = p\id t\p_id[2] = p2\id t\p_id[3] = p3\id ;t\cx = (p\x + p2\x + p3\x) / 3 ;t\cy = (p\y + p2\y + p3\y) / 3 t\x[1] = p\x t\y[1] = p\y t\x[2] = p2\x t\y[2] = p2\y t\x[3] = p3\x t\y[3] = p3\y x1# = p\x y1# = p\y x2# = p2\x y2# = p2\y x3# = p3\x y3# = p3\y xc# = ( (x1^2 + y1^2) * (y2 - y3) + (x2^2 + y2^2) * (y3 - y1) + (x3^2 + y3^2) * (y1 - y2) ) / (2 * (x1 * (y2 - y3) - y1 * (x2 - x3) + x2 * y3 - y2 * x3)) yc# = ( (x1^2 + y1^2) * (x3 - x2) + (x2^2 + y2^2) * (x1 - x3) + (x3^2 + y3^2) * (x2 - x1) ) / (2 * (x1 * (y2 - y3) - y1 * (x2 - x3) + x2 * y3 - y2 * x3)) t\cx# = xc# t\cy# = yc# End If End If Next Next End If End Function`