1 /* Libart_LGPL - library of basic graphic primitives
2  * Copyright (C) 1998-2000 Raph Levien
3  *
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.
8  *
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.
13  *
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.
18  */
19 
20 /* "Unsort" a sorted vector path into an ordinary vector path. */
21 
22 #include "config.h"
23 #include "art_vpath_svp.h"
24 
25 #include <stdio.h> /* for printf - debugging */
26 #include "art_misc.h"
27 
28 #include "art_vpath.h"
29 #include "art_svp.h"
30 
31 typedef struct _ArtVpathSVPEnd ArtVpathSVPEnd;
32 
33 struct _ArtVpathSVPEnd {
34   int seg_num;
35   int which; /* 0 = top, 1 = bottom */
36   double x, y;
37 };
38 
39 #define EPSILON 1e-6
40 
41 static int
art_vpath_svp_point_compare(double x1,double y1,double x2,double y2)42 art_vpath_svp_point_compare (double x1, double y1, double x2, double y2)
43 {
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;
48   return 0;
49 }
50 
51 static int
art_vpath_svp_compare(const void * s1,const void * s2)52 art_vpath_svp_compare (const void *s1, const void *s2)
53 {
54   const ArtVpathSVPEnd *e1 = s1;
55   const ArtVpathSVPEnd *e2 = s2;
56 
57   return art_vpath_svp_point_compare (e1->x, e1->y, e2->x, e2->y);
58 }
59 
60 /* Convert from sorted vector path representation into regular
61    vector path representation.
62 
63    Status of this routine:
64 
65    Basic correctness: Only works with closed paths.
66 
67    Numerical stability: Not known to work when more than two segments
68    meet at a point.
69 
70    Speed: Should be pretty good.
71 
72    Precision: Does not degrade precision.
73 
74 */
75 /**
76  * art_vpath_from_svp: Convert from svp to vpath form.
77  * @svp: Original #ArtSVP.
78  *
79  * Converts the sorted vector path @svp into standard vpath form.
80  *
81  * Return value: the newly allocated vpath.
82  **/
83 ArtVpath *
art_vpath_from_svp(const ArtSVP * svp)84 art_vpath_from_svp (const ArtSVP *svp)
85 {
86   int n_segs = svp->n_segs;
87   ArtVpathSVPEnd *ends;
88   ArtVpath *new;
89   int *visited;
90   int n_new, n_new_max;
91   int i, k;
92   int j = 0; /* Quiet compiler */
93   int seg_num;
94   int first;
95   double last_x, last_y;
96   int n_points;
97   int pt_num;
98 
99   last_x = 0; /* to eliminate "uninitialized" warning */
100   last_y = 0;
101 
102   ends = art_new (ArtVpathSVPEnd, n_segs * 2);
103   for (i = 0; i < svp->n_segs; i++)
104     {
105       int lastpt;
106 
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;
111 
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;
117     }
118   qsort (ends, n_segs * 2, sizeof (ArtVpathSVPEnd), art_vpath_svp_compare);
119 
120   n_new = 0;
121   n_new_max = 16; /* I suppose we _could_ estimate this from traversing
122 		     the svp, so we don't have to reallocate */
123   new = art_new (ArtVpath, n_new_max);
124 
125   visited = art_new (int, n_segs);
126   for (i = 0; i < n_segs; i++)
127     visited[i] = 0;
128 
129   first = 1;
130   for (i = 0; i < n_segs; i++)
131     {
132       if (!first)
133 	{
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++)
137 	    {
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)
141 		break;
142 	    }
143 	  if (j == n_segs * 2)
144 	    first = 1;
145 	}
146       if (first)
147 	{
148 	  /* start a new subpath */
149 	  for (j = 0; j < n_segs * 2; j++)
150 	    if (!visited[ends[j].seg_num])
151 	      break;
152 	}
153       if (j == n_segs * 2)
154 	{
155 	  printf ("failure\n");
156 	}
157       seg_num = ends[j].seg_num;
158       n_points = svp->segs[seg_num].n_points;
159       for (k = 0; k < n_points; k++)
160 	{
161 	  pt_num = svp->segs[seg_num].dir ? k : n_points - (1 + k);
162 	  if (k == 0)
163 	    {
164 	      if (first)
165 		{
166 		  art_vpath_add_point (&new, &n_new, &n_new_max,
167 				       ART_MOVETO,
168 				       svp->segs[seg_num].points[pt_num].x,
169 				       svp->segs[seg_num].points[pt_num].y);
170 		}
171 	    }
172 	  else
173 	    {
174 	      art_vpath_add_point (&new, &n_new, &n_new_max,
175 				   ART_LINETO,
176 				   svp->segs[seg_num].points[pt_num].x,
177 				   svp->segs[seg_num].points[pt_num].y);
178 	      if (k == n_points - 1)
179 		{
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],
183 		     set first if so */
184 		}
185 	    }
186 	  first = 0;
187 	}
188       visited[seg_num] = 1;
189     }
190 
191   art_vpath_add_point (&new, &n_new, &n_new_max,
192 		       ART_END, 0, 0);
193   art_free (visited);
194   art_free (ends);
195   return new;
196 }
197