Tri Tri Intersection ?

Blitz3D Forums/Blitz3D Programming/Tri Tri Intersection ?

Is there some sourcecode for a (2D) Triangle to Triangle intersection test?

Or what is in your opinion the best way to align 2 triangles onscreen with minimal space requirement?

haha, probably I will simply create two masked images and use ImagesCollide <:o)

I don't know any tri tri intersection code, but do you mean side-by-side alignment ? I wrote a routine a while back that could do something like that. If you give it the coords for two points, and the length of the three splines, it calculates where the 3rd point should be. There are two possibilities, so I used a forth point as a reference:
;---------------------------------------------------------------------------------------------------
;												  C2	
;                                                 /\
;                                               /    \
;											  /        \
;									        A __________ B
;									   	      \        /
;									            \    /
;									              \/
;									               C1         . D
;
;							  this program calculates (X,Y) of point C1/C2,
; 							   given are the coordinates of point A, B and D.
;							 also known are the distances between each point.
;---------------------------------------------------------------------------------------------------


	;declare float variables
	Local	mx#, my#
	Local 	ax#, ay#, bx#, by#, dx#, dy#
	Local	cx1#, cy1#, cx2#, cy2#
	Local 	oax#, oay#, obx#, oby#, ocx#, ocy#
	Local	organgle#, distance#
	Local	h1#, d1#, h2#, d2#, h3#, d3#
	Local 	AB#, BC#, AC#, CD#
	Local	C1#, C2#

