ICS Theory Group

ICS 269, Spring 1997: Theory Seminar


17 October 1997:
Two Dimensional Set Membership Classification Revisited: Winding Number Versus Ray Firing
Mac Casale, ICS, UC Irvine

Testing a point for containment within a set bounded by a Jordan curve is fundamental to many geometry based applications. The common approach is to fire a ray from the point and count the number of intersections with the boundary curve. The point is contained if the number of intersections is odd. We present certain difficulties that occur with this approach, which are due to tolerancing issues, and present an alternative, based on the winding number, which is a tool from the theory of functions of complex variables. It is shown that for points far from the boundary, the winding number calculation is highly reliable, but that difficulties arise, using standard integration methods, near the boundary due to the singular nature of the integrand. Methods for dealing with the difficulties, borrowing ideas from generalized function theory, appear to lead to a robust implementation. It is suggested that integral equation methods may become an important tool in the toolchest of computational geometers in the years to come.