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 .
topology::point_graph<C>, which is isotopic to the curve defined by the polynomial
p, in the box . The coordinates of the points in
gare of type
C. The implementation is designed for
pare rational numbers. During the computation, they are rounded to
doublenumber 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.
TopSbdBdg2d<C>. The default value is .
Here is a picture of such output: