robert@slipknot.rain.com.UUCP (Robert Reed) writes:

The standard edge crossing test, which works for any other polygon, should work fine here. See page 34, Foley and van Dam Computer Graphics. In brief you count the number of polygon edges that cross a ray drawn from the point to infinity. An odd number of crossings means the point is interior.

orourke@sophia.smith.edu (Joseph O'Rourke) writes:

Although this is a matter of taste, I find this inferior to the algorithm that I use, which tests if the point is left-of-or-on the three directed lines determined by pairs of vertices of the triangle. In the edge crossing code, one must deal with the ray crossing a vertex, being parallel to an edge, being collinear with an edge:

                               /\
                              /  \
                             /    \
                        *---+------+------>

Coding these special cases requires care. The other method has no no comparable special cases. But all methods, as someone else pointed out, are subject to tricky precision issues, because coordinates are multiplied.

A fail-proof method is to compute the barycentric coordinates. For a triangle {(x1,y1), (x2,y2), (x3,y3)} and some point (x0,y0), calculate

b0 =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
b1 = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0 
b2 = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
b3 = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0 

Then if b1, b2, and b3 are all > 0, (x0,y0) is strictly inside the triangle; if bi = 0 and the other two coordinates are positive, (x0,y0) lies on the edge opposite (xi,yi); if bi and bj = 0, (x0,y0) lies on (xk,yk); if bi < 0, (x0,y0) lies outside the edge opposite (xi,yi); if all three coordinates are negative, something else is wrong. This method does not depend on the cyclic order of the vertices.

lis@iss.nus.sg (Ik Soo Lim) writes:

Is there anyone willing to explain Barycentric Coordinates or references on the topic?

Here's the simplified version:

Given three (non-colinear) points A,B,C, the "barycentric coordinates" of a point P with respect to A,B,C are u,v,w, such that:

    P = u*A + v*B + w*C
    1.0 = u+v+w

Note that u,v,w can (separately) be <0, or >1. However, if the point P is *inside* the triangle ABC, then:

    0.0 <= u,v,w <= 1.0

All points in the 2D plane can be uniquely represented by [u,v,w], with respect to ABC. So...you can think of ABC as a "coordinate system"

One common use for barycentric coordinates is to warp the 2D plane by computing [u,v,w] with respect to ABC, and then re-generating the point with respect to DEF. Everything that you know about transforming from one Cartesian coordinate system to another carries over to barycentric coordinates.

Another common use is to exploit the relationships between special values (0.0 or 1.0, for example) of u,v,w and the triangle ABC. For example, if u = 0.0, then P lies ON the line containing B and C. (since u = 0, then the location of the point P does not depend at all on the location of A).

But...how do you compute u,v,w with respect to ABC? A nice way to visualize it, and a perfectly good way to do the computation, is shown below:

                            C

                     

                           P



                A                    B

Let |ABC| = area of the triangle ABC - or something proportional to the area.

         |BCP|       |CAP|                    |ABP|
Then u = -----,  v = -----, w = 1.0 - u - v = -----  
         |ABC|       |ABC|                    |ABC|

Hmmm "something proportional to the area of triangle ABC. How about:

   |ABC| = (B-A) x (C-A), where 'x' is the "2D cross-product"

In 2D, the cross-product is a scalar = 2*Area(ABC).

If your triangle is "clockwise" instead of "counter-clockwise", then the cross-product can be negative. That's just fine, as long as you are consistent. Everything is defined in terms of the "rotation sense" of ABC. Note that when P is outside ABC, then the orientation of ABC will differ from the orientation of one (or two) of the triangles involving P. That gives a negative u,v, or w - no problem, that's just peachy-keen.

That should do for starters...