Following up on my own posting, if these three expressions all have the same sign, the point is in the triangle. If any of them is zero, the point is on the boundary, and if any of them have opposite signs, then the point is not in the triangle:
expression_1 = xz * yb - xb * yz + xb - xz + yz - yb expression_2 = xa * yz - xz * ya + xz - xa + ya - yz expression_3 = xa * (yb - yz) + xb * (yz - ya) + xz * (ya - yb) These expressions are the numerators that result when solving the three equations in my previous posting by Cramer's Rule. There is no reason to calculate the denominator and divide; if the triangle really is a triangle (i.e., if the three points of the triangle are not collinear), then the denominator is nonzero. At least one of the numerators has to have the same sign as the denominator, since otherwise all solution unknowns would be negative but they sum to 1. If any numerator is of the opposite sign, then the corresponding solution unknown is negative, indicating that the point is not in the triangle. Dave On Sep 20, 12:27 pm, Dave <dave_and_da...@juno.com> wrote: > Use Barycentric Coordinates: Let the point A have coordinates (xa, > ya), and similar for points B, C, and Z. Solve the system of linear > equations > > xa * a + xb * b + c = xz > ya * a + yb * b + c = yz > a + b + c = 1 > > for a, b, and c. If all of a, b, and c are >= 0, the point is in the > triangle (> 0) or on the boundary (= 0). Otherwise, the point is > outside the triangle. > > Dave > > On Sep 20, 10:02 am, umesh <umesh1...@gmail.com> wrote: > > > > > Initially we have given three point A , B, C in plane represent three > > nodes of triangle, now given another point Z which lies in same > > plane, find out whether that point lies on/inside the triangle or > > outside of triangle....try to get in minimum time and space > > complexity > > > -- > > Thanks & Regards > > > Umesh kewat- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
