Post a Comment
Algorithm tests for point location
Lawrence Arendt, Manitoba HVDC Research Centre, Winnipeg, Canada -- EDN, 8/3/2000
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)
