Inside-polygon algorithm for curvilinear contours. Design and lmplementation

Abstract

This paper describes an algorithm to determine whether a point is inside or outside a curvilinear polygon, based on the well known algorithm consisting of counting the intersections of an horizontal ray with the polygon. Curvilinear polygons. as analytic resources. are not common in computer graphics, but they do arise on sorne domains. Normally, parametric curves, such as cubic splines or beziers, are used to model curves in graphic applications. But parametric curves cannot be easily manipulated in analytic computations. For example, obtaining a curve parallel to another is not a simple task, and is not even possible under all circumstances. For this reason, sorne computational geometry applications use non-parametric polyline curves, formed by straight-Iine segments and circular arcs. The straightforward geometry of lines and circumferences makes it easy to develop complex algorithms to work with nonparametric curves. But despite the fact that this curves are easy to treat analytically, they lack the parametric benefits of c1assical curves; and for this reason, it is very hard to find in the literature any work about them. If we are to represent curvilinear polygons using patches of straight-line segments and circular arcs, named polyline curvilinear polygons, one ofthe fundamental óperations that we need to implement is the point-in-polygon test. Haven't been able to find any such algorithm. the author adapted the c1assical method used with straight-Iine polygons, and extended it for use with polyline curves.