1 /*
2 vrect.c
3
4 Rectangle manipulation
5
6 Copyright (C) 2012 Bill Currie <bill@taniwha.org>
7
8 Author: Bill Currie <bill@taniwha.org>
9 Date: 2012/1/6
10
11 This program is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License
13 as published by the Free Software Foundation; either version 2
14 of the License, or (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
19
20 See the GNU General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to:
24
25 Free Software Foundation, Inc.
26 59 Temple Place - Suite 330
27 Boston, MA 02111-1307, USA
28
29 */
30 #ifdef HAVE_CONFIG_H
31 # include "config.h"
32 #endif
33
34 #include <stdlib.h>
35
36 #include "QF/mathlib.h"
37 #include "QF/vrect.h"
38
39 //#define TEST_MEMORY
40
41 #define RECT_BLOCK 128
42 #ifndef TEST_MEMORY
43 static vrect_t *free_rects;
44 #endif
45
46 VISIBLE vrect_t *
VRect_New(int x,int y,int width,int height)47 VRect_New (int x, int y, int width, int height)
48 {
49 vrect_t *r;
50 #ifndef TEST_MEMORY
51 if (!free_rects) {
52 int i;
53
54 free_rects = malloc (RECT_BLOCK * sizeof (vrect_t));
55 for (i = 0; i < RECT_BLOCK - 1; i++)
56 free_rects[i].next = &free_rects[i + 1];
57 free_rects[i].next = 0;
58 }
59 r = free_rects;
60 free_rects = free_rects->next;
61 #else
62 r = malloc (sizeof (vrect_t));
63 #endif
64 r->next = 0;
65 r->x = x;
66 r->y = y;
67 r->width = width;
68 r->height = height;
69 return r;
70 }
71
72 VISIBLE void
VRect_Delete(vrect_t * rect)73 VRect_Delete (vrect_t *rect)
74 {
75 #ifndef TEST_MEMORY
76 rect->next = free_rects;
77 free_rects = rect;
78 #else
79 free (rect);
80 #endif
81 }
82
83 VISIBLE vrect_t *
VRect_Intersect(const vrect_t * r1,const vrect_t * r2)84 VRect_Intersect (const vrect_t *r1, const vrect_t *r2)
85 {
86 int minx = max (VRect_MinX (r1), VRect_MinX (r2));
87 int miny = max (VRect_MinY (r1), VRect_MinY (r2));
88 int maxx = min (VRect_MaxX (r1), VRect_MaxX (r2));
89 int maxy = min (VRect_MaxY (r1), VRect_MaxY (r2));
90 return VRect_New (minx, miny, maxx - minx, maxy - miny);
91 }
92
93 VISIBLE vrect_t *
VRect_HSplit(const vrect_t * r,int y)94 VRect_HSplit (const vrect_t *r, int y)
95 {
96 vrect_t *r1, *r2;
97 int r1miny = VRect_MinY (r);
98 int r1maxy = min (VRect_MaxY (r), y);
99 int r2miny = max (VRect_MinY (r), y);
100 int r2maxy = VRect_MaxY (r);
101 r1 = VRect_New (VRect_MinX (r), r1miny, r->width, r1maxy - r1miny);
102 r2 = VRect_New (VRect_MinX (r), r2miny, r->width, r2maxy - r2miny);
103 r1->next = r2;
104 return r1;
105 }
106
107 VISIBLE vrect_t *
VRect_VSplit(const vrect_t * r,int x)108 VRect_VSplit (const vrect_t *r, int x)
109 {
110 vrect_t *r1, *r2;
111 int r1minx = VRect_MinX (r);
112 int r1maxx = min (VRect_MaxX (r), x);
113 int r2minx = max (VRect_MinX (r), x);
114 int r2maxx = VRect_MaxX (r);
115 r1 = VRect_New (r1minx, VRect_MinY (r), r1maxx - r1minx, r->height);
116 r2 = VRect_New (r2minx, VRect_MinY (r), r2maxx - r2minx, r->height);
117 r1->next = r2;
118 return r1;
119 }
120
121 VISIBLE vrect_t *
VRect_Difference(const vrect_t * r,const vrect_t * s)122 VRect_Difference (const vrect_t *r, const vrect_t *s)
123 {
124 vrect_t *i, *t, *_r;
125 vrect_t *rects = 0;
126 #define STASH(t) \
127 do { \
128 if (!VRect_IsEmpty (t)) { \
129 t->next = rects; \
130 rects = t; \
131 } else { \
132 VRect_Delete (t); \
133 } \
134 } while (0)
135
136 // Find the intersection of r (original rect) and s (the rect being
137 // subtracted from r). The intersection rect is used to carve the original
138 // rect. If there is no intersection (the intersection rect is empty),
139 // then there is nothing to subtract and the original rect (actually, a
140 // copy of it) is returned.
141 i = VRect_Intersect (r, s);
142 if (VRect_IsEmpty (i)) {
143 // copy r's shape to i, and return i.
144 i->x = r->x;
145 i->y = r->y;
146 i->width = r->width;
147 i->height = r->height;
148 return i;
149 }
150
151 // Split r along the top of the intersection rect and stash the top
152 // section if it is not empty.
153 t = VRect_HSplit (r, VRect_MinY (i));
154 // can't delete r: we don't own it
155 _r = t->next;
156 STASH (t); // maybe stash the top section
157 // r now represents the portion of the original rect below the top of
158 // the intersection rect.
159
160 // Split r along the bottom of the intersection rect and stash the bottom
161 // section if it is not empty.
162 t = VRect_HSplit (_r, VRect_MaxY (i));
163 VRect_Delete (_r); // finished with that copy of _r
164 _r = t;
165 STASH (t->next); // maybe stash the bottom section
166 // r now represents the horizontal section that is common with the
167 // intersection rect.
168
169 // Split r along the left side of tht intersection rect and stash the
170 // left section if it is not empty.
171 t = VRect_VSplit (_r, VRect_MinX (i));
172 VRect_Delete (_r); // finished with that copy of _r
173 _r = t->next;
174 STASH (t); // maybe stash the left section
175 // r now represets the section of the original rect that is between the
176 // top and bottom, and to the right of the left side of the intersection
177 // rect.
178
179 // Split r along the right side of the intersection rect and stash the
180 // right section if it is not empty. The left section is discarded.
181 t = VRect_VSplit (_r, VRect_MaxX (i));
182 VRect_Delete (_r); // finished with that copy of _r
183 STASH (t->next); // maybe stash the right section
184 VRect_Delete (t); // discard the left section
185
186 VRect_Delete (i); // finished with the intersection rect
187
188 return rects;
189 }
190
191 VISIBLE vrect_t *
VRect_Union(const vrect_t * r1,const vrect_t * r2)192 VRect_Union (const vrect_t *r1, const vrect_t *r2)
193 {
194 int minx, miny;
195 int maxx, maxy;
196
197 if (VRect_IsEmpty (r1))
198 return VRect_New (r2->x, r2->y, r2->width, r2->height);
199
200 if (VRect_IsEmpty (r2))
201 return VRect_New (r1->x, r1->y, r1->width, r1->height);
202
203 minx = min (VRect_MinX (r1), VRect_MinX (r2));
204 miny = min (VRect_MinY (r1), VRect_MinY (r2));
205 maxx = max (VRect_MaxX (r1), VRect_MaxX (r2));
206 maxy = max (VRect_MaxY (r1), VRect_MaxY (r2));
207 return VRect_New (minx, miny, maxx - minx, maxy - miny);
208 }
209
210 VISIBLE vrect_t *
VRect_Merge(const vrect_t * r1,const vrect_t * r2)211 VRect_Merge (const vrect_t *r1, const vrect_t *r2)
212 {
213 vrect_t *t, *u = 0;
214 vrect_t *merge;
215
216 // cannot merge intersecting rectangles
217 t = VRect_Intersect (r1, r2);
218 if (!VRect_IsEmpty (t)) {
219 VRect_Delete (t);
220 return 0;
221 }
222 VRect_Delete (t);
223
224 merge = VRect_Union (r1, r2);
225 if (VRect_IsEmpty (merge)) {
226 VRect_Delete (merge);
227 return 0;
228 }
229
230 // If the subtracting r1 from the union results in more than one rectangle
231 // then r1 and r2 cannot be merged.
232 t = VRect_Difference (merge, r1);
233 if (t && t->next)
234 goto cleanup;
235
236 // If subtracting r2 from the result of the previous difference results in
237 // any rectangles, then r1 and r2 cannot be merged.
238 if (t)
239 u = VRect_Difference (t, r2);
240 if (!u) {
241 if (t)
242 VRect_Delete (t);
243 return merge;
244 }
245 cleanup:
246 VRect_Delete (merge);
247 // merge is used as a temp while freeing t and u
248 while (u) {
249 merge = u->next;
250 VRect_Delete (u);
251 u = merge;
252 }
253 while (t) {
254 merge = t->next;
255 VRect_Delete (t);
256 t = merge;
257 }
258 return 0;
259 }
260