;---------------------------------------------------------------------------------------------------
;  											   Main Program
;---------------------------------------------------------------------------------------------------

	;setup
	Graphics 320, 240
	SetBuffer BackBuffer()
	
	SeedRnd MilliSecs()

	;main loop
	Repeat
	
		Cls
		Locate 0, 0
		
		;-----
		;INPUT
		;-----
		
		;generate three points
		ax = Rand(250) + 35
		ay = Rand(80) + 120
		bx = Rand(250) + 35
		by = Rand(80) + 120
		cx = Rand(250) + 35
		cy = Rand(80) + 120

		;this point is used to determine which 
		;of the two possible points is valid by checking the distance
		dx = Rand(250) + 35
		dy = Rand(80) + 120
				
		;calculate their distances
		AC = VDist(ax, ay, cx, cy)
		AB = VDist(ax, ay, bx, by)
		BC = VDist(bx, by, cx, cy)
		
		CD = VDist(cx, cy, dx, dy)
		
		;-------
		;PROCESS
		;-------

		;-----------------------------------------------------		
		;goal - (re)calculate the position of point C (cx, cy)
		;-----------------------------------------------------
		
		;store the position of point A, for translate purposes
		oax = ax
		oay = ay
		;and point B and C as well for drawing purposes
		obx = bx
		oby = by
		ocx = cx
		ocy = cy
								
		;calculate angle and distance from A to B
		organgle = (450 - ATan2(bx - ax, by - ay)) Mod 360
		distance = vdist(ax, ay, bx, by)
				
		;set new coordinates A and B (0,0)-(AB,0)
		;because the formula works only with points A and B aligned on the X-axis. (y=0)
		ax = 0
		ay = 0
		bx = distance
		by = 0
		
		;----------------------------------------------------------------------------------
		; this is the main formula
		; it calculates (x,y) for 
		;  the third point
		;there is two possibilities: C1 and C2
		;----------------------------------------------------------------------------------
		cx1 = ((AB ^ 2) - (BC ^ 2) + (AC ^ 2)) / (2 * AB)
		cy1 = Sqr(((4 * AB ^ 2 * AC ^ 2) - (AB ^ 2 - BC ^ 2 + AC ^ 2) ^ 2) / (4 * AB ^ 2))
		cx2 =  cx1
		cy2 = -cy1
		;-----------------------------------------------------------------------------------
		;  using the 4th point (D) we could determine which option is valid
		;-----------------------------------------------------------------------------------
		
		Color 0, 0, 255
		Rect 0, 0, 320, 40
		
		Color 255, 255, 255		

		;;check distances(lengths)
		Print "AB=" + vdist(ax, ay, bx,  by)  + " (" + AB + ")"
		Print "BC=" + vdist(bx, by, cx1, cy1) + " (" + BC + ")"
		Print "AC=" + vdist(ax, ay, cx1, cy1) + " (" + AC + ")"
		
		;calculate midpoint 1
		mx1 = (ax + bx + cx1) / 3
		my1 = (ay + by + cy1) / 3	
		
		;calculate angles (h1,h2,h3,h4) and distances (d1,d2,d3,d4)
		;point A
		h1 = 450 - ATan2((ax  - mx1), (ay  - my1))
		d1 = vdist(ax, ay,  mx1, my1)
		;point B
		h2 = 450 - ATan2((bx  - mx1), (by  - my1))
		d2 = vdist(bx, by,  mx1, my1)
		;point C1
		h3 = 450 - ATan2((cx1 - mx1), (cy1 - my1))
		d3 = vdist(cx1, cy1,  mx1, my1)
		;point C2
		h4 = 450 - ATan2((cx2 - mx1), (cy2 - my1))
		d4 = vdist(cx2, cy2, mx1, my1)

		;AB are rotated back into their original position
		;C1 and C2 rotate along
		ax  = Cos(h1 + organgle) * d1
		ay  = Sin(h1 + organgle) * d1
		bx  = Cos(h2 + organgle) * d2
		by  = Sin(h2 + organgle) * d2
		cx1 = Cos(h3 + organgle) * d3
		cy1 = Sin(h3 + organgle) * d3
		cx2 = Cos(h4 + organgle) * d4
		cy2 = Sin(h4 + organgle) * d4
		
		;translate points so that point A is at it's original position
		cx2 = cx2 - ax + oax
		cy2 = cy2 - ay + oay
		cx1 = cx1 - ax + oax
		cy1 = cy1 - ay + oay
		bx  = bx  - ax + oax
		by  = by  - ay + oay
		ax  = ax  - ax + oax
		ay  = ay  - ay + oay
		
		;determine what C is valid
		If Abs(VDist(cx1, cy1, dx, dy) - CD) < Abs(VDist(cx2, cy2, dx, dy) - CD) Then
		
			cx = cx1
			cy = cy1
		
		Else
		
			cx = cx2
			cy = cy2
			
		End If
		
		;------
		;OUTPUT
		;------

		Viewport 0, 40, 320, 200
		
		Color 0, 64, 0
		;draw original points to the screen		
		Oval oax - 3, oay - 3, 7, 7, False
		Oval obx - 3, oby - 3, 7, 7, False
		Oval ocx - 3, ocy - 3, 7, 7, False

		;draw reference point D
		Oval dx - 2, dy - 2, 5, 5, False

		;draw triangle		
		Color 64, 64, 0					
		Line ax, ay, bx, by
		Line bx, by, cx, cy
		Line cx, cy, ax, ay
				
		;text labels
		Color 180, 180, 180
		Text ax, ay, "A", True, False
		Text bx, by, "B", True, False
		Text dx, dy, "D", True, False	
		Color 255, 0, 0
		Text cx, cy, "C", True, False
				
		Viewport 0, 0, GraphicsWidth(), GraphicsHeight()
						
		Flip
		
		;wait for a key
		now = MilliSecs()
		Repeat
		   Delay 50
		Until (MilliSecs() - now > 750) Or KeyDown(1) Or KeyDown(205)
		
	Until KeyHit(1)
	

End

;---------------------------------------------------------------------------------------------------
;												 END
;---------------------------------------------------------------------------------------------------





;----------------------------------------------------------------------------------------------------
;												VDist()
;----------------------------------------------------------------------------------------------------
;return distance between two points
Function VDist#(x1#, y1#, x2#, y2#)
	Return Sqr((x2 - x1) ^ 2 + (y2 - y1) ^ 2)
End Function


Thanks, I´ll check this out.

Can't you just do 3 ray-to-triangle2 tests (one ray for each triangle1 edge)? Move triangle1 away from triangle2 by the amount of intersection?

Maybe yes, but I guess this wouldn't recognize an enclosed triangle?

Or maybe test if each corner is inside the triangle (both ways).

I think Beaker's solution sounds pretty straight forward... especially if you had a function to detect if a point was inside a triangle...

Hmm... if only

Hmmmmmmmmmmm...

wait a minute - what if they are intersecting, but there's no vertex inside the other tri? Like when two lines are crossing two lines of the 2nd tri.

Well, Beakers first suggestion with 3* ray vs tri sounds good. Then I still have to ckeck if a tri is enclosed (all 3 vertices within Tri 1), by using Robs code. Wrapped in a neat function this may be pretty good.