#
source:
trunk/third/libart_lgpl/art_vpath_svp.c
@
18256

Revision 18256, 4.9 KB checked in by ghudson, 22 years ago (diff) |
---|

Line | |
---|---|

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 = 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 * |

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 | } |

**Note:**See TracBrowser for help on using the repository browser.