Determine if a point lies within area of a triangle

**angel.white** · March 6th 2008, 11:19 AM

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.

**iknowone** · March 6th 2008, 12:08 PM

How about:

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.

**wingless** · March 6th 2008, 12:17 PM

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.

**TwistedOne151** · March 6th 2008, 12:40 PM

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.

**Plato** · March 6th 2008, 01:15 PM

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 $\vec {AB} \,,\,\vec {AC} ,\,\& \,\vec {AP}$ are coplanar the we can say that P is interior to $\angle CAB$ if $\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.

**angel.white** · March 6th 2008, 06:19 PM

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 $\vec {AB} \,,\,\vec {AC} ,\,\& \,\vec {AP}$ are coplanar the we can say that P is interior to $\angle CAB$ if $\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 $\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.

**iknowone** · March 7th 2008, 08:46 AM

$<br /> \vec {AB}<br />$

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

This can be written in component form:

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

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

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

It shouldn't take too much convincing to see that if the above is satisfied for at least 2 of the following: $\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.

**angel.white** · March 7th 2008, 12:20 PM

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

     read in triangle from file

     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
          skip to next triangle
     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
          add one to the count
     END IF

     IF ac x-int > 0 > ab x-int
          add 1 to the count
     END IF

END LOOP

DISPLAY value of count

**angel.white** · March 7th 2008, 01:17 PM

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

**sathishdip** · March 14th 2010, 08:46 AM

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

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

LinkBack

Thread Tools

Display

Determine if a point lies within area of a triangle

Best and Worst

access the co ordinates of the triangle

Similar Math Help Forum Discussions

determine equilateral triangle's length using a point from the inside

point lies closest ot the y axis

Area of equilateral triangle given known distances of a point from the sides.

Finding if a point lies on a line between 2 others

given area of triangle determine value of sin C.

Search Tags