By ET 0.618


2010-01-12 14:25:49 8 Comments

Is there an easy way to determine if a point is inside a triangle? It's 2D, not 3D.

25 comments

@Shaon Majumder 2018-08-08 14:10:14

This is the simplest concept to determine if a point is inside or outside the triangle or on an arm of a triangle.

Determination of a point is inside a triangle by determinants:

Determination of a point is inside a triangle by determinants

The simplest working code:

#-*- coding: utf-8 -*-

import numpy as np

tri_points = [(1,1),(2,3),(3,1)]

def pisinTri(point,tri_points):
    Dx , Dy = point

    A,B,C = tri_points
    Ax, Ay = A
    Bx, By = B
    Cx, Cy = C

    M1 = np.array([ [Dx - Bx, Dy - By, 0],
                    [Ax - Bx, Ay - By, 0],
                    [1      , 1      , 1]
                  ])

    M2 = np.array([ [Dx - Ax, Dy - Ay, 0],
                    [Cx - Ax, Cy - Ay, 0],
                    [1      , 1      , 1]
                  ])

    M3 = np.array([ [Dx - Cx, Dy - Cy, 0],
                    [Bx - Cx, By - Cy, 0],
                    [1      , 1      , 1]
                  ])

    M1 = np.linalg.det(M1)
    M2 = np.linalg.det(M2)
    M3 = np.linalg.det(M3)
    print(M1,M2,M3)

    if(M1 == 0 or M2 == 0 or M3 ==0):
            print("Point: ",point," lies on the arms of Triangle")
    elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)):
            #if products is non 0 check if all of their sign is same
            print("Point: ",point," lies inside the Triangle")
    else:
            print("Point: ",point," lies outside the Triangle")

print("Vertices of Triangle: ",tri_points)
points = [(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)]
for c in points:
    pisinTri(c,tri_points)

@Joseph Merdrignac 2017-12-08 23:11:28

Since there's no JS answer,
Clockwise & Counter-Clockwise solution:

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {

    let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)

    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&
            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&
            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 

}

EDIT: there was a typo for det computation (cy - ay instead of cx - ax), this is fixed.

https://jsfiddle.net/jniac/rctb3gfL/

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {

    let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
	
    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&
            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&
            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 

}






let width = 500, height = 500

// clockwise
let triangle1 = {

	A : { x: 10, y: -10 },
	C : { x: 20, y: 100 },
	B : { x: -90, y: 10 },
	
	color: '#f00',

}

// counter clockwise
let triangle2 = {

	A : { x: 20, y: -60 },
	B : { x: 90, y: 20 },
	C : { x: 20, y: 60 },

	color: '#00f',
	
}


let scale = 2
let mouse = { x: 0, y: 0 }






// DRAW >

let wrapper = document.querySelector('div.wrapper')

wrapper.onmousemove = ({ layerX:x, layerY:y }) => {
	
	x -= width / 2
	y -= height / 2
	x /= scale
	y /= scale
	
	mouse.x = x
	mouse.y = y
	
	drawInteractive()

}

function drawArrow(ctx, A, B) {

	let v = normalize(sub(B, A), 3)
	let I = center(A, B)
	
	let p
	
	p = add(I, rotate(v, 90), v)
	ctx.moveTo(p.x, p.y)
	ctx.lineTo(I.x, I .y)
	p = add(I, rotate(v, -90), v)
	ctx.lineTo(p.x, p.y)

}

function drawTriangle(ctx, { A, B, C, color }) {

	ctx.beginPath()
	ctx.moveTo(A.x, A.y)
	ctx.lineTo(B.x, B.y)
	ctx.lineTo(C.x, C.y)
	ctx.closePath()
	
	ctx.fillStyle = color + '6'
	ctx.strokeStyle = color
	ctx.fill()
	
	drawArrow(ctx, A, B)
	drawArrow(ctx, B, C)
	drawArrow(ctx, C, A)
	
	ctx.stroke()

}

function contains({ A, B, C }, P) {

	return triangleContains(A.x, A.y, B.x, B.y, C.x, C.y, P.x, P.y)

}

function resetCanvas(canvas) {

	canvas.width = width
	canvas.height = height
	
	let ctx = canvas.getContext('2d')

	ctx.resetTransform()
	ctx.clearRect(0, 0, width, height)
	ctx.setTransform(scale, 0, 0, scale, width/2, height/2)
	
}

function drawDots() {

	let canvas = document.querySelector('canvas#dots')
	let ctx = canvas.getContext('2d')

	resetCanvas(canvas)
	
	let count = 1000

	for (let i = 0; i < count; i++) {

		let x = width * (Math.random() - .5)
		let y = width * (Math.random() - .5)
		
		ctx.beginPath()
		ctx.ellipse(x, y, 1, 1, 0, 0, 2 * Math.PI)
		
		if (contains(triangle1, { x, y })) {
		
			ctx.fillStyle = '#f00'
		
		} else if (contains(triangle2, { x, y })) {
		
			ctx.fillStyle = '#00f'
		
		} else {
		
			ctx.fillStyle = '#0003'
		
		}

		
		ctx.fill()
		
	}
	
}

function drawInteractive() {

	let canvas = document.querySelector('canvas#interactive')
	let ctx = canvas.getContext('2d')

	resetCanvas(canvas)
	
	ctx.beginPath()
	ctx.moveTo(0, -height/2)
	ctx.lineTo(0, height/2)
	ctx.moveTo(-width/2, 0)
	ctx.lineTo(width/2, 0)
	ctx.strokeStyle = '#0003'
	ctx.stroke()
	
	drawTriangle(ctx, triangle1)
	drawTriangle(ctx, triangle2)
	
	ctx.beginPath()
	ctx.ellipse(mouse.x, mouse.y, 4, 4, 0, 0, 2 * Math.PI)
	
	if (contains(triangle1, mouse)) {
	
		ctx.fillStyle = triangle1.color + 'a'
		ctx.fill()
		
	} else if (contains(triangle2, mouse)) {
	
		ctx.fillStyle = triangle2.color + 'a'
		ctx.fill()
		
	} else {
	
		ctx.strokeStyle = 'black'
		ctx.stroke()
		
	}
	
}

