A BSP-Based Algorithm for Dimensionally Nonhomogeneous Planar Implicit Curves with Topological Guarantees

摘要

Mathematical systems (e.g., Mathematica, Maple, Matlab, and DPGraph) easily plot planar algebraic curves implicitly defined by polynomial functions. However, these systems, and most algorithms found in the literature, cannot draw many implicit curves correctly; in particular, those with singularities (self-intersections, cusps, and isolated points). They do not detect sign-invariant components either, because they use numerical methods based on the Bolzano corollary, that is, they assume that the curve-describing function f flips sign somewhere in a line segment AB that crosses the curve, or f(A). f(B) < 0. To solve these problems, we have generalized the False Position (FP) method to determine two types of zeros: (ⅰ) crossing zeros and (ⅱ) extremal zeros (local minima and maxima without function sign variation). We have called this method the Generalized False Position (GFP) method. It allows us to sample an implicit curve against the Binary Space Partitioning (BSP), say bisection lines, of a rectangular region of IK2. Interestingly, the GFP method can also be used to determine isolated points of the curve. The result is a general algorithm for sampling and rendering planar implicit curves with topological guarantees.