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

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 .

**See also:**`synaps/topology/TopSbdBdg2d.h`

,`TopSbdBdg`

.

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