drawDots()
drawInteractive()










// trigo

function add(...points) {
	
	let x = 0, y = 0
	
	for (let point of points) {
	
		x += point.x
		y += point.y
	
	}
	
	return { x, y }

}

function center(...points) {
	
	let x = 0, y = 0
	
	for (let point of points) {
	
		x += point.x
		y += point.y
	
	}
	
	x /= points.length
	y /= points.length
	
	return { x, y }

}

function sub(A, B) {

	let x = A.x - B.x
	let y = A.y - B.y
	
	return { x, y }

}

function normalize({ x, y }, length = 10) {

	let r = length / Math.sqrt(x * x + y * y)
	
	x *= r
	y *= r
	
	return { x, y }

}

function rotate({ x, y }, angle = 90) {

	let length = Math.sqrt(x * x + y * y)
	
	angle *= Math.PI / 180
	angle += Math.atan2(y, x)
	
	x = length * Math.cos(angle)
	y = length * Math.sin(angle)
	
	return { x, y }

}
* {
	margin: 0;
}

html {
	font-family: monospace;
}

body {
	padding: 32px;
}

span.red {
	color: #f00;
}

span.blue {
	color: #00f;
}

canvas {
	position: absolute;
	border: solid 1px #ddd;
}
<p><span class="red">red triangle</span> is clockwise</p>
<p><span class="blue">blue triangle</span> is couter clockwise</p>
<br>
<div class="wrapper">
	<canvas id="dots"></canvas>
	<canvas id="interactive"></canvas>
</div>

enter image description here

I'm using here the same method as described above: a point is inside ABC if it is respectively on the "same" side of each line AB, BC, CA.

triangle inclusion example

@xApple 2018-07-23 12:34:42

I tired this code and it doesn't work. It always returns False.

@Joseph Merdrignac 2018-07-24 16:16:40

hmmm... you probably made a mistake. Here's a fiddle with that function running : jsfiddle.net/jniac/rctb3gfL

@Joseph Merdrignac 2018-07-24 16:59:55

i've seen your Python response, we are using the same method, if i use one more line (let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)), this is to determine the triangle winding order, so the method will works with CW & CCW triangles (see jsFiddle).

@Joseph Merdrignac 2018-07-24 19:46:03

hm i made a mistake, i wrote: let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay) instead of let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) so this is fixed, thanks for reporting

@Maxim Kamalov 2014-04-20 18:36:43

I needed point in triangle check in "controlable environment" when you're absolutely sure that triangles will be clockwise. So, I took Perro Azul's jsfiddle and modified it as suggested by coproc for such cases; also removed redundant 0.5 and 2 multiplications because they're just cancel each other.

http://jsfiddle.net/dog_funtom/H7D7g/

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = {
    x: W / 2,
    y: H / 2
};
var triangle = randomTriangle();

$("canvas").click(function (evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function (evt) {
    triangle = randomTriangle();
    test();
});

test();

function test() {
    var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);

    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function ptInTriangle(p, p0, p1, p2) {
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0) return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    while (true) {
        var result = {
            a: {
                x: rand(0, W),
                y: rand(0, H)
            },
            b: {
                x: rand(0, W),
                y: rand(0, H)
            },
            c: {
                x: rand(0, W),
                y: rand(0, H)
            }
        };
        if (checkClockwise(result.a, result.b, result.c)) return result;
    }
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>

<pre id="result"></pre>

<canvas width="500" height="500"></canvas>

Here is equivalent C# code for Unity:

public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 p2)
{
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0)
        return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}

@ravi tanwar 2019-02-03 05:41:39

One of the easiest ways to check if the area formed by the vertices of triangle (x1,y1),(x2,y2),(x3,y3) is positive or not.

Area can by calculated by the formula:

1/2 [x1(y2–y3) + x2(y3–y1) + x3(y1–y2)]

or python code can be written as:

def triangleornot(p1,p2,p3):
    return (1/ 2) [p1[0](p2[1]–p3[1]) + p2[0] (p3[1]–p1[1]) + p3[0] (p1[0]–p2[0])]

@Pawel 2016-05-13 23:34:09

Supposedly high-performance code which I adapted in JavaScript (article below):

function pointInTriangle (p, p0, p1, p2) {
  return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}
  • pointInTriangle(p, p0, p1, p2) - for counter-clockwise triangles
  • pointInTriangle(p, p0, p1, p2) - for clockwise triangles

Look in jsFiddle (performance test included), there's also winding checking in a separate function. Or press "Run code snippet" below

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

document.querySelector('#performance').addEventListener('click', _testPerformance);

test();

