Back to index

easystroke  0.5.5.1
Classes | Defines | Functions | Variables
stroke.c File Reference
#include "stroke.h"
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include <stdbool.h>

Go to the source code of this file.

Classes

struct  point
struct  _stroke_t

Defines

#define _GNU_SOURCE
#define EPS   0.000001

Functions

stroke_t * stroke_alloc (int n)
void stroke_add_point (stroke_t *s, double x, double y)
static double angle_difference (double alpha, double beta)
void stroke_finish (stroke_t *s)
void stroke_free (stroke_t *s)
int stroke_get_size (const stroke_t *s)
void stroke_get_point (const stroke_t *s, int n, double *x, double *y)
double stroke_get_time (const stroke_t *s, int n)
double stroke_get_angle (const stroke_t *s, int n)
static double sqr (double x)
double stroke_angle_difference (const stroke_t *a, const stroke_t *b, int i, int j)
double stroke_compare (const stroke_t *a, const stroke_t *b, int *path_x, int *path_y)

Variables

const double stroke_infinity = 0.2

Class Documentation

struct point

Definition at line 28 of file stroke.c.

Class Members
double alpha
double dt
double t
double x
double y
struct _stroke_t

Definition at line 36 of file stroke.c.

Collaboration diagram for _stroke_t:
Class Members
int capacity
int n
struct point * p

Define Documentation

#define _GNU_SOURCE

Definition at line 17 of file stroke.c.

#define EPS   0.000001

Definition at line 26 of file stroke.c.


Function Documentation

static double angle_difference ( double  alpha,
double  beta 
) [inline, static]

Definition at line 58 of file stroke.c.

                                                                 {
       // return 1.0 - cos((alpha - beta) * M_PI);
       double d = alpha - beta;
       if (d < -1.0)
              d += 2.0;
       else if (d > 1.0)
              d -= 2.0;
       return d;
}

Here is the caller graph for this function:

static double sqr ( double  x) [inline, static]

Definition at line 130 of file stroke.c.

{ return x*x; }

Here is the caller graph for this function:

void stroke_add_point ( stroke_t *  s,
double  x,
double  y 
)

Definition at line 51 of file stroke.c.

                                                       {
       assert(s->capacity > s->n);
       s->p[s->n].x = x;
       s->p[s->n].y = y;
       s->n++;
}

Here is the caller graph for this function:

stroke_t* stroke_alloc ( int  n)

Definition at line 42 of file stroke.c.

                              {
       assert(n > 0);
       stroke_t *s = malloc(sizeof(stroke_t));
       s->n = 0;
       s->capacity = n;
       s->p = calloc(n, sizeof(struct point));
       return s;
}

Here is the caller graph for this function:

double stroke_angle_difference ( const stroke_t *  a,
const stroke_t *  b,
int  i,
int  j 
)

Definition at line 132 of file stroke.c.

                                                                                   {
       return fabs(angle_difference(stroke_get_angle(a, i), stroke_get_angle(b, j)));
}

Here is the call graph for this function:

Here is the caller graph for this function:

double stroke_compare ( const stroke_t *  a,
const stroke_t *  b,
int *  path_x,
int *  path_y 
)

