# Subdivision methods for implicit curves in 2D

In this section, we describe a subdivision method, for computing the topology of a curve , defined by an implicit equation , where . It uses the representation of polynomials in the Bernstein basis of a domain :

where is the Bernstein basis in degree , on the interval . The polynomial will be represented by its control coefficients and the domain . It can be subdivided by applying the de Casteljau algorithm, in the and direction.

The subdivision algorithm is based on a criterion for detecting the regularity of the curve , in the domain .

 Definition: We say that a domain is regular for , if its topology in is uniquely determined from the intersection points of , with the boundary of .

Here is a property that we use to detect regular domains:

 Proposition: If (resp. ) in , then is regular for .

The test is implemented by checking that the control coefficients of or on D have a constant sign, which implies the previous proposition.

 Algorithm: Subdivision algorithm for implicit curves. input: defining the implicit curves and a domain . Initialize with ; while ; pick a domain in and test if it is regular; if is not regular not subdivide it and add the subdomains to ; otherwise, connect the points on to get the topology of in ; output: a graph of points connected by segments, isotopic to .

## Implementation

void topology::assign(point_graph<C> & g, MPol<QQ>& p,
TopSbdBdg2d<C> mth,
C x0, C x1, C y0, C y1);


• This function computes a graph of points g of type topology::point_graph<C>, which is isotopic to the curve defined by the polynomial p, in the box . The coordinates of the points in g are of type C. The implementation is designed for C=double.
• The input coefficients of p are rational numbers. During the computation, they are rounded to double number types. If the topology in the box can be certified from this approximation, a graph of points connecting the intersection of the curve with the boundary of is computed. Otherwise the box is subdivided into subboxes and the test is applied recursively.
• If the curve has singular points, the subdivision will continue until the size of the box is smaller than the precision specified by the class TopSbdBdg2d<C>. The default value is .
synaps/topology/TopSbdBdg2d.h, TopSbdBdg.

## Example

#include <synaps/topology/TopSbdBdg2d.h>

int main(int argc, char** argv)
{
MPol<QQ> p("x^6+3*x^4*y^2+3*x^2*y^4+y^6-4x^2*y^2");
topology::point_graph<double> g;
topology::assign(g, p, TopSbdBdg2d<double>(),
-2., 2.1, -2.2, 2., 2);
}


Here is a picture of such output:

SYNAPS DOCUMENTATION