lib/art/art_vpath_svp.c

   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
  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
  52 art_vpath_svp_compare (const void *s1, const void *s2)
  53 {
  54   const ArtVpathSVPEnd *e1 = (ArtVpathSVPEnd *)s1;
  55   const ArtVpathSVPEnd *e2 = (ArtVpathSVPEnd *)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 *
  84 art_vpath_from_svp (const ArtSVP *svp)
  85 {
  86   int n_segs = svp->n_segs;
  87   ArtVpathSVPEnd *ends;
  88   ArtVpath *xnew;
  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 = (ArtVpathSVPEnd*)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   xnew = (ArtVpath*)art_new (ArtVpath, n_new_max);
 124
 125   visited = (int*)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 (&xnew, &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 (&xnew, &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 (&xnew, &n_new, &n_new_max,
 192                        ART_END, 0, 0);
 193   art_free (visited);
 194   art_free (ends);
 195   return xnew;
 196 }