function test() {
    var result = checkClockwise(triangle.a, triangle.b, triangle.c) ? pointInTriangle(point, triangle.a, triangle.c, triangle.b) : pointInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function _testPerformance () {
	var px = [], py = [], p0x = [], p0y = [], p1x = [], p1y = [], p2x = [], p2y = [], p = [], p0 = [], p1 = [], p2 = [];
    
	for(var i = 0; i < 1000000; i++) {
    p[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p0[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p1[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p2[i] = {x: Math.random() * 100, y: Math.random() * 100};
  }
  console.time('optimal: pointInTriangle');
  for(var i = 0; i < 1000000; i++) {
    pointInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('optimal: pointInTriangle');

  console.time('original: ptInTriangle');
  for(var i = 0; i < 1000000; i++) {
  	ptInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('original: ptInTriangle');
}

function pointInTriangle (p, p0, p1, p2) {
	return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}

function ptInTriangle(p, p0, p1, p2) {
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0) return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return (s + t) < A;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<button id="performance">Run performance test (open console)</button>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>

Inspired by this: http://www.phatcode.net/articles.php?id=459

@John Bananas 2012-03-18 01:22:31

I wrote this code before a final attempt with Google and finding this page, so I thought I'd share it. It is basically an optimized version of Kisielewicz answer. I looked into the Barycentric method also but judging from the Wikipedia article I have a hard time seeing how it is more efficient (I'm guessing there is some deeper equivalence). Anyway, this algorithm has the advantage of not using division; a potential problem is the behavior of the edge detection depending on orientation.

bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
    int as_x = s.x-a.x;
    int as_y = s.y-a.y;

    bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;

    if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false;

    if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;

    return true;
}

In words, the idea is this: Is the point s to the left of or to the right of both the lines AB and AC? If true, it can't be inside. If false, it is at least inside the "cones" that satisfy the condition. Now since we know that a point inside a trigon (triangle) must be to the same side of AB as BC (and also CA), we check if they differ. If they do, s can't possibly be inside, otherwise s must be inside.

Some keywords in the calculations are line half-planes and the determinant (2x2 cross product). Perhaps a more pedagogical way is probably to think of it as a point being inside iff it's to the same side (left or right) to each of the lines AB, BC and CA. The above way seemed a better fit for some optimization however.

@surgemcgee 2019-05-08 17:14:42

This test is about 140-180% faster than the first one provided (thanks to you both btw :). I ran the code here: paste.ubuntu.com/p/k5w7ywH4p8 using the nodejs v8 engine with optimizations disabled and got the following results: :w !node -p --minimal test1: 114.852ms test2: 64.330ms test1: 115.650ms test2: 63.491ms test1: 117.671ms test2: 65.353ms test1: 119.146ms test2: 63.871ms test1: 118.271ms test1: 118.670ms test2: 63.352ms

@xuiqzy 2020-05-23 11:27:12

@surgemcgee why would you run it without optimizations? Isn't that more removed from reality then?

@surgemcgee 2020-05-24 12:40:10

@xuiqzy Well, my program contains the two different solutions. I have yet to administer the fastest method of doing it. Perhaps that comment should be removed and replaced with my completed works regarding this..

@Glenn Slayden 2013-12-31 17:34:51

C# version of the barycentric method posted by andreasdr and Perro Azul. Note that the area calculation can be avoided if s and t have opposite signs. I verified correct behavior with a pretty thorough unit test.

public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)
{
    var s = p0.Y * p2.X - p0.X * p2.Y + (p2.Y - p0.Y) * p.X + (p0.X - p2.X) * p.Y;
    var t = p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * p.X + (p1.X - p0.X) * p.Y;

    if ((s < 0) != (t < 0))
        return false;

    var A = -p1.Y * p2.X + p0.Y * (p2.X - p1.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y;

    return A < 0 ?
            (s <= 0 && s + t >= A) :
            (s >= 0 && s + t <= A);
}

[edit]
accepted suggested modification by @Pierre; see comments

@Luke Dupin 2018-11-20 19:01:26

The solution with the ending if statement works for clockwise and counter clockwise triangle points.

@Glenn Slayden 2019-11-20 01:46:00

@LukeDupin Not sure I understand your comment. This answer works as posted for any supplied ordering of the 3 points.

@Adam Gawne-Cain 2014-08-17 06:22:25

Java version of barycentric method:

class Triangle {
    Triangle(double x1, double y1, double x2, double y2, double x3,
            double y3) {
        this.x3 = x3;
        this.y3 = y3;
        y23 = y2 - y3;
        x32 = x3 - x2;
        y31 = y3 - y1;
        x13 = x1 - x3;
        det = y23 * x13 - x32 * y31;
        minD = Math.min(det, 0);
        maxD = Math.max(det, 0);
    }

    boolean contains(double x, double y) {
        double dx = x - x3;
        double dy = y - y3;
        double a = y23 * dx + x32 * dy;
        if (a < minD || a > maxD)
            return false;
        double b = y31 * dx + x13 * dy;
        if (b < minD || b > maxD)
            return false;
        double c = det - a - b;
        if (c < minD || c > maxD)
            return false;
        return true;
    }

    private final double x3, y3;
    private final double y23, x32, y31, x13;
    private final double det, minD, maxD;
}

The above code will work accurately with integers, assuming no overflows. It will also work with clockwise and anticlockwise triangles. It will not work with collinear triangles (but you can check for that by testing det==0).

The barycentric version is fastest if you are going to test different points with the same triangle.

The barycentric version is not symmetric in the 3 triangle points, so it is likely to be less consistent than Kornel Kisielewicz's edge half-plane version, because of floating point rounding errors.

Credit: I made the above code from Wikipedia's article on barycentric coordinates.

@Alex Byrth 2017-06-21 18:53:22

Nice ! It can even improved to use javax.vecmath's Point3f / Point2f tuples, in order to better handle the data input.

@Cédric Dufour 2015-12-04 17:08:58

By using the analytic solution to the barycentric coordinates (pointed out by Andreas Brinck) and:

  • not distributing the multiplication over the parenthesized terms
  • avoiding computing several times the same terms by storing them
  • reducing comparisons (as pointed out by coproc and Thomas Eding)

One can minimize the number of "costly" operations:

function ptInTriangle(p, p0, p1, p2) {
    var dX = p.x-p2.x;
    var dY = p.y-p2.y;
    var dX21 = p2.x-p1.x;
    var dY12 = p1.y-p2.y;
    var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
    var s = dY12*dX + dX21*dY;
    var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
    if (D<0) return s<=0 && t<=0 && s+t>=D;
    return s>=0 && t>=0 && s+t<=D;
}

Code can be pasted in Perro Azul jsfiddle or try it by clicking "Run code snippet" below

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

test();

function test() {
    var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function ptInTriangle(p, p0, p1, p2) {
    var A = 1/2 * (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    var sign = A < 0 ? -1 : 1;
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y) * sign;
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y) * sign;
    
    return s > 0 && t > 0 && (s + t) < 2 * A * sign;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>

Leading to:

  • variable "recalls": 30
  • variable storage: 7
  • additions: 4
  • subtractions: 8
  • multiplications: 6
  • divisions: none
  • comparisons: 4

This compares quite well with Kornel Kisielewicz solution (25 recalls, 1 storage, 15 subtractions, 6 multiplications, 5 comparisons), and might be even better if clockwise/counter-clockwise detection is needed (which takes 6 recalls, 1 addition, 2 subtractions, 2 multiplications and 1 comparison in itself, using the analytic solution determinant, as pointed out by rhgb).

@Jack D'Aurizio 2016-08-06 21:13:53

Nice solution. I think is is quite equivalent to my last approach here on MSE: math.stackexchange.com/questions/51326/…

@Giovanni Funchal 2016-11-28 17:51:05

I just tested the code as is, and it doesn't work for me (example p -4.69317198, -6.99191951 p0 -7.05846786 0.596718192 p1 -6.8703599 -2.36565161 p2 -4.69317198, -6.99191951)

@Cédric Dufour 2016-12-14 13:15:32

@GiovanniFunchal Strange, your example works for me, both in the jsfiddle (replace the initial "point" and "triangle" definitions) and my local Python implementation. Numeric precision issues (try stripping some decimals) ?

@Eyal 2017-05-29 08:13:54

Your seems the fastest in my test: jsfiddle.net/eyal/gxw3632c/27 . The difference between all the methods is quite small, though.

@devnullicus 2020-03-02 21:59:39

Try triangle (-1,-1), (1,-1), (0,1) and point (0,-1). Returns false when it should return true because s(2) + t(2) > d (2). Something wrong with the math on edges of the triangle, it seems, as the point p is right on the border between p0 and p1 and it's not a simple matter of converting a < to a <= or something like that.

@devnullicus 2020-03-03 00:33:46

Acually, after further study, it DOES appear that it can be easily fixed. Changing the last line of ptInTriangle to "return s >= 0.0 && t >= 0.0 && (s + t) <= 2.0 * A * sgn" seems to work.

@Developer 2014-01-06 11:32:43

Here is an efficient Python implementation:

def PointInsideTriangle2(pt,tri):
    '''checks if point pt(2) is inside triangle tri(3x2). @Developer'''
    a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \
        tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1])
    s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \
        (tri[0,0]-tri[2,0])*pt[1])
    if s<0: return False
    else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \
              (tri[1,0]-tri[0,0])*pt[1])
    return ((t>0) and (1-s-t>0))

and an example output:

enter image description here

@ThorSummoner 2020-04-08 05:00:19

I haven't been able to to make this work, for example for the point in the triangle [(0,0), (3,0), (3,4)], neither points (1,1) or (0,0) test positive. I tried with both clockwise and ant-clockwise triangle points.

@Ramiro R.C. 2017-09-25 16:13:20

Other function in python, faster than Developer's method (for me at least) and inspired by Cédric Dufour solution:

def ptInTriang(p_test, p0, p1, p2):       
     dX = p_test[0] - p0[0]
     dY = p_test[1] - p0[1]
     dX20 = p2[0] - p0[0]
     dY20 = p2[1] - p0[1]
     dX10 = p1[0] - p0[0]
     dY10 = p1[1] - p0[1]

     s_p = (dY20*dX) - (dX20*dY)
     t_p = (dX10*dY) - (dY10*dX)
     D = (dX10*dY20) - (dY10*dX20)

     if D > 0:
         return (  (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D  )
     else:
         return (  (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D  )

You can test it with:

X_size = 64
Y_size = 64
ax_x = np.arange(X_size).astype(np.float32)
ax_y = np.arange(Y_size).astype(np.float32)
coords=np.meshgrid(ax_x,ax_y)
points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,))
p_test = np.array([0 , 0])
p0 = np.array([22 , 8]) 
p1 = np.array([12 , 55]) 
p2 = np.array([7 , 19]) 
fig = plt.figure(dpi=300)
for i in range(0,X_size*Y_size):
    p_test[0] = points_unif[0][i]
    p_test[1] = points_unif[1][i]
    if ptInTriang(p_test, p0, p1, p2):
        plt.plot(p_test[0], p_test[1], '.g')
    else:
        plt.plot(p_test[0], p_test[1], '.r')

It takes a lot to plot, but that grid is tested in 0.0195319652557 seconds against 0.0844349861145 seconds of Developer's code.

Finally the code comment:

# Using barycentric coordintes, any point inside can be described as:
# X = p0.x * r + p1.x * s + p2.x * t
# Y = p0.y * r + p1.y * s + p2.y * t
# with:
# r + s + t = 1  and 0 < r,s,t < 1
# then: r = 1 - s - t
# and then:
# X = p0.x * (1 - s - t) + p1.x * s + p2.x * t
# Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t
#
# X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# we have to solve:
#
# [ X - p0.x ] = [(p1.x-p0.x)   (p2.x-p0.x)] * [ s ]
# [ Y - p0.Y ]   [(p1.y-p0.y)   (p2.y-p0.y)]   [ t ]
#
# ---> b = A*x ; ---> x = A^-1 * b
# 
# [ s ] =   A^-1  * [ X - p0.x ]
# [ t ]             [ Y - p0.Y ]
#
# A^-1 = 1/D * adj(A)
#
# The adjugate of A:
#
# adj(A)   =   [(p2.y-p0.y)   -(p2.x-p0.x)]
#              [-(p1.y-p0.y)   (p1.x-p0.x)]
#
# The determinant of A:
#
# D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x)
#
# Then:
#
# s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) }
# t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) }
#
# s = s_p / D
# t = t_p / D
#
# Recovering r:
#
# r = 1 - (s_p + t_p)/D
#
# Since we only want to know if it is insidem not the barycentric coordinate:
#
# 0 < 1 - (s_p + t_p)/D < 1
# 0 < (s_p + t_p)/D < 1
# 0 < (s_p + t_p) < D
#
# The condition is:
# if D > 0:
#     s_p > 0 and t_p > 0 and (s_p + t_p) < D
# else:
#     s_p < 0 and t_p < 0 and (s_p + t_p) > D
#
# s_p = { dY20*dX - dX20*dY }
# t_p = { dX10*dY - dY10*dX }
# D = dX10*dY20 - dY10*dX20

@Code Pope 2019-05-15 12:35:40

This function is not working. Give ptInTriang([11,45],[45, 45],[45, 45] ,[44, 45]) and it will return true although it is false

@Ajay Anand 2017-04-20 19:52:19

bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
  float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1), 
    l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2), 
    l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
  return (l1>0 && l2>0  && l3>0) || (l1<0 && l2<0 && l3<0);
}

It can not be more efficient than this! Each side of a triangle can have independent position and orientation, hence three calculations: l1, l2 and l3 are definitely needed involving 2 multiplications each. Once l1, l2 and l3 are known, result is just a few basic comparisons and boolean operations away.

@xApple 2018-07-23 12:57:41

Here is a solution in python that is efficient, documented and contains three unittests. It's professional-grade quality and ready to be dropped into your project in the form of a module as is.

import unittest

###############################################################################
def point_in_triangle(point, triangle):
    """Returns True if the point is inside the triangle
    and returns False if it falls outside.
    - The argument *point* is a tuple with two elements
    containing the X,Y coordinates respectively.
    - The argument *triangle* is a tuple with three elements each
    element consisting of a tuple of X,Y coordinates.

    It works like this:
    Walk clockwise or counterclockwise around the triangle
    and project the point onto the segment we are crossing
    by using the dot product.
    Finally, check that the vector created is on the same side
    for each of the triangle's segments.
    """
    # Unpack arguments
    x, y = point
    ax, ay = triangle[0]
    bx, by = triangle[1]
    cx, cy = triangle[2]
    # Segment A to B
    side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by)
    # Segment B to C
    side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy)
    # Segment C to A
    side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay)
    # All the signs must be positive or all negative
    return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0)

