SYNAPS (SYmbolic Numeric ApplicationS) » Geometry

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 points (or vertices of the graph) are on the curve $\mathcal{C}$ ,

they are connected by segments, which intersect only at these end-points.

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:

First, we choose a direction, and consider a virtual line orthogonal to this direction, sweeping the plane;

We detect at which critical position, the topology of the intersection of the line and the curve changes and compute the corresponding intersection points;

We compute the intersection points for sample lines in between these critical positions.

We connect the computed points by segments, in order to get a graph isotopic to $\mathcal{C}$ .

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:

Implementation

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

It computes a graph of points g (of type topology::point_graph<C>) which is isotopic to the curve $\mathcal{C}$ , defined by the polynomial p. The coefficients of the points in the graph are of type C. The polynomial P is converted to a polynomial with rational coefficients, if needed.

The class TopSweep2d depends on two parameters:

C, which is the type of coefficients of the points in the result,

SLV, which is the type of univariate solver to be used. The default value for SLV is Aberth<RR>.

This class provides following definition and static function:

typedef u_solution_t; the type of the solutions which are computed by the solver,

static Seq<u_solution_t> u_solve( const UPOL& p); which specifies the univariate solver, used in the algorithm.

Example

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

int main(int argc, char** argv) 
{
  const char * exemples[] = { 
    "33481-68244*x+47684*y+32162*x^2-54873*x*y+86*x^3*y+2566*x^3+3974*y^4*x+1354*x^2*y^3+13464*y^3-14150*y^4+4622*y^5+37086*y^2*x+7078*x^2*y-6980*y^3*x+204*x^2*y^2+34*x^4+267*x^3*y^2+x^5-y^7-21*x*y^5+25*x^4*y-30*y^6-37557*y^2",
    "x^6+y^2*x^4-y^4*x^2-2*x^4-y^6+2*y^4+x^2-y^2+x*y"
  };
  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];
      sprintf(file,"tmp-%i.off",i);
      geomview::ostream vw(file);
      vw<<g;
      vw.view();
    };
  return 0;
  
}

Here is the graph,which is computed:

SYNAPS DOCUMENTATION