new function list_deep_free
[swftools.git] / lib / art / art_svp.c
1 /* Libart_LGPL - library of basic graphic primitives
2  * Copyright (C) 1998 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 /* Basic constructors and operations for sorted vector paths */
21
22 #include "config.h"
23 #include "art_svp.h"
24
25 #include "art_misc.h"
26
27 /* Add a new segment. The arguments can be zero and NULL if the caller
28    would rather fill them in later.
29
30    We also realloc one auxiliary array of ints of size n_segs if
31    desired.
32 */
33 /**
34  * art_svp_add_segment: Add a segment to an #ArtSVP structure.
35  * @p_vp: Pointer to where the #ArtSVP structure is stored.
36  * @pn_segs_max: Pointer to the allocated size of *@p_vp.
37  * @pn_points_max: Pointer to where auxiliary array is stored.
38  * @n_points: Number of points for new segment.
39  * @dir: Direction for new segment; 0 is up, 1 is down.
40  * @points: Points for new segment.
41  * @bbox: Bounding box for new segment.
42  *
43  * Adds a new segment to an ArtSVP structure. This routine reallocates
44  * the structure if necessary, updating *@p_vp and *@pn_segs_max as
45  * necessary.
46  *
47  * The new segment is simply added after all other segments. Thus,
48  * this routine should be called in order consistent with the #ArtSVP
49  * sorting rules.
50  *
51  * If the @bbox argument is given, it is simply stored in the new
52  * segment. Otherwise (if it is NULL), the bounding box is computed
53  * from the @points given.
54  **/
55 int
56 art_svp_add_segment (ArtSVP **p_vp, int *pn_segs_max,
57                      int **pn_points_max,
58                      int n_points, int dir, ArtPoint *points,
59                      ArtDRect *bbox)
60 {
61   int seg_num;
62   ArtSVP *svp;
63   ArtSVPSeg *seg;
64
65   svp = *p_vp;
66   seg_num = svp->n_segs++;
67   if (*pn_segs_max == seg_num)
68     {
69       *pn_segs_max <<= 1;
70       svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
71                                    (*pn_segs_max - 1) * sizeof(ArtSVPSeg));
72       *p_vp = svp;
73       if (pn_points_max != NULL)
74         *pn_points_max = art_renew (*pn_points_max, int, *pn_segs_max);
75     }
76   seg = &svp->segs[seg_num];
77   seg->n_points = n_points;
78   seg->dir = dir;
79   seg->points = points;
80   if (bbox)
81     seg->bbox = *bbox;
82   else if (points)
83     {
84       double x_min, x_max;
85       int i;
86
87       x_min = x_max = points[0].x;
88       for (i = 1; i < n_points; i++)
89         {
90           if (x_min > points[i].x)
91             x_min = points[i].x;
92           if (x_max < points[i].x)
93             x_max = points[i].x;
94         }
95       seg->bbox.x0 = x_min;
96       seg->bbox.y0 = points[0].y;
97       
98       seg->bbox.x1 = x_max;
99       seg->bbox.y1 = points[n_points - 1].y;
100     }
101   return seg_num;
102 }
103
104
105 /**
106  * art_svp_free: Free an #ArtSVP structure.
107  * @svp: #ArtSVP to free.
108  * 
109  * Frees an #ArtSVP structure and all the segments in it.
110  **/
111 void
112 art_svp_free (ArtSVP *svp)
113 {
114   int n_segs = svp->n_segs;
115   int i;
116
117   for (i = 0; i < n_segs; i++)
118     art_free (svp->segs[i].points);
119   art_free (svp);
120 }
121
122 #ifdef ART_USE_NEW_INTERSECTOR
123 #define EPSILON 0
124 #else
125 #define EPSILON 1e-6
126 #endif
127
128 /**
129  * art_svp_seg_compare: Compare two segments of an svp.
130  * @seg1: First segment to compare.
131  * @seg2: Second segment to compare.
132  * 
133  * Compares two segments of an svp. Return 1 if @seg2 is below or to the
134  * right of @seg1, -1 otherwise.
135  **/
136 int
137 art_svp_seg_compare (const void *s1, const void *s2)
138 {
139   const ArtSVPSeg *seg1 = (ArtSVPSeg *)s1;
140   const ArtSVPSeg *seg2 = (ArtSVPSeg *)s2;
141
142   if (seg1->points[0].y - EPSILON > seg2->points[0].y) return 1;
143   else if (seg1->points[0].y + EPSILON < seg2->points[0].y) return -1;
144   else if (seg1->points[0].x - EPSILON > seg2->points[0].x) return 1;
145   else if (seg1->points[0].x + EPSILON < seg2->points[0].x) return -1;
146   else if ((seg1->points[1].x - seg1->points[0].x) *
147            (seg2->points[1].y - seg2->points[0].y) -
148            (seg1->points[1].y - seg1->points[0].y) *
149            (seg2->points[1].x - seg2->points[0].x) > 0) return 1;
150   else return -1;
151 }
152