1 /* Libart_LGPL - library of basic graphic primitives
2 * Copyright (C) 1998-2000 Raph Levien
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
20 /* "Unsort" a sorted vector path into an ordinary vector path. */
23 #include "art_vpath_svp.h"
25 #include <stdio.h> /* for printf - debugging */
28 #include "art_vpath.h"
31 typedef struct _ArtVpathSVPEnd ArtVpathSVPEnd;
33 struct _ArtVpathSVPEnd {
35 int which; /* 0 = top, 1 = bottom */
42 art_vpath_svp_point_compare (double x1, double y1, double x2, double y2)
44 if (y1 - EPSILON > y2) return 1;
45 if (y1 + EPSILON < y2) return -1;
46 if (x1 - EPSILON > x2) return 1;
47 if (x1 + EPSILON < x2) return -1;
52 art_vpath_svp_compare (const void *s1, const void *s2)
54 const ArtVpathSVPEnd *e1 = (ArtVpathSVPEnd *)s1;
55 const ArtVpathSVPEnd *e2 = (ArtVpathSVPEnd *)s2;
57 return art_vpath_svp_point_compare (e1->x, e1->y, e2->x, e2->y);
60 /* Convert from sorted vector path representation into regular
61 vector path representation.
63 Status of this routine:
65 Basic correctness: Only works with closed paths.
67 Numerical stability: Not known to work when more than two segments
70 Speed: Should be pretty good.
72 Precision: Does not degrade precision.
76 * art_vpath_from_svp: Convert from svp to vpath form.
77 * @svp: Original #ArtSVP.
79 * Converts the sorted vector path @svp into standard vpath form.
81 * Return value: the newly allocated vpath.
84 art_vpath_from_svp (const ArtSVP *svp)
86 int n_segs = svp->n_segs;
92 int j = 0; /* Quiet compiler */
95 double last_x, last_y;
99 last_x = 0; /* to eliminate "uninitialized" warning */
102 ends = (ArtVpathSVPEnd*)art_new (ArtVpathSVPEnd, n_segs * 2);
103 for (i = 0; i < svp->n_segs; i++)
107 ends[i * 2].seg_num = i;
108 ends[i * 2].which = 0;
109 ends[i * 2].x = svp->segs[i].points[0].x;
110 ends[i * 2].y = svp->segs[i].points[0].y;
112 lastpt = svp->segs[i].n_points - 1;
113 ends[i * 2 + 1].seg_num = i;
114 ends[i * 2 + 1].which = 1;
115 ends[i * 2 + 1].x = svp->segs[i].points[lastpt].x;
116 ends[i * 2 + 1].y = svp->segs[i].points[lastpt].y;
118 qsort (ends, n_segs * 2, sizeof (ArtVpathSVPEnd), art_vpath_svp_compare);
121 n_new_max = 16; /* I suppose we _could_ estimate this from traversing
122 the svp, so we don't have to reallocate */
123 xnew = (ArtVpath*)art_new (ArtVpath, n_new_max);
125 visited = (int*)art_new (int, n_segs);
126 for (i = 0; i < n_segs; i++)
130 for (i = 0; i < n_segs; i++)
134 /* search for the continuation of the existing subpath */
135 /* This could be a binary search (which is why we sorted, above) */
136 for (j = 0; j < n_segs * 2; j++)
138 if (!visited[ends[j].seg_num] &&
139 art_vpath_svp_point_compare (last_x, last_y,
140 ends[j].x, ends[j].y) == 0)
148 /* start a new subpath */
149 for (j = 0; j < n_segs * 2; j++)
150 if (!visited[ends[j].seg_num])
155 printf ("failure\n");
157 seg_num = ends[j].seg_num;
158 n_points = svp->segs[seg_num].n_points;
159 for (k = 0; k < n_points; k++)
161 pt_num = svp->segs[seg_num].dir ? k : n_points - (1 + k);
166 art_vpath_add_point (&xnew, &n_new, &n_new_max,
168 svp->segs[seg_num].points[pt_num].x,
169 svp->segs[seg_num].points[pt_num].y);
174 art_vpath_add_point (&xnew, &n_new, &n_new_max,
176 svp->segs[seg_num].points[pt_num].x,
177 svp->segs[seg_num].points[pt_num].y);
178 if (k == n_points - 1)
180 last_x = svp->segs[seg_num].points[pt_num].x;
181 last_y = svp->segs[seg_num].points[pt_num].y;
182 /* to make more robust, check for meeting first_[xy],
188 visited[seg_num] = 1;
191 art_vpath_add_point (&xnew, &n_new, &n_new_max,