Point Inside or Outside Triangle?Date: 08/02/2001 at 03:52:00 From: Natalie Subject: Is the point inside of triangle I have a problem how to find out if a point is inside or outside of a triangle. I have coordinates of three vertices of a triangle and coordinates of the point that I have to check. Let's say: point A(200,300) point B(300,500) point C(100,500) and the point for checking is D(200,350) How can I know if D is inside the triangle or not? A / \ / \ / D \ /_______\ C B Date: 08/02/2001 at 17:00:01 From: Doctor Rick Subject: Re: Is the point inside of triangle Hi, Natalie. I went to our Search Dr. Math page, http://mathforum.org/mathgrepform.html and searched for the words point inside triangle . You can do this too. I found a lot of irrelevant pages, but I also found these: Point inside a Triangle http://mathforum.org/dr.math/problems/bob.07.15.01.html Point Inside Triangle http://mathforum.org/dr.math/problems/point.inside.triangle.html Formula for Point in Rectangle http://mathforum.org/dr.math/problems/scott5.31.96.html I'll give you an idea of my own, which you may find helpful if you are familiar with vectors. (If not, you could just take my word that the formula below works. Of course, you'll test it to be sure I didn't type something wrong, and let me know if I did.) I will assume, for the moment, that the points A, B, and C are in clockwise order around the triangle. If you look along AB from A toward B, all points inside the triangle are on your right. Likewise as you look along BC from B toward C, all interior points are on your right; and the same for CA. One way to calculate which side of the line a point is on is to take the vector product or cross-product of two vectors. In particular, construct the vectors B-A and D-A. I'll do this in three dimensions. B-A = (x_b-x_a, y_b-y_a, 0) D-A = (x_d-x_a, y_d-y_a, 0) The cross-product of vectors (x_1, y_1, x_1) and (x_2, y_2, y_2) is (y_1*z_2-z_1*y_2, z_1*x_2-x_1*z_2, x_1*y_2-y_1*x_2) The cross product of two vectors is perpendicular to both vectors. Its direction follows the right-hand rule: if the second vector is to the left of the first (looking from above), then the cross product points up. Let's take the cross product (D-A)x(B-A). The x and y components are zero; the vector points either up (z component is positive) or down (z component is negative) depending on whether B-A is to the left or right of D-A. Thus the sign of the z component of the cross product tells us what we need: z_ab = (x_d-x_a)*(y_b-y_a)-(y_d-y_a)*(x_b-x_a) If z_ab > 0 then D is on the "inside" side of AB. If you do the same replacing AB with CB and then CA, and each time z is negative, then D is inside the triangle. What if you don't know whether the vertices of the triangle are in clockwise or counterclockwise order? Just change the condition: a point D is inside the triangle if EITHER all of z_ab, z_bc, and z_ca are positive, OR they are all negative. If the points are in clockwise order, as I assumed above, then there is no (exterior) point such that all the z's are negative, so we won't get spurious results due to the broader condition. The area method mentioned in two of the archived answers is essentially the same approach as mine, if you consider the derivation of the determinant formula for area used there. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/