How do we know if the coordintes of a point lie within and outside a triangle?

[david07]

ex: if the origin points are A = (0, 0)

B = (3,5)
C= (6,3)

How do we know that point (3,1) lies within or outside the triangle using mathematical formulas?

I know there is a similar topic to this somewhere in forums but i don't understand where a & b comes from.

please can anyone help me out?

thanks

 

[radou]

Well, if you're looking at that certain point, the I guess you can find the equation of the line connecting A and C, and simply find the value of that function at x = 3. If it's greater than 1, then (3, 1) doesn't lie in the triangle.

 

[david07]

Thanks but no not for that particular point.

I mean the coordinates can be different except the origin. (0, 0)

how do we know if we have to find the equation of line of AC or AB or BC??

 

[robert Ihnot]

If you take that particular problem and draw the triangle, you can determine which sides are where. The picture is important. Of the three points, (where X is the first coordinate, Y the second), (3,5) is the highest point, while (6,3) lies the furthest along the X-axis.

Moving along the X-axis from (0,0) to (6,3) we have a slope of 1/2. The point in question (3,1), connected to (0,0), has a slope of Y/X = 1/3. So that line and point is outside the triangle.

 

[Werg22]

Well, I can think of two ways. First, with areas. Say the vertices are A, B and C. We denote the area of that triangle K. A point P, if inside the triangle, satisfies the condition

PAB + PAC + PCB = K.

That is, the sum of the area of all possible triangles formed between two vertices of ABC and P is K. A point that does not satisfy this equality is located outside the triangle.

The second way is equivalent but goes along with the angles. That is (I use < to denote angles):

<APB + <APC + <BPC = 360

PS: Note that points along the sides of the triangle ABC are included.

 

[forrest747]

You know the vertices so you can easily get the linear equations [call them y1=, y2= and y3=] for the three lines that contain each side of the triangle.

