Code archives/Algorithms/Point in Triangle

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

Download source code

Point in Triangle by Rob Farley
(Posted 20 years ago)
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.
Open in online IDE
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
(Posted 20 years ago)
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
(Posted 20 years ago)
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