Algorithm to determine if a point is inside a triangle with mathematics (no hit test involved)

June 18, 2012 • Actionscript 3, Flash by Emanuele Feronato • 14 Comments

A couple of months ago I published an algorithm to determine if a point is inside a square with mathematics (no hit test involved).

Are you ready for some more maths? This time I am publishing an algorithm to determine if a point is inside a triangle.

Although checking if a point is inside “something” may seem just a programming exercise, during next days I will show you how many awesome things you can do with it.

The idea is simple. Given an ABC triangle, every side cuts the plane in two. We can say a point is inside a triangle when its position in all three planes is on the same side of the triangle, or when it’s not in any plane on the opposite side of the triangle.

Look at this picture:

We can say a point is inside the triangle when it’s outside of plane AB, outside plane BC and outside plane CA, or inside “rest of the world”-plane AB, inside “rest of the world”-plane BC and inside “rest of the world”-plane CA.

This is what we are going to do:

package {
	import flash.display.Sprite;
	import flash.geom.Point;
	import flash.events.Event;
	import flash.events.MouseEvent;
	public class Main extends Sprite {
		private var A:Point;
		private var B:Point;
		private var C:Point;
		var triangleCanvas:Sprite=new Sprite();
		public function Main() {
			triangleCanvas=new Sprite();
			addChild(triangleCanvas);
			drawTriangle(null);
			stage.addEventListener(MouseEvent.CLICK,drawTriangle);
			addEventListener(Event.ENTER_FRAME,update);
		}
		private function drawTriangle(e:MouseEvent):void {
			A=new Point(Math.random()*600+20,Math.random()*440+20);
			B=new Point(Math.random()*600+20,Math.random()*440+20);
			C=new Point(Math.random()*600+20,Math.random()*440+20);
		}
		private function update(e:Event):void {
			var mousePoint:Point=new Point(mouseX,mouseY);
			triangleCanvas.graphics.clear();
			if (isInsideTriangle(A,B,C,mousePoint)) {
				triangleCanvas.graphics.lineStyle(1,0xFF0000);
			}
			else {
				triangleCanvas.graphics.lineStyle(1,0x000000);
			}
			triangleCanvas.graphics.moveTo(A.x,A.y);
			triangleCanvas.graphics.lineTo(B.x,B.y);
			triangleCanvas.graphics.lineTo(C.x,C.y);
			triangleCanvas.graphics.lineTo(A.x,A.y);
		}
		private function isInsideTriangle(A:Point,B:Point,C:Point,P:Point):Boolean {
			var planeAB:Number = (A.x-P.x)*(B.y-P.y)-(B.x-P.x)*(A.y-P.y);
			var planeBC:Number = (B.x-P.x)*(C.y-P.y)-(C.x - P.x)*(B.y-P.y);
			var planeCA:Number = (C.x-P.x)*(A.y-P.y)-(A.x - P.x)*(C.y-P.y);
			return sign(planeAB)==sign(planeBC) && sign(planeBC)==sign(planeCA);
		}
		private function sign(n:Number):int {
			return Math.abs(n)/n;
		}
	}
}

