# 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.