點對多邊形位置檢測的穩定串行最優與并行的算法

摘 要：點相對于多邊形位置檢測是計算機圖形學中的一個底層而基本的問題，目前的算法較多，但這些算法要么復雜，要么不穩定，都或多或少存在一些問題。為改進算法，首先從分析直線的正負性入手，進一步全面描述了點與有向線段的各種相互位置關系及相應的處理步驟。借助于正負性，不僅簡化了點與有向線段的位置判斷，降低了算法復雜性，更徹底消除了各種不穩定的因素。算法處理如此的精細也保證了算法的可并行性，實現了串、并行算法。實驗證明，串行算法是一個穩定的最優算法。

關鍵詞：點； 多邊形； 檢測； 正負性； 復雜性； 串行； 并行； 算法

中圖分類號：TP3917

文獻標志碼：A文章編號：10013695(2010)04134207doi:10.3969/j.issn.10013695.2010.04.037