###############################################################################
class TestPointInTriangle(unittest.TestCase):

    triangle = ((22 , 8),
                (12 , 55),
                (7 , 19))

    def test_inside(self):
        point = (15, 20)
        self.assertTrue(point_in_triangle(point, self.triangle))

    def test_outside(self):
        point = (1, 7)
        self.assertFalse(point_in_triangle(point, self.triangle))

    def test_border_case(self):
        """If the point is exactly on one of the triangle's edges,
        we consider it is inside."""
        point = (7, 19)
        self.assertTrue(point_in_triangle(point, self.triangle))

###############################################################################
if __name__ == "__main__":
    suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle)
    unittest.TextTestRunner().run(suite)

There is an additional optional graphical test for the algorithm above to confirm its validity:

import random
from matplotlib import pyplot
from triangle_test import point_in_triangle

###############################################################################
# The area #
size_x = 64
size_y = 64

# The triangle #
triangle = ((22 , 8),
            (12 , 55),
            (7 , 19))

# Number of random points #
count_points = 10000

# Prepare the figure #
figure = pyplot.figure()
axes = figure.add_subplot(111, aspect='equal')
axes.set_title("Test the 'point_in_triangle' function")
axes.set_xlim(0, size_x)
axes.set_ylim(0, size_y)

# Plot the triangle #
from matplotlib.patches import Polygon
axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none'))

# Plot the points #
for i in range(count_points):
    x = random.uniform(0, size_x)
    y = random.uniform(0, size_y)
    if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g')
    else:                                  pyplot.plot(x, y, '.b')

# Save it #
figure.savefig("point_in_triangle.pdf")

Producing the following graphic:

Test the point_in_triangle function

@QuestionFeed 2018-02-12 13:00:15

bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
    /* inputs: e=point.x, f=point.y
               a=triangle.Ax, b=triangle.Bx, c=triangle.Cx 
               g=triangle.Ay, h=triangle.By, i=triangle.Cy */
    v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
    w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
    if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
    else return false;//is outside
    return 0;
} 

almost perfect Cartesian coordinates converted from barycentric are exported within *v (x) and *w (y) doubles. Both export doubles should have a * char before in every case, likely: *v and *w Code can be used for the other triangle of a quadrangle too. Hereby signed wrote only triangle abc from the clockwise abcd quad.

A---B
|..\\.o|  
|....\\.| 
D---C 

the o point is inside ABC triangle for testing with with second triangle call this function CDA direction, and results should be correct after *v=1-*v; and *w=1-*w; for the quadrangle

@Kornel Kisielewicz 2010-01-12 14:27:02

In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.

Here's some high quality info in this topic on GameDev, including performance issues.

And here's some code to get you started:

float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    float d1, d2, d3;
    bool has_neg, has_pos;

    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}

@Kornel Kisielewicz 2010-01-12 14:51:22

It's commonly used in 2D. Barycentric coordinates tend to confuse people. Also, given the cooridates of the triangle, and the point cordinate, I'm unsure about the efficiency of using barycentrics.

@Andreas Brinck 2010-01-12 15:09:44

@Kornel The barycentric version is more efficient in 2D as well. Your solution also has the problem that it will report a different result for points exactly on the edges of the triangle depending on wether the triangle is specified in clockwise or counter clockwise order.

@user252020 2010-01-16 04:57:47

For my purposes (the reason I found this site) the original answer proposed by Kornel Kisielewicz is much more efficient. I'm working with an LCD display with BYTE size coordinates and a very typical microprocessor where integer multiply is a very fast instruction, and division is much, much, slower. Numeric issues are also much smaller, due to no division! all calculations are exact. Thanks, Rick

@David Doria 2013-03-25 15:29:24

So the sign() function tells you which side of the halfplane (formed by the line between p2 and p3) p1 is?

@Thash 2016-09-09 15:28:09

Note that if you assume some order of the vertices (say counter clockwise), you don't need to calculate all of those determinants all the time. In fact in the best case, 1 determinant is enough to find that the point is not inside the triangle.

