An Algorithm for Judging Points Inside or Outside a Polygon

摘要

There are massive classic algorithms determining whether points are inside or outside of a polygon, such as Ray Casting, Cross Product Judging and Angle-judging, whereas these algorithms require discussing various kinds of special circumstances, or the determination needs transformation into other algorithms, which are inefficient and unstable. According to the knowledge of elementary geometry and graph theory, this article suggests a new algorithm, by using the method of drawing a vertical line through the point under judgment and judging the point with the method of substitution and then marking a variable. This algorithm requires neither discussing special circumstances, nor performing division operations, therefore the efficiency and stability of it is significantly increased. Many cases have proved that the efficiency of this algorithm is about 9.5 to 9.8 times of the classical ray algorithm.