[Method caveat: begin with a point known to be OUTSIDE the triangle. Find the line equation y4= from that outside point to the point you want to check. Determine if y4 intersects each of y1, y2 or y3. Simple to program this algorithm. Count the number of intersections.

If you begin OUTSIDE the triangle, and you have no intersections, then you are outside the triangle (duh). One intersection, you are inside the triangle. Two intersections, you are outside the triangle.

This trick works for any polygon. If you begin outside the polygon, count the number of intersections and if you have an even number of intersections, you are outside the polygon. If you have an odd number of intersections, you are inside the polygon.

 

[Werg22]

You know the vertices so you can easily get the linear equations [call them y1=, y2= and y3=] for the three lines that contain each side of the triangle.

[Method caveat: begin with a point known to be OUTSIDE the triangle. Find the line equation y4= from that outside point to the point you want to check. Determine if y4 intersects each of y1, y2 or y3. Simple to program this algorithm. Count the number of intersections.

If you begin OUTSIDE the triangle, and you have no intersections, then you are outside the triangle (duh). One intersection, you are inside the triangle. Two intersections, you are outside the triangle.

This trick works for any polygon. If you begin outside the polygon, count the number of intersections and if you have an even number of intersections, you are outside the polygon. If you have an odd number of intersections, you are inside the polygon.

Certainly a valid method, but it's a shame there is no equivalent analytical method...

 

[david07]

Well, I can think of two ways. First, with areas. Say the vertices are A, B and C. We denote the area of that triangle K. A point P, if inside the triangle, satisfies the condition

PAB + PAC + PCB = K.

That is, the sum of the area of all possible triangles formed between two vertices of ABC and P is K. A point that does not satisfy this equality is located outside the triangle.

The second way is equivalent but goes along with the angles. That is (I use < to denote angles):

<APB + <APC + <BPC = 360

PS: Note that points along the sides of the triangle ABC are included.

so u mean first find the area of the triangle using the coordinate points.

and then do PAB+PAC+PCB=are of triangle using the given coordinate points.

what i don't understand is how does PAB+PAC+PCB work??

I mean AB, AC, CB can be found using distance formula but P is suppose some point (0,2) how does that work?

 

[mathwonk]

wow that is a really cool question. i don't know the NSWER yet.

heres a suggestion, say the vertices are A,B,C, and the extra point is D.

then for each pair of vertices say A,B, try to decide if C and D are on h same side of line joining A,B.

the linear equation which equals zero at both A,B, will hve the same sign at points on the same side of line AB.

does this help?

 

[Werg22]

so u mean first find the area of the triangle using the coordinate points.

and then do PAB+PAC+PCB=are of triangle using the given coordinate points.

what i don't understand is how does PAB+PAC+PCB work??

I mean AB, AC, CB can be found using distance formula but P is suppose some point (0,2) how does that work?

I'm afraid I don't quite get the question... maybe I should have been clearer with the expression PAB + PAC + PCB. PAB, PAC, PCB represent the areas of the triangles PAB, PAC and PCB, respectively. So if the sum of the areas of the triangles PAB, PAC and PCB, is equal to the area of ABC, then point P lies inside the triangle. I know it's tedious to calculate all these areas (personally I find Heron's formula very bad looking) but it's still a solution...

Edit: Oh I see what you mean. ABC and P represent the points, not the sides!

 

[Werg22]

wow that is a really cool question. i don't know the NSWER yet.

heres a suggestion, say the vertices are A,B,C, and the extra point is D.

then for each pair of vertices say A,B, try to decide if C and D are on h same side of line joining A,B.

the linear equation which equals zero at both A,B, will hve the same sign at points on the same side of line AB.

does this help?

Though I didn't quite get this part, if it's possible to easily verify if C and D are on the same side, there's yet another solution: if C and D are on the same side, and the x coordinate of C is smaller than that of D or bigger, depending on weather they are on the right or left of segment AB, and if the linear equation that goes through C and D crosses the segment AB, then D is inside the triangle. I know I'm just stating the obvious, but someone must do it.

 

[D H]

This appears to work: use two of the edges as a basis for the plane. The coordinates of the unknown point in this "edge space" must be non-negative and must sum to one or less.

Algorithm: Place one of the vertices at the origin. Denote the other two vertices as
$$\bmatrix x_i \\ y_i\endbmatrix$$
Denote the point in question as
$$\bmatrix x \\ y\endbmatrix$$

The coordinates of this point are

$$\bmatrix u\\v \endbmatrix = \bmatrix x_1 & x_2 \\y_1 & y_2 \endbmatrix^{-1} \bmatrix x \\ y\endbmatrix$$

The point is inside the triangle if $u,v>=0$ and $u+v<=1$.

 

[mathwonk]

the interior of a triangle is the intersection of the three hal planes determiend by the three sides.

so if a point is on the same side of each side as the third vertex, it is in the interior.

e.g. take the triangle with vertices (0,0), (0,1),(1,0).

the three sides determine the three lines x=0, y=0, and x+y-1=0.

now applying the first equation, namely x, to the third vertex (1,0) gives 1, so an interior point shoiuld have x>0.

the second side with vertices (0,0), (1,0), determines the line y=0 and the third vertex has y=1 so the interior points have y>0. then x+y-2 = 0 for the third side, and the third vertex has x+y-1 = -1, so the interior points satisfy x+y-1 < 0.

hence an interior point is one with x>0, y>0 and x+y < 1. e.g. (1/3,1/2).

 

[david07]

ok i kinda understand werg22 area method but i still don't get the right answer.
Could someone please help me out with this

A (0,0)
B (1,5)
C (4,1)
P (2,2)

I am getting the area of ABC as 9.5

PAB+PAC+PCB=0

Technically (2,2) should be in but according to your method if it isn't equal to area of ABC then it is outside.

Don't understand what mistake i am making.

Can someone help please.

Thanks

technically

 

[Werg22]

PAB+PAC+PCB=0

What is the meaning of this?

 

[D H]

Take the triangle with vertices (0,0), (0,1),(1,0).

the three sides determine the three lines x=0, y=0, and x+y-1=0.

This is a nice canonical triangle. Let (u,v) be the Cartesian coordinates of a point on a plane with a triangle with vertices at (0,0),(1,0),(0,1). As mathwonk pointed out, the conditions that a point (u,v) be in the interior of the canonical triangle are u,v>0 and u+v<1.

This canonical triangle can be mapped to a triangle with vertices at (0,0),(x1,y1),(x2,y2) by the transformation

$$\bmatrix x\\y\endbmatrix = \bmatrix x_1 & x_2 \\y_1 & y_2 \endbmatrix\;\bmatrix u\\v\endbmatrix$$

The inverse of this transformation maps from the generic triangle to the canonical triangle:

$$\bmatrix u\\v \endbmatrix = \bmatrix x_1 & x_2 \\y_1 & y_2 \endbmatrix^{-1} \bmatrix x \\ y\endbmatrix$$

which is what I stated in post #12 (except I did not have strict inequalities).

 

[david07]

I mean when i find PAB, PAC, PCB i get all of those areas as 0.

which is not equal to the area of ABC.

hence (2,2) does not fall in the triangle ABC although it is supposed to be.

 

[VietDao29]

I mean when i find PAB, PAC, PCB i get all of those areas as 0.

which is not equal to the area of ABC.

hence (2,2) does not fall in the triangle ABC although it is supposed to be.

How did you come up with all those area equal to 0? It's not true. =.="

An area of a triangle is 0 only when 3 points overlaps each other, or they are co-linear. Your example is neither of the two cases above, so your triangle does have area.

 

[rdpreet]

This is a nice canonical triangle. Let (u,v) be the Cartesian coordinates of a point on a plane with a triangle with vertices at (0,0),(1,0),(0,1). As mathwonk pointed out, the conditions that a point (u,v) be in the interior of the canonical triangle are u,v>0 and u+v<1.

This canonical triangle can be mapped to a triangle with vertices at (0,0),(x1,y1),(x2,y2) by the transformation

$$\bmatrix x\\y\endbmatrix = \bmatrix x_1 & x_2 \\y_1 & y_2 \endbmatrix\;\bmatrix u\\v\endbmatrix$$

The inverse of this transformation maps from the generic triangle to the canonical triangle:

$$\bmatrix u\\v \endbmatrix = \bmatrix x_1 & x_2 \\y_1 & y_2 \endbmatrix^{-1} \bmatrix x \\ y\endbmatrix$$

which is what I stated in post #12 (except I did not have strict inequalities).

I got the point of mapping the triangle to a canonical triangle...

But I am hazy about the process, with the all the formulae put in codes. Can you please simplify it a li'l.

 

[awkward]

You can find some methods here:

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

 

[benice]

Hi,

We can find a function fun for a triangle such that:
* fun(x,y) = 0 if (x,y) lies on the triangle, i.e., fun(x,y) = 0 is an equation for the triangle;
* fun(x,y) < 0 if (x,y) lies inside the triangle;
* fun(x,y) > 0 if (x,y) lies outside the triangle.

The function for the triangle ABC is
fun(x,y) = 3x - 6y - 21 + abs(7x - 21) + abs(9x - 18y + 21 - abs(7x - 21)).

Since fun(3,1) = 12 > 0, (3,1) lies outside the triangle ABC.