@user3289695 2016-10-14 10:53:31

Thank you! I made a JavaScript version of your code, and I don't know why or how it works, but it does! It has been very useful to me with an HTML5 canvas on which I draw a set of triangles.

@Bernhard 2016-12-19 12:19:24

In relation to this answer, I found this question on Math.SE useful: math.stackexchange.com/questions/51326/…

@Morris Franken 2017-05-16 21:20:27

Be aware though, this function will always return true if v1, v2 and v3 are equal.

@Eyal 2017-05-29 07:30:09

Math.sign is very slow. Better to change the last line to: return b1*b2>0 && b2*b3>0; Then remove all calls to sign.

@Yves Daoust 2018-04-29 09:08:24

@AndreasBrinck: you are missing that the barycentric approach requires the computation of the same 2x2 minors. But what's more, it performs a division by the 3x3 system determinant, which is useless, costly and numerically dangerous. And saying the "this does not belong to the algorithm" is wrong. Nothing beats the orientation test.

@Redu 2016-12-03 17:59:01

Honestly it is as simple as Simon P Steven's answer however with that approach you don't have a solid control on whether you want the points on the edges of the triangle to be included or not.

My approach is a little different but very basic. Consider the following triangle;

enter image description here

In order to have the point in the triangle we have to satisfy 3 conditions

  1. ACE angle (green) should be smaller than ACB angle (red)
  2. ECB angle (blue) should be smaller than ACB angle (red)
  3. Point E and Point C shoud have the same sign when their x and y values are applied to the equation of the |AB| line.

In this method you have full control to include or exclude the point on the edges individually. So you may check if a point is in the triangle including only the |AC| edge for instance.

So my solution in JavaScript would be as follows;

function isInTriangle(t,p){

  function isInBorder(a,b,c,p){
    var m = (a.y - b.y) / (a.x - b.x);                     // calculate the slope
    return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y);
  }
  
  function findAngle(a,b,c){                               // calculate the C angle from 3 points.
    var ca = Math.hypot(c.x-a.x, c.y-a.y),                 // ca edge length
        cb = Math.hypot(c.x-b.x, c.y-b.y),                 // cb edge length
        ab = Math.hypot(a.x-b.x, a.y-b.y);                 // ab edge length
    return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle
  }

  var pas = t.slice(1)
             .map(tp => findAngle(p,tp,t[0])),             // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0])
       ta = findAngle(t[1],t[2],t[0]);
  return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p);
}

var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}],
      point1 = {x:3, y:9},
      point2 = {x:7, y:9};

console.log(isInTriangle(triangle,point1));
console.log(isInTriangle(triangle,point2));

@andreasdr 2013-01-17 15:42:17

I agree with Andreas Brinck, barycentric coordinates are very convenient for this task. Note that there is no need to solve an equation system every time: just evaluate the analytical solution. Using Andreas' notation, the solution is:

s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

where Area is the (signed) area of the triangle:

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

Just evaluate s, t and 1-s-t. The point p is inside the triangle if and only if they are all positive.

EDIT: Note that the above expression for the area assumes that the triangle node numbering is counter-clockwise. If the numbering is clockwise, this expression will return a negative area (but with correct magnitude). The test itself (s>0 && t>0 && 1-s-t>0) doesn't depend on the direction of the numbering, however, since the expressions above that are multiplied by 1/(2*Area) also change sign if the triangle node orientation changes.

EDIT 2: For an even better computational efficiency, see coproc's comment below (which makes the point that if the orientation of the triangle nodes (clockwise or counter-clockwise) is known beforehand, the division by 2*Area in the expressions for s and t can be avoided). See also Perro Azul's jsfiddle-code in the comments under Andreas Brinck's answer.

@Andreas Brinck 2013-01-18 15:36:30

That is solving the equation system :)

@andreasdr 2013-01-19 15:43:46

Yes, my point is that any criticism of your method based on the computational cost of solving the equation system is unfounded, since that doesn't have to be done as part of the algorithm.

@coproc 2013-02-04 21:20:56

The efficiency can be improved by not dividing through 2*Area, i.e. by calculating s´=2*|Area|*s and t´=2*|Area|*t (if the orientation of the points - clockwise or counter-clockwise - is not known, the sign of Area has to be checked, of course, but otherwise it maybe does not even need to be computed), since for checking s>0 it suffices to check s´>0. And instead of checking 1-s-t>0 it suffices to check s´+t´<2*|Area|.

@rhgb 2014-01-16 16:42:13

I may add that if p0->p1->p2 is counter-clockwise in Cartesian (which is usually clockwise in screen coordinates), the Area calculated by this method will be positive.

@user2600366 2016-09-30 12:25:51

i wonder, what does it mean clockwise using 3 coordinates, do u mean that p0 is the highest, ? can u please explain?

@andreasdr 2016-10-02 08:19:29

@user2600366 When you travel along the boundary of the triangle in the direction p0 -> p1 -> p2 -> p0, and so on, you will have the interior of the triangle either always to your right or always to your left. In the former case, the numbering is clockwise, in the latter case, it is counter-clockwise.

@rbaleksandar 2016-10-17 15:24:10

@user2600366 While Barycentric is awesome there are other options such as the one that completely depends on the clockwise-orietnation of the vertices (which defines the winding of the triangle). I forgot its name but basically you check whether the point in on the left (inside) of each edge of the triangle (where right means outside). If you screw up the winding of the triangle you end up with nonsense. There you can see how the orientation plays role and what it means. This answer as well as the comments are great and extremely helpful! Also check Realtime Collision Detection book.

@Tyler Kelly 2018-10-04 22:17:11

can someone further explain how to handle unknown orientation + handling negative coordinates?

@user6839822 2018-10-31 14:04:39

@edit 2: if you leave out the division by 2*Area then the check on 1-s-t>0 will be true for points outside of the area. So the factor 1/(2*Area) actually is important!

@andreasdr 2019-01-10 11:50:33

