Optimal regular polygon inclusion in two-dimensional space for evaluating material nesting

Given a two-dimensional convex polygon with N vertices and a query point v , testing whether v is internal or external to the polygon is a fundamental problem, namely convex polygon inclusion problem, in computer graphics and computational geometry. An earlier algorithm for solving the convex polygon inclusion problem by Preparata and Shamos requires θ (log N ) time. This paper presents an O(log N ) time algorithm for solving the convex polygon inclusion problem and it also can reach O( 1 ) time for regular polygon inclusion problem. Experiments are carried out for arbitrary convex polygons to demonstrate the computational advantage of the proposed method.