An LGPL/GPL-licensed artwork library
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

art_vpath_svp.c 4.9KB

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