Results 1 to 10 of 10

Math Help - Determine if a point lies within area of a triangle

  1. #1
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    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.
    Attached Thumbnails Attached Thumbnails Determine if a point lies within area of a triangle-point-triangle.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2008
    Posts
    148
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member wingless's Avatar
    Joined
    Dec 2007
    From
    Istanbul
    Posts
    585
    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.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,662
    Thanks
    1616
    Awards
    1
    Quote Originally Posted by angel.white View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Thank you everybody, I appreciate the help.
    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2008
    Posts
    148

    Best and Worst

    <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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    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
    Attached Thumbnails Attached Thumbnails Determine if a point lies within area of a triangle-p102.jpg  
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Mar 2010
    Posts
    1

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 7th 2010, 01:57 AM
  2. point lies closest ot the y axis
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 3rd 2010, 07:03 AM
  3. Replies: 3
    Last Post: October 29th 2009, 07:53 AM
  4. Replies: 2
    Last Post: November 21st 2008, 03:30 AM
  5. given area of triangle determine value of sin C.
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: July 19th 2008, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum