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
art_svp_add_segment(ArtSVP ** p_vp,int * pn_segs_max,int ** pn_points_max,int n_points,int dir,ArtPoint * points,ArtDRect * bbox)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
art_svp_free(ArtSVP * svp)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
art_svp_seg_compare(const void * s1,const void * s2)137 art_svp_seg_compare (const void *s1, const void *s2)
138 {
139 const ArtSVPSeg *seg1 = s1;
140 const ArtSVPSeg *seg2 = 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
153