Delaunay triangulation

Santiago · May 02, 2023, 23:47:23

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.

Code Select

; trying to solve the Delaunay sistem to have a surface of triangles from a line of points.




Graphics 1800,1000,0,2
SetFont (LoadFont("Blitz",20))

Global c_edges
Global c_points
Global c_triangles

While 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
	
	
	
Wend


End

; triangles, 

Type triangle
	
	Field id
	Field p_id[3]
	
	Field x#[3]
	Field y#[3]
	
	Field cx#
	Field cy#
	Field radius#
	
	
End Type

Function 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

;edges

Type edge
	
	Field id
	Field x#[2]
	Field y#[2]
	
	Field cx#
	Field cy#
	
	Field valid
	
End Type

Function 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 vertex

Type point
	
	Field id
	Field x#
	Field y#
	
End Type

Function 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 Function


Function 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

SyntaxBomb - Indie Coders

Delaunay triangulation

Santiago