Exploring 2D arrangements of implicit algebraic curves using Xalci web-demo
max planck institut
informatik
mpii logoMinerva of the Max Planck Society
Efficient and Exact Algorithms for Curves and Surfaces

Computational Geometry Algorithms Library

Algorithms for Complex Shapes
Locations of visitors to this page
 

Xalci web demo is a web-based application with Macromedia Flash client interface which allows everyone to analyse the topology of algebraic curves and visualize the arrangements of such curves. A real plane algebraic curve is a zero set of a bivariate polynomial f(x,y). These curves split the plane into 0-, 1- and 2-dimensional components, called vertices, arcs and facets of an arrangement. Our software provides a detailed information on an arrangement and allows to interactively explore it by zooming at certain locations or selecting individual features. Xalci can be used for demonstrative and educational purposes. See also our video presentation at SoCG'08. For more information on planar arrangements, see CGAL manual.

Our software

Xalci was developed within Geometric Computing and Computer Algebra group at Max-Planck Insitute for Informatics. A major part of our software has evolved from the former Exacus project (Efficient and Exact Algorithms for Curves and Surfaces) which has later become a part of CGAL. Cgal is a large Open Source software library providing various geometric algorithms designed according to generic programming paradigm as it is widely known from STL. Particularly, we have contributed to a number of Cgal packages including Bivariate Algebraic Kernel for manipulations with algebraic curves and Curved Kernel via Analysis which provides an interface to Arrangements package. CGAL Arrangements is a generic implementation of Bentley-Ottmann sweep-line algorithm which allows us to compute an arrangement of various geometric objects.

Our main goal is to provide efficient, exact (in mathematical sense) and complete (handling highly degenerate cases) algorithms and implementations for various-degree non-linear geometry. Using our software one can compute the arrangements of arbitrary-degree algebraic curves in the plane and embedded on two-dimensional parametric surfaces. We also support boolean operations on polygons bounded by such curve arcs. Our algorithms can handle all degeneracies, such as singularities and intersections of high multiplicity; efficiency is guaranteed through the use of various filtering techniques to avoid expensive computations in many cases (modular filters, floating point filters) and special handling for fixed-degree algebraic curves. Additionally, we utilize the modern graphics hardware to dramatically reduce the cost of expensive symbolic arithemtic.

A table below shows Xalci's software hierarchy starting from the third-party libraries in the bottom (providing various data structures, exact number types, graphics support, etc.) all the way up to the generic arrangements algorithm from Cgal. Note that, the distinction between middle-level libraries (ConiX, CubiX, QuadriX and AlciX) providing the analyses of conics, cubics, projected quadrics and arbitrary-degree algebraic curves is merely kept for historical reasons as it used to be in Exacus. The major part of this functionality has been subsumed by Bivariate algebraic kernel.

CGAL Arrangements
Curved Kernel via Analysis

ConiX (CnX)
CubiX (CbX)
QuadriX (QdX)
AlciX (AcX)
Bivariate Algebraic Kernel
Univariate Algebraic Kernel (Real Solve)
Cgal library support
Stl Boost Gmp Mpfr Mpfi Ntl Qt

To compute and manipulate algebraic arrangements, we utilize the following algorithms:

  • Decomposition of the algebraic curves in a set of x-monotone arcs: In this step we perform geometric-topological analysis of each algebraic curve using a fast symbolic-numeric lifting method [2,3]. Our approach uses a novel validation procedure which favours low-precision number computations whenever possible and greatly reduces the overhead of expensive symbolic arithmetic. The output of the analysis is equivalent to the computation of a cylindrical algebraic decomposition (CAD) with adjacency information. A large portion of the software migrated from the previous approach used for curve and curve-pair analyses, see [4,5].

  • Arrangement computation of the curve arcs: We use a generic implementation of Bentley-Ottmann sweep-line algorithm offered by Cgal's Arrangements package. The geometric-topological analyses of a single algebraic curve and of a pair of curves are translated into geometric predicates on the curve arcs using Curved Kernel via Analysis package, see [1].

  • Visualization of the curve arcs of an arrangement: Our algorithm is based on the combination of curve tracing and local space subdivision methods, see [6,7]. It computes a geometrically-correct piecewise-linear approximation of a curve arc which lies within a fixed Hausdorff distance (pixel size) from the actual curve graph. Robustness of our method is guaranteed by an adaptive precision model such that the majority of algebraic curves can be handled using only low-precision floating-point computations while exact arithemtic is employed in tough cases.

    • All the subalgorithms mentioned above guarantee the correctness of the computed results such that resulting plot provides a mathematically true picture of the arrangement. We are also planning to integrate the graphics hardware support to further reduce the impact of expensive symbolic computations.

    References:

    1. E. Berberich, P. Emeliyanenko: CGAL's Curved Kernel via Analysis, Algorithms for Complex Shapes, MPI für Informatik, ACS-TR-123203-04, Technical Report, 2008

    2. E. Berberich, P. Emeliyanenko, A. Kobel, M. Sagraloff: Arrangement Computation for Planar Algebraic Curves. In SNC '11, San Jose, California, 2011

    3. E. Berberich, P. Emeliyanenko, M. Sagraloff: An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks. In ALENEX '11, pages 35-47. SIAM, 2011

    4. A. Eigenwillig, M. Kerber, N. Wolpert: Fast and Exact Geometric Analysis of Real Algebraic Plane Curves. In ISSAC '07, pages 151-158. New York, NY, USA, 2008. ACM

    5. A. Eigenwillig, M. Kerber: Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves. In SODA '08, pages 122-131. SIAM, Philadelphia, PA, USA

    6. P. Emeliyanenko, E. Berberich, M. Sagraloff: Visualizing Acrs of Implicit Algebraic Curves, Exactly and Fast. In ISVC '09, pages 608-619, Berlin, Heidelberg, 2009. Springer-Verlag

    7. P. Emeliyanenko, M. Kerber: Visualizing and Exploring Planar Algebraic Arrangements - a Web Application. In SCG '08, pages 224-225, video presentation. New York, NY, USA, 2008. ACM.



       PageRank Checking Icon   

    Max-Planck-Institut für Informatik, Geometric Computing Group