Point- in- Polygon Test Based on the 4*4 Determinant Method.
Lin Lou, Norimasa Yoshida, Hiroaki Hanamitsu, Fujio Yamaguchi · Journal of the Japan Society for Precision Engineering · 1996
The point-in-polygon test is one of the most fundamental geometric tests and appears very frequently in computer graphics and geometric modeling. The algorithms based on parity counting for this test, are widely being used and have been discussed in many papers. However, geometric and numerical problems still remain in many of those algorithms. In this paper, a new algorithm based on parity counting is presented for the point-in-polygon test, By using a sign correction technique and exact integer arithmetic, both geometric and numerical problems have been improved. Finally, the efficiency of the algorithm is discussed. All of the processing in the algorithm is based on the 4 × 4 determinant method.