Test for Point Inside TriangleDate: Fri, 4 Nov 1994 16:08:30 +0000 (TST) From: Boonchai Techaumnat Subject: Geometry Problem I have one geometry problem and want a simple solution that can be solved by computer program -- numerically -- with good resolution. The Problem: How can I know whether a point P(x,y) is in a triangle with vertices P1(x1,y1), P2(x2,y2), and P3(x3,y3)? Thanks for any help Boonchai T. Date: Fri, 4 Nov 1994 08:24:14 +0900 X-Sender: mpatter1@cc.swarthmore.edu Hi Boonchai! Thanks for writing to us. This is a good question. It sounds like a fun project. What language are you planning to write the program in? Here are some tips to get started: 1) Using the coordinates of the points, compute the equations of the lines containing the sides of the triangle. 2) Draw a triangle and label each side, l1, l2, and l3. (The l stands for line.) If a point is in the interior of the triangle, what has to be true about its relationship to the three lines? (Hint: think less than or greater than) 3) More specifically, think of the lines in terms of three pairs. Given any pair, what is the relationship between the point and the two lines of the pair? 4) Now, when you have some ideas, check to make sure that a point that is exterior to the triangle does not pass your tests for interior points. I hope this helps. I (and the other math doctors too) would love to hear about the solution you come up with. Please write back if you have questions about this response or some other topic. -Margaret, Math Doctor on call Date: Sun, 6 Nov 1994 14:19:12 +0000 (TST) From: Boonchai Techaumnat No, it's not fun, but my serious project. I will use C++ to solve this problem. From (3) I thought that if a point is in the triangle, it must be in the angle range of all 3 pairs. This gives me a solution for my problem! Thanks a lot, but I don't get anything from (2). Can you make it clearer? It may point to an alternate solution. Thanks, Boonchai T. Date: Mon, 7 Nov 1994 01:04:27 +0900 X-Sender: mpatter1@cc.swarthmore.edu Hi again. I am glad that you have a solution. The solution that I had in mind when I wrote tip #2 was to find the equations for each line and then compare the point P to those lines. I had thought that for each pair the point must be less than one of the lines and greater than the other, but now that I draw it out on my scratch paper, I don't think that it would always be true (like in the case of an obtuse triangle). So, your idea sounds good. -Margaret Date: Mon, 10 Mar 1997 From: Subject: Solution to an old problem Hello Doctors! Here is an alternate solution to this problem: How can I know whether a point P(x,y) is in a triangle with vertices P1(x1,y1), P2(x2,y2), and P3(x3,y3)? There are two possibilities: 1. P is INSIDE or ON, 2. P is OUTSIDE triangle P1P2P3. If you draw a sketch and consider triangles, PP1P2, PP2P3, PP3P1 You will notice the following relationship in their areas. If P is ON or INSIDE, A(PP1P2) + A(PP2P3) + A(PP3P1) = A(P1P2P3) If P is OUTSIDE then, A(PP1P2) + A(PP2P3) + A(PP3P1) > A(P1P2P3) Area of a triangle can be found using the determinant: A = abs(1/2 * |x1 y1 1| ) |x2 y2 1| |x3 y3 1| You can write a function in C++ that accepts the three points (as Classes) or their coordinates and returns the area. Finally if you have to distinguish between ON and INSIDE, put the point in the equations of the three lines that form the sides. If one of them is satisfied, P is ON a side. If two are satisfied, P is a vertex of the triangle. - Ujjwal Rane |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/