Point in Triangle

This code has been declared by its author to be Public Domain code.

Point in Triangle by Rob Farley

2007

Usage:

InTriangle(x0,y0,x1,y1,x2,y2,x3,y3)

(x0,y0) is the point you are checking

(x1,y1) (x2,y2) and (x3,y3) are the points of the triangle.

Returns True or False

You only need the function at the bottom, the stuff at the top is simply a demo.

Graphics 640,480,32,2
SeedRnd MilliSecs()

Repeat
Cls
	x1 = Rand(100,540)
	y1 = Rand(100,380)
	x2 = Rand(100,540)
	y2 = Rand(100,380)
	x3 = Rand(100,540)
	y3 = Rand(100,380)
	
	
	Color 255,0,0
	
	For x=0 To 639
	For y=0 To 479
		If intriangle (x,y,x1,y1,x2,y2,x3,y3) Then Plot x,y
	Next
	Next
	
	Color 255,255,255
	Line x1,y1,x2,y2
	Line x2,y2,x3,y3
	Line x3,y3,x1,y1
	
	WaitKey

Until KeyHit(1)


Function InTriangle(x0,y0,x1,y1,x2,y2,x3,y3)

	b0# =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
	b1# = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0 
	b2# = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
	b3# = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0 
	
	If b1>0 And b2>0 And b3>0 Then Return True Else Return False

End Function

Comments

Floyd

2007

Here's a small optimization. The function returns True only if several tests succeed. You can return False as soon as one of them fails.

Function InTriangle(x0,y0,x1,y1,x2,y2,x3,y3)

	b0# =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
	b1# = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0 
	If b1 <= 0 Then Return False
	
	b2# = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
	If b2 <= 0 Then Return False

	b3# = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0 
	If b3 <= 0 Then Return False
	
	Return True

End Function

Warpy

2007

Given that you only care about the sign of b1/b2/b3, couldn't you multiply by b0 instead of dividing? If we're being pedantic about optimization, it might be a teensy bit quicker, and less likely to give NaN.

Code Archives Forum