%0 Journal Article
%T 基于凸剖分的点在多边形内的高效判定
%A 李静
%A 王文成
%A 吴恩华
%J 自然科学进展
%D 2007
%I 
%X 提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.
%K 点
%K 多边形
%K 包容性检测
%K 加速
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=01BA20E8BA813E1908F3698710BBFEFEE816345F465FEBA5&cid=96E6E851B5104576C2DD9FC1FBCB69EF&jid=504AF8C1E5476CA7C4EC9DF6FEAC14AC&aid=6E9D5FE2F91B161D&yid=A732AF04DDA03BB3&vid=BCA2697F357F2001&iid=DF92D298D3FF1E6E&sid=342E193BAB6B28C5&eid=E5E53C81AEB35E6C&journal_id=1002-008X&journal_name=自然科学进展&referenced_num=0&reference_num=14