Sweeping an implicit 2d curve

Let $\mathcal{C}$ be a planar implicit curve defined by a polynomial equation $f (x, y) = 0$, where $f \in \mathbbm{Q}[x, y]$. We are going to describe an algorithm, which outputs a graph of points in the plane, \ isotopic to the curve $\mathcal{C}$, and with the following properties:

The method which is described here belongs to the family of sweeping algorithms, also related to Morse functions and critical values. It proceeds as follows:

Let us assume that the sweeping direction that we have choosen is the $x$-axis. Then the topology of $L_{x_0} \cap \mathcal{C}$ (where $L_x$ is the line orthogonal to the $x$-axis through the point $(x, 0)$) changes, when $L_{x_0} \cap \mathcal{C}$ contains multiple points, that is when

\[ f (x, y) = 0, \partial_y f (x, y) = 0 \]

has a real solution.

The corresponding $x$-coordinates of these points satisfies $\tmop{res}_y (f, \partial_y f) (x) = r (x) = 0$. We solve this equation. Let $\alpha_1 < \cdots < \alpha_s$ be the real roots of $r (x) = 0$. For each $\alpha_i$, we \ compute the corresponding $y$ such that $f (\alpha_i, y) = 0$. At this point, we also check that the curve is in generic position, that is, there is at most one multiple solution of $f (\alpha_i, y) = 0$.

Once these points are computed, we compute intermediate (rational) points $\mu_0 < \mu_1 < \cdots < \mu_s$, such that $\mu_{i - 1} < \alpha < \mu_i$ and the corresponding $y$ such that $f (\alpha_i, y) = 0$.

All these points are collected and sorted by lexicographic order such that $x > y$. The subset of points, corresponding to two consecutive $x$-coordinates are connected, according to their $y$-coordinates, in the order described below:



void topology::assign(topology::point_graph<C>& g, 
                      const MPol<U>& p,TopSweep2d<C,SLV> mth);

This class provides following definition and static function:



#include <cstdio>
#include <synaps/arithm/gmp.h>
#include <synaps/topology/TopSweep2d.h>

int main(int argc, char** argv) 
  const char * exemples[] = { 
  for ( int i = 0; i < 2; i ++ )
      std::cout << i << std::endl;
      MPol<QQ> p(exemples[i], Variables("x y"));
      topology::point_graph<double> g;
      topology::assign(g, p, TopSweep2d<double>());
      char file[200];
      geomview::ostream vw(file);
  return 0;

Here is the graph,which is computed: