diff options
Diffstat (limited to 'src/art_vpath_svp.c')
| -rw-r--r-- | src/art_vpath_svp.c | 196 |
1 files changed, 196 insertions, 0 deletions
diff --git a/src/art_vpath_svp.c b/src/art_vpath_svp.c new file mode 100644 index 0000000..000265c --- /dev/null +++ b/src/art_vpath_svp.c @@ -0,0 +1,196 @@ +/* Libart_LGPL - library of basic graphic primitives + * Copyright (C) 1998-2000 Raph Levien + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this library; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +/* "Unsort" a sorted vector path into an ordinary vector path. */ + +#include "config.h" +#include "art_vpath_svp.h" + +#include <stdio.h> /* for printf - debugging */ +#include "art_misc.h" + +#include "art_vpath.h" +#include "art_svp.h" + +typedef struct _ArtVpathSVPEnd ArtVpathSVPEnd; + +struct _ArtVpathSVPEnd { + int seg_num; + int which; /* 0 = top, 1 = bottom */ + double x, y; +}; + +#define EPSILON 1e-6 + +static int +art_vpath_svp_point_compare (double x1, double y1, double x2, double y2) +{ + if (y1 - EPSILON > y2) return 1; + if (y1 + EPSILON < y2) return -1; + if (x1 - EPSILON > x2) return 1; + if (x1 + EPSILON < x2) return -1; + return 0; +} + +static int +art_vpath_svp_compare (const void *s1, const void *s2) +{ + const ArtVpathSVPEnd *e1 = s1; + const ArtVpathSVPEnd *e2 = s2; + + return art_vpath_svp_point_compare (e1->x, e1->y, e2->x, e2->y); +} + +/* Convert from sorted vector path representation into regular + vector path representation. + + Status of this routine: + + Basic correctness: Only works with closed paths. + + Numerical stability: Not known to work when more than two segments + meet at a point. + + Speed: Should be pretty good. + + Precision: Does not degrade precision. + +*/ +/** + * art_vpath_from_svp: Convert from svp to vpath form. + * @svp: Original #ArtSVP. + * + * Converts the sorted vector path @svp into standard vpath form. + * + * Return value: the newly allocated vpath. + **/ +ArtVpath * +art_vpath_from_svp (const ArtSVP *svp) +{ + int n_segs = svp->n_segs; + ArtVpathSVPEnd *ends; + ArtVpath *new; + int *visited; + int n_new, n_new_max; + int i, k; + int j = 0; /* Quiet compiler */ + int seg_num; + int first; + double last_x, last_y; + int n_points; + int pt_num; + + last_x = 0; /* to eliminate "uninitialized" warning */ + last_y = 0; + + ends = art_new (ArtVpathSVPEnd, n_segs * 2); + for (i = 0; i < svp->n_segs; i++) + { + int lastpt; + + ends[i * 2].seg_num = i; + ends[i * 2].which = 0; + ends[i * 2].x = svp->segs[i].points[0].x; + ends[i * 2].y = svp->segs[i].points[0].y; + + lastpt = svp->segs[i].n_points - 1; + ends[i * 2 + 1].seg_num = i; + ends[i * 2 + 1].which = 1; + ends[i * 2 + 1].x = svp->segs[i].points[lastpt].x; + ends[i * 2 + 1].y = svp->segs[i].points[lastpt].y; + } + qsort (ends, n_segs * 2, sizeof (ArtVpathSVPEnd), art_vpath_svp_compare); + + n_new = 0; + n_new_max = 16; /* I suppose we _could_ estimate this from traversing + the svp, so we don't have to reallocate */ + new = art_new (ArtVpath, n_new_max); + + visited = art_new (int, n_segs); + for (i = 0; i < n_segs; i++) + visited[i] = 0; + + first = 1; + for (i = 0; i < n_segs; i++) + { + if (!first) + { + /* search for the continuation of the existing subpath */ + /* This could be a binary search (which is why we sorted, above) */ + for (j = 0; j < n_segs * 2; j++) + { + if (!visited[ends[j].seg_num] && + art_vpath_svp_point_compare (last_x, last_y, + ends[j].x, ends[j].y) == 0) + break; + } + if (j == n_segs * 2) + first = 1; + } + if (first) + { + /* start a new subpath */ + for (j = 0; j < n_segs * 2; j++) + if (!visited[ends[j].seg_num]) + break; + } + if (j == n_segs * 2) + { + printf ("failure\n"); + } + seg_num = ends[j].seg_num; + n_points = svp->segs[seg_num].n_points; + for (k = 0; k < n_points; k++) + { + pt_num = svp->segs[seg_num].dir ? k : n_points - (1 + k); + if (k == 0) + { + if (first) + { + art_vpath_add_point (&new, &n_new, &n_new_max, + ART_MOVETO, + svp->segs[seg_num].points[pt_num].x, + svp->segs[seg_num].points[pt_num].y); + } + } + else + { + art_vpath_add_point (&new, &n_new, &n_new_max, + ART_LINETO, + svp->segs[seg_num].points[pt_num].x, + svp->segs[seg_num].points[pt_num].y); + if (k == n_points - 1) + { + last_x = svp->segs[seg_num].points[pt_num].x; + last_y = svp->segs[seg_num].points[pt_num].y; + /* to make more robust, check for meeting first_[xy], + set first if so */ + } + } + first = 0; + } + visited[seg_num] = 1; + } + + art_vpath_add_point (&new, &n_new, &n_new_max, + ART_END, 0, 0); + art_free (visited); + art_free (ends); + return new; +} |