A ROBUST POINT INCLUSION ALGORITHM FOR REGIONS BOUNDED BY PARAMETRIC CURVE SEGMENTS

Classifying a point with respect to a closed planar region is a freque ntly encountered problem in the field of geometric computing. One of t he most popular techniques is the parity count method in which a semi- infinite ray originating from a given test point is intersected with t he boundary of a region. An odd number of intersections indicates that the point is inside the region. While this method can be applied to r egions bounded by complex curves, most reported work mainly confines t he boundary of a region to be composed of straight lines, circular-are a, or parabolic splines. Owing to rounding errors in floating point co mputation, mis-located intersections between a ray and the boundary ma y lead to incorrect results. For regions bounded by complex curve segm ents, solutions to high order polynomial equations are usually require d. The effect of rounding error is thus more apparent and may cause se rious inconsistency such that a test point well within a region may be classified as outside the region. This paper presents an algorithm fo r classifying a point with respect to a region bounded by a series of piecewise continuous linear, quadratic, or cubic parametric curve segm ents. Techniques for handling special cases when the test ray passes t hrough the end point of a curve segment will be discussed. The robust point inclusion test is attained through the use of a tolerance zone a ssociated with each end point of a curve segment. The size of the tole rance zone depends on the segment representation error and the ray-seg ment intersection error. A method for estimating these errors and the size of the tolerance zone will also be discussed. (C) 1997 Elsevier S cience Ltd.