Algorithm tests for point location
Lawrence Arendt, Manitoba HVDC Research Centre, Winnipeg, Canada -- EDN, August 3, 2000
A recent software project approximated the phase-space trajectory (also known as a strange attractor) of a certain dynamic system by using several nonoverlapping triangles. It became necessary to determine whether particular operating points were on or off that attractor. Determining whether a circle or a rectangle contains a point is trivial. A circle centered at point C and having a radius R contains a point P(x,y) only if ||CP||1,y1) and D(x2,y2) contains a point P(x,y) only if x12 and y12. However, it is not such a trivial task to determine whether triangle ABC, which has vertices A(x1,y1), B(x2,y2), and C(x3,y3), contains point P(x,y) (Figure 1). You can simplify the task by calculating the triangle's area using the formula:
where P1, P2, and P3 are the vertices. If you use the absolute value of the determinant, you need not be concerned whether P1P2P3 are labeled in a counterclockwise fashion. To determine whether ABC contains P, calculate the area of ABC using Equation 1 and then define three new triangles, each having as its vertices point P and two vertices of ABC.
This operation results in three unique triangles: ABP, BCP, and CAP. You can then calculate the areas of triangles ABP, BCP, and CAP. If ABC contains P (Figure 2), then Area (ABP)+Area (BCP)+Area (CAP)=Area (ABC). If ABC does not contain P (Figure 3), then Area (ABP)+Area (BCP)+Area(CAP)>Area (ABC).
The beauty of the algorithm in Listing 1 is that you need no squares, square roots, or trigonometric functions. You can extend the methodology to triangles in 3-D space. You can also adapt it for finding the area of irregular-shaped polygons. The C++ program in Listing 1 is for a TTriangle class having a Contains(...) function similar to that of the Windows TRect class. TFPoint is the floating-point equivalent of the integer TPoint class. (DI #2566)