package {

import flash.display.Sprite;

import flash.geom.Point;

import flash.events.Event;

import flash.events.MouseEvent;

public class Main extends Sprite {

private var A:Point;

private var B:Point;

private var C:Point;

var triangleCanvas:Sprite=new Sprite();

public function Main() {

triangleCanvas=new Sprite();

addChild(triangleCanvas);

drawTriangle(null);

stage.addEventListener(MouseEvent.CLICK,drawTriangle);

addEventListener(Event.ENTER_FRAME,update);

}

private function drawTriangle(e:MouseEvent):void {

A=new Point(Math.random()*600+20,Math.random()*440+20);

B=new Point(Math.random()*600+20,Math.random()*440+20);

C=new Point(Math.random()*600+20,Math.random()*440+20);

}

private function update(e:Event):void {

var mousePoint:Point=new Point(mouseX,mouseY);

triangleCanvas.graphics.clear();

if (isInsideTriangle(A,B,C,mousePoint)) {

triangleCanvas.graphics.lineStyle(1,0xFF0000);

}

else {

triangleCanvas.graphics.lineStyle(1,0x000000);

}

triangleCanvas.graphics.moveTo(A.x,A.y);

triangleCanvas.graphics.lineTo(B.x,B.y);

triangleCanvas.graphics.lineTo(C.x,C.y);

triangleCanvas.graphics.lineTo(A.x,A.y);

}

private function isInsideTriangle(A:Point,B:Point,C:Point,P:Point):Boolean {

var planeAB:Number = (A.x-P.x)*(B.y-P.y)-(B.x-P.x)*(A.y-P.y);

var planeBC:Number = (B.x-P.x)*(C.y-P.y)-(C.x - P.x)*(B.y-P.y);

var planeCA:Number = (C.x-P.x)*(A.y-P.y)-(A.x - P.x)*(C.y-P.y);

return sign(planeAB)==sign(planeBC) && sign(planeBC)==sign(planeCA);

}

private function sign(n:Number):int {

return Math.abs(n)/n;

}

And this is the result: click the mouse to draw a random triangle, move the mouse inside the triangle to turn it red.

Download the source code.

Rate this post: 1 Star

(21 votes, average: 4.95 out of 5)

Loading ...

Flash Templates provided by Template Monster are pre-made web design products developed using Flash technology.
They can be easily customized to meet the unique requirements of your project.

Be my fan on Facebook and follow me on Twitter! Exclusive content for my Facebook fans and Twitter followers

This post has 14 comments

kartofelek

on June 18, 2012 at 12:33 pm

Sometimes this algoritm draw a “dual line” and dont detect mouse pointer.
Antoan

on June 18, 2012 at 12:54 pm

I believe this way is faster. It is my interpretation of using a determinant in a 3×3 matrix.

function isInside(p1:Point, p2:Point,p3:Point):Boolean
{
return (p1.x*(p2.y-p3.y)+p2.x*(p3.y-p1.y)+p3.x*(p1.y-p2.y) >= 0);
}

Your vertices should be given in clockwise order (or was it anti-clockwise? I don’t remember)
senthil

on June 18, 2012 at 1:42 pm

Thanks for the simple math logic! Is this only for inside or on the triangle also?
Pierre Chamberlain

on June 18, 2012 at 3:13 pm

@Antoan, where’s the 4th point that refers to the user’s location / point that needs to be analysed within the triangle?

@Emanuele, wouldn’t the sign(…):int method perform faster if you did a conditional check if the number is above 0 = return 1, under 0 = return -1, else = 0? I haven’t done any tests myself, but something tells me calling Math.abs(…) is slower than a quick check of greater-than / less-than.
Rahyar

on June 18, 2012 at 10:07 pm

It was very interesting. Thanks
Ben Reynolds

on June 19, 2012 at 2:38 am

Awesome, I’d never thought of that!
Algorithm to determine if a point is inside a triangle with mathematics (no hit test involved) – Emanuele Feronato « eaflash

on June 19, 2012 at 9:31 am

[...] on http://www.emanueleferonato.com Share this:TwitterFacebookLike this:LikeBe the first to like [...]
Antoan

on June 26, 2012 at 8:13 pm

@Pierre, Oops, my bad, that actually just finds the determinant, this is the actual code:

function det(p1:Point, p2:Point,p3:Point):Number{
return p1.x*(p2.y-p3.y)+p2.x*(p3.y-p1.y)+p3.x*(p1.y-p2.y);
}

function isInside(p:Point, p1:Point, p2:Point, p3:Point):Boolean{
return det(p, p1, p2) >=0 && det(p, p2, p3) >= 0 && det(p, p3, p1) >= 0;
}
steve anson

on June 28, 2012 at 10:27 am

excellent explanation of math involved here, using 2 techniques, cross product and barycentric coordinates

http://www.blackpawn.com/texts/pointinpoly/default.html
Kate

on June 30, 2012 at 2:39 am

IS this code released under a specific license? It would be helpful if you release it under some license so it can be used widely.
Emanuele Feronato

on July 2, 2012 at 12:23 am

Kate, use it as you want :)
Zuze

on July 7, 2012 at 7:54 pm

This also works for freeform quads and higher order shapes.
+1. Good job!
Bruno Berti

on July 13, 2012 at 3:12 pm

Thanks for the excellent explanation!

I’m making a game where the player needs to create various types of triangles. By relative lengths of sides: scalene, isosceles and equilateral, and by internal angles: acute, obtuse and right. Do you have a tip for the calculation of differentiation of these triangles?
Sank

on September 14, 2012 at 8:55 am

@Antoan Thanks for the formula, it helped and it’s ‘clockwise’ :)

italian geek and PROgrammer

This post has 14 comments

Antoan

senthil

Antoan

Kate

Emanuele Feronato

Zuze

Bruno Berti

Sank