The reason that you can avoid division by 2*Area if you know the orientation of the points is that in that case, you know the sign of Area. Looking at both cases: For clockwise / counter-clockwise orientation, Area>0 / Area < 0, so the factor 1/(2*Area) preserves / flips the sign of the three expressions. Thus, the point is within the triangle if all the expressions are positive / negative.

@Bela Bessenyei 2016-08-18 18:21:56

The easiest way and it works with all types of triangles is simply determine the angles of the P point A, B , C points angles. If any of the angles are bigger than 180.0 degree then it is outside, if 180.0 then it is on the circumference and if acos cheating on you and less than 180.0 then it is inside.Take a look for understanding http://math-physics-psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

@Orup 2016-07-14 19:33:55

I just want to use some simple vector math to explain the barycentric coordinates solution which Andreas had given, it will be way easier to understand.

  1. Area A is defined as any vector given by s * v02 + t * v01, with condition s >= 0 and t >= 0. If any point inside the triangle v0, v1, v2, it must be inside Area A.

enter image description here

  1. If further restrict s, and t belongs to [0, 1]. We get Area B which contains all vectors of s * v02 + t * v01, with condition s, t belongs to [0, 1]. It is worth to note that the low part of the Area B is the mirror of Triangle v0, v1, v2. The problem comes to if we can give certain condition of s, and t, to further excluding the low part of Area B.

enter image description here

  1. Assume we give a value s, and t is changing in [0, 1]. In the following pic, point p is on the edge of v1v2. All the vectors of s * v02 + t * v01 which are along the dash line by simple vector sum. At v1v2 and dash line cross point p, we have:

(1-s)|v0v2| / |v0v2| = tp|v0v1| / |v0v1|

we get 1 - s = tp, then 1 = s + tp. If any t > tp, which 1 < s + t where is on the double dash line, the vector is outside the triangle, any t <= tp, which 1 >= s + t where is on single dash line, the vector is inside the triangle.

Then if we given any s in [0, 1], the corresponding t must meet 1 >= s + t, for the vector inside triangle.

enter image description here

So finally we get v = s * v02 + t * v01, v is inside triangle with condition s, t, s+t belongs to [0, 1]. Then translate to point, we have

p - p0 = s * (p1 - p0) + t * (p2 - p0), with s, t, s + t in [0, 1]

which is the same as Andreas' solution to solve equation system p = p0 + s * (p1 - p0) + t * (p2 - p0), with s, t, s + t belong to [0, 1].

@Yves Daoust 2018-04-29 09:02:13

You can just say that you use the local frame defined by the three vertices so that the sides become s=0, t=0 and s+t=1. The affine coordinate transformation is a well-known operation of linear algebra.

@Pierre 2015-11-30 23:45:09

There are pesky edge conditions where a point is exactly on the common edge of two adjacent triangles. The point cannot be in both, or neither of the triangles. You need an arbitrary but consistent way of assigning the point. For example, draw a horizontal line through the point. If the line intersects with the other side of the triangle on the right, the point is treated as though it is inside the triangle. If the intersection is on the left, the point is outside.

If the line on which the point lies is horizontal, use above/below.

If the point is on the common vertex of multiple triangles, use the triangle with whose center the point forms the smallest angle.

More fun: three points can be in a straight line (zero degrees), for example (0,0) - (0,10) - (0,5). In a triangulating algorithm, the "ear" (0,10) must be lopped off, the "triangle" generated being the degenerate case of a straight line.

@ihayet 2014-08-03 18:56:04

If you know the co-ordinates of the three vertices and the co-ordinates of the specific point, then you can get the area of the complete triangle. Afterwards, calculate the area of the three triangle segments (one point being the point given and the other two being any two vertices of the triangle). Thus, you will get the area of the three triangle segments. If the sum of these areas are equal to the total area (that you got previously), then, the point should be inside the triangle. Otherwise, the point is not inside the triangle. This should work. If there are any issues, let me know. Thank you.

@Yves Daoust 2014-02-02 11:27:31

If you are looking for speed, here is a procedure that might help you.

Sort the triangle vertices on their ordinates. This takes at worst three comparisons. Let Y0, Y1, Y2 be the three sorted values. By drawing three horizontals through them you partition the plane into two half planes and two slabs. Let Y be the ordinate of the query point.

if Y < Y1
    if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done
    else Y > Y0 -> the point lies in the upper slab
else
    if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done
    else Y < Y2 -> the point lies in the lower slab

Costs two more comparisons. As you see, quick rejection is achieved for points outside of the "bounding slab".

Optionally, you can supply a test on the abscissas for quick rejection on the left and on the right (X <= X0' or X >= X2'). This will implement a quick bounding box test at the same time, but you'll need to sort on the abscissas too.

Eventually you will need to compute the sign of the given point with respect to the two sides of the triangle that delimit the relevant slab (upper or lower). The test has the form:

((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk))

The complete discussion of i, j, k combinations (there are six of them, based on the outcome of the sort) is out of the scope of this answer and "left as an exercise to the reader"; for efficiency, they should be hard-coded.

If you think that this solution is complex, observe that it mainly involves simple comparisons (some of which can be precomputed), plus 6 subtractions and 4 multiplies in case the bounding box test fails. The latter cost is hard to beat as in the worst case you cannot avoid comparing the test point against two sides (no method in other answers has a lower cost, some make it worse, like 15 subtractions and 6 multiplies, sometimes divisions).

UPDATE: Faster with a shear transform

As explained just above, you can quickly locate the point inside one of the four horizontal bands delimited by the three vertex ordinates, using two comparisons.

You can optionally perform one or two extra X tests to check insideness to the bounding box (dotted lines).

Then consider the "shear" transform given by X'= X - m Y, Y' = Y, where m is the slope DX/DY for the highest edge. This transform will make this side of the triangle vertical. And since you know on what side of the middle horizontal you are, it suffices to test the sign with respect to a single side of the triangle.

enter image description here

