4×4 行列式法によるポリゴンに対する点の内外判定アルゴリズムの比較

概要

論文の詳細を見る
Point-in-Polygon Tests are basic geometric algorithms in solid modeling. The 4×4 Determinant Method provides a structured framework for all interference problems in the modeling process. The authors have proposed two different algorithms for Point-in-Polygon Tests based on the 4×4 Determinant Method, the PNZ Triangle Method and the Vertex Convexity Method. This paper compares the (1) algorithm simplicity, (2) arithmetic operations per vertex, (3) pre-calculable date, (4) accuracy in floating point arithmetic, (5) applicability in special cases, and (6) applicability in faces with curved edges, of the two algorithms. This shows which algorithm is preferable in each situation, and which algorithm is suitable for implementation in a hardware geometric processor.
公益社団法人精密工学会の論文
1990-07-05