# Thread: Determine if a point lies within area of a triangle

1. ## Determine if a point lies within area of a triangle

I need to write an algorithm to determine whether a point lies within the area of a triangle. (meaning on the inside) I developed a theory of a way that I think will work, but want to know if there is a better way to do this.

The way I came up with is to first organize the points in order of either highest to lowest, or farthest left to farthest right. Then find the equation of a line from the point to each vertex in the triangle. Then if that line lies between or on the other two vertices for all three of the lines, the point is inside the triangle. And if it lies outside (ie to the left or right or above or below) of the other two vertices on any of the lines, it is outside. I attached a picture to show what I mean.

In the left picture, you can see that the line going almost up and down lies to the right of the left vertex, and to the left of the right vertex, so it is good. The one with the negative slope below the right vertex, and above the middle vertex. and the line with the negative slope lies below the left vertex, and above the middle vertex.

In the second picture, the line going through the middle vertex lies below both the left and right vertex. The line going through the left vertex lies to the left of both the middle and right vertex.

I'll have to think about how to do the algorithm. Slope should be easy to figure out as I am given the locations of the vertices, and the point will be the origin, and I think I can use point-slope format for a line to see how it fares. But before I spend the energy, is there a better way to do this? Something simpler, or requiring fewer computations, or easier to see in general.

Measure the interior angles of original triangle and the interior angles of the triangles formed by each set of 2 of the orignal vertices and the point in question.

So find 3 interior angles (the initial triangle), and then 6 interior angles (2 for each of the original vertex). If either of these 2 interior angles is larger than the original (for any one vertex), the point is outside the triangle otherwise it is not.

This is similar to some techniques used for finding the convex hull of a collection of points.

3. Hmm.. I'm not sure but, you may draw a ray that starts from the given point and goes over the center of triangle. If the ray crosses two sides of the triangle, the point is outside. If it crosses only one side, it's in the triangle.

4. You could also find the barycentric coordinates (see here or here) of the point (with the triangle in question as the reference triangle) and check the signs of the coordinates: if one or two are negative (but not all three, as barycentric coordinates are homogeneous), it is outside the triangle. If all three have the same sign, it is inside the triangle. If any coordinate is zero, it is on the triangle's perimeter.

--Kevin C.

5. Originally Posted by angel.white
I need to write an algorithm to determine whether a point lies within the area of a triangle. (meaning on the inside) I developed a theory of a way that I think will work, but want to know if there is a better way to do this.
The correct term is the point is in the interior of the triangle.
The theorem is: A point is in the interior if and only if the point is in the interior of each of the angles of the triangle.
In reality, we just have to check if the point is interior to two of the angles.
If the rays $\displaystyle \vec {AB} \,,\,\vec {AC} ,\,\& \,\vec {AP}$ are coplanar the we can say that P is interior to $\displaystyle \angle CAB$ if $\displaystyle \arccos \left( {\frac{{\vec {AB} \cdot \vec {AP} }}{{\left\| {\vec {AB} } \right\|\left\| {\vec {AP} } \right\|}}} \right) + \arccos \left( {\frac{{\vec {AC} \cdot \vec {AP} }}{{\left\| {\vec {AC} } \right\|\left\| {\vec {AP} } \right\|}}} \right) = \arccos \left( {\frac{{\vec {AB} \cdot \vec {AC} }}{{\left\| {\vec {AB} } \right\|\left\| {\vec {AC} } \right\|}}} \right)$

You should be able to program a check to see of the point is interior to two of the angles.

6. Thank you everybody, I appreciate the help.
Originally Posted by Plato
The correct term is the point is in the interior of the triangle.
The theorem is: A point is in the interior if and only if the point is in the interior of each of the angles of the triangle.
In reality, we just have to check if the point is interior to two of the angles.
If the rays $\displaystyle \vec {AB} \,,\,\vec {AC} ,\,\& \,\vec {AP}$ are coplanar the we can say that P is interior to $\displaystyle \angle CAB$ if $\displaystyle \arccos \left( {\frac{{\vec {AB} \cdot \vec {AP} }}{{\left\| {\vec {AB} } \right\|\left\| {\vec {AP} } \right\|}}} \right) + \arccos \left( {\frac{{\vec {AC} \cdot \vec {AP} }}{{\left\| {\vec {AC} } \right\|\left\| {\vec {AP} } \right\|}}} \right) = \arccos \left( {\frac{{\vec {AB} \cdot \vec {AC} }}{{\left\| {\vec {AB} } \right\|\left\| {\vec {AC} } \right\|}}} \right)$