Assuming you precomputed the slope m, as well as the X' for the sheared triangle vertices and the coefficients of the equations of the sides as X = m Y + p, you will need in the worst case

  • two ordinate comparisons for vertical classification;
  • optionally one or two abscissa comparisons for bounding box rejection;
  • computation of X' = X - m Y;
  • one or two comparisons with the abscissas of the sheared triangle;
  • one sign test X >< m' Y + p' against the relevant side of the sheared triangle.

@psiman 2012-10-29 23:28:23

What I do is precalculate the three face normals,

  • in 3D by cross product of side vector and the face normal vector.

  • in 2D by simply swapping components and negating one,

then inside/outside for any one side is when a dot product of the side normal and the vertex to point vector, change sign. Repeat for other two (or more) sides.

Benefits:

  • a lot is precalculated so great for multiple point testing on same triangle.

  • early rejection of common case of more outside than inside points. (also if point distribution weighted to one side, can test that side first.)

@Andreas Brinck 2010-01-12 14:41:40

Solve the following equation system:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

The point p is inside the triangle if 0 <= s <= 1 and 0 <= t <= 1 and s + t <= 1.

s,t and 1 - s - t are called the barycentric coordinates of the point p.

@Daniel Rikowski 2010-01-12 14:51:53

This is faster than the half-plane check, but perhaps a little bit harder to grasp if you are new to barycentric coordinates.

@Matthieu N. 2010-01-16 22:14:22

With trivial exits (not implemented) in Kornel's method, his can actually far more efficient than yours. If you actually try to compute s and t you'll know what I mean.

@Andreas Brinck 2010-01-17 08:49:06

@Ben You can implement trivial exits in this version as well, for instance you can begin by calculating only s and exit if it isn't in the [0 1] range. If the triangles can be both clockwise and counter clockwise you'll still have to calculate at least two signs in the halfplane version. Finally, how effective any trivial exits are depend on the input data.

@andreasdr 2013-01-17 15:45:11

Exactly three years later, here are my 2 cents: Just solve for s and t analytically first, and let the program evaluate those expressions. The point p is then in the triangle if and only if s, t and 1-s-t are all positive. It doesn't get more computationally efficient than that.

@urraka 2013-04-09 01:01:23

I wanted to test this so I made a jsfiddle, relying on @andreasdr solution and coproc comment: jsfiddle.net/PerroAZUL/zdaY8/1

@H'H 2013-08-23 15:30:56

Is this algorithm efficient for an unstructured mesh with lots of triangle elements?

@Thomas Eding 2014-05-02 16:15:01

Optimization: s + t <= 1 implies s <= 1 and t <= 1 if s >= 0 and t >= 0.

@Flayn 2015-08-25 10:30:59

The article totologic.blogspot.fr/2014/01/… proposed by @Logic post helped me to better understand this solution

@Eyal 2017-05-27 18:19:15

I found an implementation of barycentric in javascript that fails for a pont that is very far from the triangle due to floating point: jsperf.com/point-in-triangle and it fails with this triangle and point: {"a":{"x":-40.49496078491211,"y":-8.738582611083984},"b":{"x‌​":-41.94913723574891‌​,"y":-6.313193949870‌​829},"c":{"x":-41.94‌​775545887751,"y":-6.‌​315498584878696} and point {x: 47.87142596679951, y: -6.500680708968048} Is there an accurate version?

@Darkmoor 2017-11-08 14:27:23

For an intuitive explanation.

@maaartinus 2018-02-28 23:16:28

@AndreasBrinck I can't see any support for your claim that the accepted answer is "pretty inefficient" when compared to yours. I'd bet, in fixed point it's more efficient. You wrote nothing about how you solve the equations system - it's trivial, until you consider possible numerical problems.

@Jan Turoň 2018-03-21 15:57:04

I voted you down, Andreas, as you fail to understand the question. OP asked for easy way, not efficient. You even comment on easy solution of Kornel and keep talking about efficiency.

@MannyC 2020-07-13 20:40:29

I just wanted to add a comment for people with difficulties grasping the barycentric coordinates. Taking these coordinates is like aligning our x axis with the side p1-p0 and our y axis with p2-p0. In this basis the triangle is a half square with vertices (0,0) (1,0) and (0,1). It's very easy too see the conditions on s, t and s+t after one draws it.

@Simon P Stevens 2010-01-12 14:31:40

A simple way is to:

find the vectors connecting the point to each of the triangle's three vertices and sum the angles between those vectors. If the sum of the angles is 2*pi then the point is inside the triangle.

Two good sites that explain alternatives are:

blackpawn and wolfram

@Kornel Kisielewicz 2010-01-12 14:35:03

Um, that method isn't exactly efficient, and is very prone to numerical errors...

@Simon P Stevens 2010-01-12 14:38:40

It's quite the opposite, it's very inefficient :-) It's just one simple way though, that's easy to implement. Can you give an example of a numerical error this would cause?

@Redu 2016-12-03 17:31:29

While to me this simply seems to be the best of all answers under this topic, i guess the points on the edges of the triangle are calculated to be included to the triangle and you haven't got a solid control on that.

@lonewarrior556 2018-01-20 10:08:48

checking if it's exactly 2pi is numerically impossible given pi's irrational. However you just need to check if the angles add up to something greater than pi.

Related Questions

Sponsored Content

30 Answered Questions

[SOLVED] Is floating point math broken?

48 Answered Questions

54 Answered Questions

35 Answered Questions

[SOLVED] Determine Whether Two Date Ranges Overlap

5 Answered Questions

[SOLVED] How do I determine whether my calculation of pi is accurate?

20 Answered Questions

[SOLVED] How do CSS triangles work?

36 Answered Questions

[SOLVED] How can I pair socks from a pile efficiently?

35 Answered Questions

14 Answered Questions

[SOLVED] What is the optimal algorithm for the game 2048?

18 Answered Questions

[SOLVED] What algorithms compute directions from point A to point B on a map?

Sponsored Content