基于单调性与相关边的多边形内外点判断算法

李基拓; 陆国栋; 冯星

doi:10.11834/jig.200206199

学术论文与技术报告 | 浏览量 : 0 下载量: 442 CSCD: 0

PDF
导出
分享
收藏
专辑

基于单调性与相关边的多边形内外点判断算法
A New Algorithm of Point in-out Polygon Test Based on Monotonicity and Correlative Edges
2002年7卷第6期页码：595
纸质出版：2002
DOI： 10.11834/jig.200206199
稿件说明：

移动端阅览

李基拓, 陆国栋, 冯星. 基于单调性与相关边的多边形内外点判断算法[J]. 中国图象图形学报, 2002,7(6):595. DOI： 10.11834/jig.200206199.

A New Algorithm of Point in-out Polygon Test Based on Monotonicity and Correlative Edges[J]. Journal of Image and Graphics, 2002, 7(6): 595. DOI： 10.11834/jig.200206199.

摘要

为了充分挖掘多边形边的基本性质——单调性，基于检测点与多边形边之间的坐标关系，提出了相关边的概念及一种判断点在多边形内外的新算法。综合运用单调性与相关边技术，将点与我边形之间的位置关系转化为点与茯相关边之间的位置关系，从而尽可能地避免了叉积运算，且无需求交运算，从根本上提高了算法的效率，同时新算法还简单有效地解决了射线法中的临界位置问题。程序验证表明，新算法易于实现，适用于简单多边形，具有运行速度快、稳定性高等优点。

Abstract

Point in-out polygon test is one of the fundamental issues in Computer graphics. In this paper

the fundamental characteristic of the polygon edges-monotonicity is utilized sufficiently. According to the coordinate relations between the points and the edges

the conception of correlative edges is proposed. By integrating monotonicity with correlative edges

a new algorithm of point in-out polygon is put forward. The new algorithm transforms the relationship between a point and a polygon into that between a point and its correlative edges. The operations of intersection are avoided

and the operations of cross product are reduced as far as possible. The efficiency of the algorithm is raised radically. It is proved simply and effectively when the points are at critical positions. Software implementation verifies the high robustness and efficiency of the new algorithm.