You should be able to program a check to see of the point is interior to two of the angles.
I'm unfamiliar with geometry, how exactly is $\displaystyle \vec {AP}$ defined? Is that the slope from A to P or the line that defines it, ie y=mx+b, something else?

Right now I'm looking at using Iknowone's method, but I like that there is already an equation to determine the answer.

7. ## Best and Worst

$\displaystyle \vec {AB}$

Is the vector from the point $\displaystyle A$ to the point $\displaystyle B$.

This can be written in component form:

given $\displaystyle A = (a_1,a_2)$ and $\displaystyle B =(b_1,b_2)$ we have $\displaystyle \vec {AB} = (b_1-a_1, b_2-a_2)$.

The norm of the vector $\displaystyle ||\vec{AB}||$ is just the length of the line between points $\displaystyle A$ and $\displaystyle B$.

What Plato suggested is actually a more detailed explanation of my suggestion. He says, (which should be clear if you draw a picture),
$\displaystyle \angle CAB = \angle CAP + \angle PAB$ if the point P is in the interior of $\displaystyle \angle CAB$.

It shouldn't take too much convincing to see that if the above is satisfied for at least 2 of the following: $\displaystyle \angle CAB, \angle ABC, \angle BCA$ then the point P must be in the interior of the triangle.

So an algorithm might just check each vertex and see if the equation given is satisfied. If 2 are satisfied the program terminates and returns that the point is in the interior. If no 2 vertices satisfy the equation the program terminates and returns that the point is not in the interior. In the worst case scenario the program will have to check 3 vertices.

Now, while Plato and I had the same idea, the question of exactly how to write the program is still unanswered. His suggestion requires you sum two angles and compare to a third while my suggestion was to compare two angles (one at a time) to the third. In the best case scenario the comparison method will outperform the summation method since it may be that you only have to compare the first angle for one of the three vertices:

comparison one: interior angle is larger than original, point outside triangle.

In the worst case they are more or less equivalent. Summation may be faster or slower than logical comparison but there are an equivalent number of such operations in each algorithm -

Plato:
1. find 9 angles using the formula above.
2. 1 sum, 1 comparison for 2 vertices.

Me:
1. find 9 angles using the formula aboce.
2. 2 comparisons for 2 vertices.

Then again we are talking about 13 operations (9 of which are basic forumlas) and so efficiency is basically irrelavent.

More fun is to come up with the WORST algorithm.

8. I would like to thank everyone who helped me out, I was able to find an algorithm and solve the problem

I attached a picture to show how it works. (note that it is arbitrary whether B is above or below the x-axis, and it is also arbitrary whether it is to the left or the right of the line it is across from.)

In the end, I decided it was easier to deal with points than angles. Here is the layout of the program, algorithm is roughly the second half. (actual program was written in C)
Code:
setup variables:
ax, ay, bx, by, cx, cy   /*hold x and y values of each point's x and y*/
mab, mac, mbc           /*hold slope for each line*/
abxint, acxint, bcxint   /*hold x intercept for each line*/

count    /*number of triangles with origin in the interior of the triangle */
flag      /* used to keep track of whether a triangle passes a given test */

FOR 1 TO # of triangles to check

sort triangle so that A has the greatest y value, and c has the lowest y value

determine slope of ab, ac, bc
/* using: mab = (by - ay)/(bx-ax)    */

determine x intercept for ab, ac, bc
/* using: abxint = ((mab*ax)-ay)/mab   */

/* check that origin is between x intercepts on ac and bc */
flag = FALSE
IF ac x-int < 0 < bc x-int
flag = TRUE
END IF

IF ac x-int > 0 > bc x-int
flag = TRUE
END IF

/* if it isn't, it fails and we're done */
IF flag = FALSE
END IF

/* perform second test: check that origin is between x-intercepts on ac and ab, if so then origin is in the interior of the triangle */
IF ac x-int < 0 < ab x-int
END IF

IF ac x-int > 0 > ab x-int
END IF

END LOOP

DISPLAY value of count

9. What is the "cross product" thing?

I see some other people's answers that are drastically simpler than mine, such as:

if it the following are true, the origin is in the interior of the triangle:
ax*by-ay*bx > 0
bx*cy-by*cx > 0
cx*ay-cy*ax > 0

10. ## access the co ordinates of the triangle

hi...i have the same prob...i want to access al the co ordinates which lies inside the area of the triangle.i need a algo for that..plz help..thanks in advance