基于点圆理论的2D/3D点包含高效判定

摘要

针对2D/3D点包含判定方法的复杂和低效问题,提出基于点圆理论的方法:分类描述奇异情形在点圆中的投影、叠加特征及判定方法,将3D点包含测试转换为与2D点包含测试一致的算法(除子平面方程系数计算外).筛选和累加与射线相交的射线以上或以下的线段,据此奇偶性判定3D或2D点包含;解析2D射线与多边形相交连续线段内节点的几何特征,即y坐标要么都大于、要么都小于测试点,构建高效2D点包含增量筛选射线法.实验结果表明所建2D/3D点包含方法高效、稳定,可用于处理任意奇异性,适合于任意多面体(流形、非流形、表面为平面或曲面等)或多边形.