Following up two of my postings. Sorry, but I gave the wrong system of
equations in my first posting, and then solved that incorrect system
in my second. The system of equations should be
xa * a + xb * b + xc * c = xz
ya * a + yb * b + yc * c = yz
a + b + c = 1
Then the following are the expressions that are all the same sign if
the point is in the triangle:
expression_1 = xz * (yb - yc) + xb * (yc - yz) + xc * (yz - yb)
expression_2 = xa * (yz - yc) + xz * (yc - ya) + xc * (ya - yz)
expression_3 = xa * (yb - yz) + xb * (yz - ya) + xz * (ya - yb)
Sorry for the mistakes in the earlier posts.
Dave
On Sep 20, 3:17 pm, Dave <[email protected]> wrote:
> 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 <[email protected]> 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 <[email protected]> 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 -- 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