Definition at line 140 of file stroke.c.

                                                                                      {
       int m = a->n - 1;
       int n = b->n - 1;

       double dist[m+1][n+1];
       int prev_x[m+1][n+1];
       int prev_y[m+1][n+1];
       for (int i = 0; i < m; i++)
              for (int j = 0; j < n; j++)
                     dist[i][j] = stroke_infinity;
       dist[m][n] = stroke_infinity;
       dist[0][0] = 0.0;

       for (int x = 0; x < m; x++) {
              for (int y = 0; y < n; y++) {
                     if (dist[x][y] >= stroke_infinity)
                            continue;
                     double tx  = a->p[x].t;
                     double ty  = b->p[y].t;
                     int max_x = x;
                     int max_y = y;
                     int k = 0;

                     inline void step(int x2, int y2) {
                            double dtx = a->p[x2].t - tx;
                            double dty = b->p[y2].t - ty;
                            if (dtx >= dty * 2.2 || dty >= dtx * 2.2 || dtx < EPS || dty < EPS)
                                   return;
                            k++;

                            double d = 0.0;
                            int i = x, j = y;
                            double next_tx = (a->p[i+1].t - tx) / dtx;
                            double next_ty = (b->p[j+1].t - ty) / dty;
                            double cur_t = 0.0;

                            for (;;) {
                                   double ad = sqr(angle_difference(a->p[i].alpha, b->p[j].alpha));
                                   double next_t = next_tx < next_ty ? next_tx : next_ty;
                                   bool done = next_t >= 1.0 - EPS;
                                   if (done)
                                          next_t = 1.0;
                                   d += (next_t - cur_t)*ad;
                                   if (done)
                                          break;
                                   cur_t = next_t;
                                   if (next_tx < next_ty)
                                          next_tx = (a->p[++i+1].t - tx) / dtx;
                                   else
                                          next_ty = (b->p[++j+1].t - ty) / dty;
                            }
                            double new_dist = dist[x][y] + d * (dtx + dty);
                            if (new_dist != new_dist) abort();

                            if (new_dist >= dist[x2][y2])
                                   return;

                            prev_x[x2][y2] = x;
                            prev_y[x2][y2] = y;
                            dist[x2][y2] = new_dist;
                     }

                     while (k < 4) {
                            if (a->p[max_x+1].t - tx > b->p[max_y+1].t - ty) {
                                   max_y++;
                                   if (max_y == n) {
                                          step(m, n);
                                          break;
                                   }
                                   for (int x2 = x+1; x2 <= max_x; x2++)
                                          step(x2, max_y);
                            } else {
                                   max_x++;
                                   if (max_x == m) {
                                          step(m, n);
                                          break;
                                   }
                                   for (int y2 = y+1; y2 <= max_y; y2++)
                                          step(max_x, y2);
                            }
                     }
              }
       }
       double cost = dist[m][n];
       if (path_x && path_y) {
              if (cost < stroke_infinity) {
                     int x = m;
                     int y = n;
                     int k = 0;
                     while (x || y) {
                            int old_x = x;
                            x = prev_x[x][y];
                            y = prev_y[old_x][y];
                            path_x[k] = x;
                            path_y[k] = y;
                            k++;
                     }
              } else {
                     path_x[0] = 0;
                     path_y[0] = 0;
              }
       }
       return cost;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void stroke_finish ( stroke_t *  s)

Definition at line 68 of file stroke.c.

                                {
       assert(s->capacity > 0);
       s->capacity = -1;

       int n = s->n - 1;
       double total = 0.0;
       s->p[0].t = 0.0;
       for (int i = 0; i < n; i++) {
              total += hypot(s->p[i+1].x - s->p[i].x, s->p[i+1].y - s->p[i].y);
              s->p[i+1].t = total;
       }
       for (int i = 0; i <= n; i++)
              s->p[i].t /= total;
       double minX = s->p[0].x, minY = s->p[0].y, maxX = minX, maxY = minY;
       for (int i = 1; i <= n; i++) {
              if (s->p[i].x < minX) minX = s->p[i].x;
              if (s->p[i].x > maxX) maxX = s->p[i].x;
              if (s->p[i].y < minY) minY = s->p[i].y;
              if (s->p[i].y > maxY) maxY = s->p[i].y;
       }
       double scaleX = maxX - minX;
       double scaleY = maxY - minY;
       double scale = (scaleX > scaleY) ? scaleX : scaleY;
       if (scale < 0.001) scale = 1;
       for (int i = 0; i <= n; i++) {
              s->p[i].x = (s->p[i].x-(minX+maxX)/2)/scale + 0.5;
              s->p[i].y = (s->p[i].y-(minY+maxY)/2)/scale + 0.5;
       }

       for (int i = 0; i < n; i++) {
              s->p[i].dt = s->p[i+1].t - s->p[i].t;
              s->p[i].alpha = atan2(s->p[i+1].y - s->p[i].y, s->p[i+1].x - s->p[i].x)/M_PI;
       }

}

Here is the caller graph for this function:

void stroke_free ( stroke_t *  s)

Definition at line 104 of file stroke.c.

                              {
       if (s)
              free(s->p);
       free(s);
}

Here is the caller graph for this function:

double stroke_get_angle ( const stroke_t *  s,
int  n 
)

Definition at line 125 of file stroke.c.

                                                  {
       assert(n+1 < s->n);
       return s->p[n].alpha;
}

Here is the caller graph for this function:

void stroke_get_point ( const stroke_t *  s,
int  n,
double *  x,
double *  y 
)

Definition at line 112 of file stroke.c.

                                                                      {
       assert(n < s->n);
       if (x)
              *x = s->p[n].x;
       if (y)
              *y = s->p[n].y;
}

Here is the caller graph for this function:

int stroke_get_size ( const stroke_t *  s)

Definition at line 110 of file stroke.c.

{ return s->n; }

Here is the caller graph for this function:

double stroke_get_time ( const stroke_t *  s,
int  n 
)

Definition at line 120 of file stroke.c.

                                                 {
       assert(n < s->n);
       return s->p[n].t;
}

Here is the caller graph for this function:


Variable Documentation

const double stroke_infinity = 0.2

Definition at line 25 of file stroke.c.