MAPC: A library for efficient and exact manipulation of algebraic points and curves Academic Article uri icon

abstract

  • We present MAPC, a library for exact representation of geometric objects - specifically points and algebraic curves in the plane. Our library makes use of several new algorithms, which we present here, including methods for finding the sign of a determinant, finding intersections between two curves, and breaking a curve into monotonic segments. These algorithms are used to speed up the underlying computations. The library provides C++ classes that can be used to easily instantiate, manipulate, and perform queries on points and curves in the plane. The point classes can be used to represent points known in a variety of ways (e.g. as exact rational coordinates or algebraic numbers) in a unified manner. The curve class can be used to represent a portion of an algebraic curve. We have used MAPC for applications dealing with algebraic points and curves, including sorting points along a curve, computing arrangement of curves, medial axis computations, and boundary evaluation on curved primitives. As compared to earlier algorithms and implementations utilizing exact arithmetic, our library is able to achieve more than an order of magnitude improvement in performance.

author list (cited authors)

  • Keyser, J., Culver, T., Manocha, D., & Krishnan, S.

publication date

  • January 1999