基于斜率的多边形内外点快速判别算法

计算机与现代化 ›› 2013, Vol. 1 ›› Issue (1): 53-56.doi:

基于斜率的多边形内外点快速判别算法

洪志强

江苏科技大学计算机科学与工程学院，江苏镇江212003

收稿日期:2012-09-25 修回日期:1900-01-01 出版日期:2013-02-06 发布日期:2013-02-06

A Fast Test Algorithm to Point in Polygon Based on Slope

HONG Zhiqiang

College of Computer Science and Engineering， Jiangsu University of Science and Technology， Zhenjiang 212003， China

Received:2012-09-25 Revised:1900-01-01 Online:2013-02-06 Published:2013-02-06

摘要/Abstract

摘要：

多边形的内外点判别是图形学的一个基础算法，为了更大限度地降低其算法复杂度和运算量，提出一种基于斜率的点与多边形位置关系的快速判别法。该方法只需计算该点到多边形各顶点的斜率，然后与多边形各顶点的邻边的斜率进行比较，即可对多边形的内外点快速做出判别。该算法无需复杂的点乘、叉乘、求交、三角函数等运算，在判别过程中仅需平均2n次减法运算和n/2次的除法运算，以及一些比较运算，即可对简单n多边形的内外点做出判别。经测试，该算法快速有效。



关键词: 关键词：计算机图形, 斜率, 简单多边形, 内外点判别

Abstract:

To detect if a point in the polygon or not is a basic algorithm in computer graphics, in order to simplify the algorithm complexity， a new method is proposed here which can produce the result fast simply by computing the slope of the line connected from the point to each point of the polygon， and then compare each of the slop to the edges. Within this algorithm， there is no sophisticated computation， such as dot， cross， intersect， triangle algorithms etc and， merely has 2n times of subtract operate， n/2 times of division， and some simple compare operate in average， hence the result of the point if in an n edges polygon can be produced. Finally， tests suggest that this algorithm is fast and efficient.



Key words: Key words: computer graphics, slope, simple polygon, point in polygon test

洪志强. 基于斜率的多边形内外点快速判别算法[J]. 计算机与现代化, 2013, 1(1): 53-56.

HONG Zhiqiang. A Fast Test Algorithm to Point in Polygon Based on Slope[J]. Computer and Modernization, 2013, 1(1): 53-56.