基于拓扑映射的点集在凸多边形内外判断算法
DOI: 10.11834/jig.200304157
Keywords: 计算机图形学(520？6030),点,点集,多边形,拓扑映射,映射点,射影直线
Abstract:
通过拓扑映射，点在凸多边形内外的判别可以转化为映射点在射影直线上的位置关系问题.首先通过设置中心点，获取凸多边形各顶点的拓扑映射点，对于每个检测点，根据其映射点与顶点拓扑映射点的相对位置关系，即可确定检测点位于多边形哪条边的范围内;然后将检测点与该边进行包围盒测试，对于点在边包围盒外的情况，只需根据比较判别即可得到结果，对于点在边包围盒边界上或内部的情况，则需通过叉积运算进行判别.该方法几何意义清晰，实验结果表明，该算法运行可靠，对于单个点或多点组成的点集均有较高的检测速度.
| [1] | ［2］Feito F R, J C Torres. A Urena: Orientation, Simplicity, and inclusion test for planer polygons [J]. Computer& Graphics.1995, 19(4): 595～600.
|
| [2] | ［4］张树有,谭建荣,彭群生.基于拓扑映射的视图轮廓信息自动获取算法[J].中国图象图形学报,2001,6A(10):1016～1020.
|
| [3] | ［1］孙家广.计算机图形学[M](第3版).北京:清华大学出版社,2000:414～418.
|
| [4] | ［3］李维诗,李江雄,柯映林.平面多边形方向及内外点判断的新方法[J].计算机辅助设计与图形学学报,2000,12(6):405～407.
|
| [5] | ［5］吴春福,陆国栋,张树有.基于拓扑映射的多边形顶点凸凹判别算法[J].计算机辅助设计与图形学学报,2002,14(9):810～814.
|
Full-Text
