1 /*
2 Simple DirectMedia Layer
3 Copyright (C) 1997-2016 Sam Lantinga <slouken@libsdl.org>
4
5 This software is provided 'as-is', without any express or implied
6 warranty. In no event will the authors be held liable for any damages
7 arising from the use of this software.
8
9 Permission is granted to anyone to use this software for any purpose,
10 including commercial applications, and to alter it and redistribute it
11 freely, subject to the following restrictions:
12
13 1. The origin of this software must not be misrepresented; you must not
14 claim that you wrote the original software. If you use this software
15 in a product, an acknowledgment in the product documentation would be
16 appreciated but is not required.
17 2. Altered source versions must be plainly marked as such, and must not be
18 misrepresented as being the original software.
19 3. This notice may not be removed or altered from any source distribution.
20 */
21 #include "../SDL_internal.h"
22
23 #include "SDL_rect.h"
24 #include "SDL_rect_c.h"
25
26
27 SDL_bool
SDL_HasIntersection(const SDL_Rect * A,const SDL_Rect * B)28 SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B)
29 {
30 int Amin, Amax, Bmin, Bmax;
31
32 if (!A) {
33 SDL_InvalidParamError("A");
34 return SDL_FALSE;
35 }
36
37 if (!B) {
38 SDL_InvalidParamError("B");
39 return SDL_FALSE;
40 }
41
42 /* Special cases for empty rects */
43 if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) {
44 return SDL_FALSE;
45 }
46
47 /* Horizontal intersection */
48 Amin = A->x;
49 Amax = Amin + A->w;
50 Bmin = B->x;
51 Bmax = Bmin + B->w;
52 if (Bmin > Amin)
53 Amin = Bmin;
54 if (Bmax < Amax)
55 Amax = Bmax;
56 if (Amax <= Amin)
57 return SDL_FALSE;
58
59 /* Vertical intersection */
60 Amin = A->y;
61 Amax = Amin + A->h;
62 Bmin = B->y;
63 Bmax = Bmin + B->h;
64 if (Bmin > Amin)
65 Amin = Bmin;
66 if (Bmax < Amax)
67 Amax = Bmax;
68 if (Amax <= Amin)
69 return SDL_FALSE;
70
71 return SDL_TRUE;
72 }
73
74 SDL_bool
SDL_IntersectRect(const SDL_Rect * A,const SDL_Rect * B,SDL_Rect * result)75 SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
76 {
77 int Amin, Amax, Bmin, Bmax;
78
79 if (!A) {
80 SDL_InvalidParamError("A");
81 return SDL_FALSE;
82 }
83
84 if (!B) {
85 SDL_InvalidParamError("B");
86 return SDL_FALSE;
87 }
88
89 if (!result) {
90 SDL_InvalidParamError("result");
91 return SDL_FALSE;
92 }
93
94 /* Special cases for empty rects */
95 if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) {
96 result->w = 0;
97 result->h = 0;
98 return SDL_FALSE;
99 }
100
101 /* Horizontal intersection */
102 Amin = A->x;
103 Amax = Amin + A->w;
104 Bmin = B->x;
105 Bmax = Bmin + B->w;
106 if (Bmin > Amin)
107 Amin = Bmin;
108 result->x = Amin;
109 if (Bmax < Amax)
110 Amax = Bmax;
111 result->w = Amax - Amin;
112
113 /* Vertical intersection */
114 Amin = A->y;
115 Amax = Amin + A->h;
116 Bmin = B->y;
117 Bmax = Bmin + B->h;
118 if (Bmin > Amin)
119 Amin = Bmin;
120 result->y = Amin;
121 if (Bmax < Amax)
122 Amax = Bmax;
123 result->h = Amax - Amin;
124
125 return !SDL_RectEmpty(result);
126 }
127
128 void
SDL_UnionRect(const SDL_Rect * A,const SDL_Rect * B,SDL_Rect * result)129 SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
130 {
131 int Amin, Amax, Bmin, Bmax;
132
133 if (!A) {
134 SDL_InvalidParamError("A");
135 return;
136 }
137
138 if (!B) {
139 SDL_InvalidParamError("B");
140 return;
141 }
142
143 if (!result) {
144 SDL_InvalidParamError("result");
145 return;
146 }
147
148 /* Special cases for empty Rects */
149 if (SDL_RectEmpty(A)) {
150 if (SDL_RectEmpty(B)) {
151 /* A and B empty */
152 return;
153 } else {
154 /* A empty, B not empty */
155 *result = *B;
156 return;
157 }
158 } else {
159 if (SDL_RectEmpty(B)) {
160 /* A not empty, B empty */
161 *result = *A;
162 return;
163 }
164 }
165
166 /* Horizontal union */
167 Amin = A->x;
168 Amax = Amin + A->w;
169 Bmin = B->x;
170 Bmax = Bmin + B->w;
171 if (Bmin < Amin)
172 Amin = Bmin;
173 result->x = Amin;
174 if (Bmax > Amax)
175 Amax = Bmax;
176 result->w = Amax - Amin;
177
178 /* Vertical union */
179 Amin = A->y;
180 Amax = Amin + A->h;
181 Bmin = B->y;
182 Bmax = Bmin + B->h;
183 if (Bmin < Amin)
184 Amin = Bmin;
185 result->y = Amin;
186 if (Bmax > Amax)
187 Amax = Bmax;
188 result->h = Amax - Amin;
189 }
190
191 SDL_bool
SDL_EnclosePoints(const SDL_Point * points,int count,const SDL_Rect * clip,SDL_Rect * result)192 SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip,
193 SDL_Rect * result)
194 {
195 int minx = 0;
196 int miny = 0;
197 int maxx = 0;
198 int maxy = 0;
199 int x, y, i;
200
201 if (!points) {
202 SDL_InvalidParamError("points");
203 return SDL_FALSE;
204 }
205
206 if (count < 1) {
207 SDL_InvalidParamError("count");
208 return SDL_FALSE;
209 }
210
211 if (clip) {
212 SDL_bool added = SDL_FALSE;
213 const int clip_minx = clip->x;
214 const int clip_miny = clip->y;
215 const int clip_maxx = clip->x+clip->w-1;
216 const int clip_maxy = clip->y+clip->h-1;
217
218 /* Special case for empty rectangle */
219 if (SDL_RectEmpty(clip)) {
220 return SDL_FALSE;
221 }
222
223 for (i = 0; i < count; ++i) {
224 x = points[i].x;
225 y = points[i].y;
226
227 if (x < clip_minx || x > clip_maxx ||
228 y < clip_miny || y > clip_maxy) {
229 continue;
230 }
231 if (!added) {
232 /* Special case: if no result was requested, we are done */
233 if (result == NULL) {
234 return SDL_TRUE;
235 }
236
237 /* First point added */
238 minx = maxx = x;
239 miny = maxy = y;
240 added = SDL_TRUE;
241 continue;
242 }
243 if (x < minx) {
244 minx = x;
245 } else if (x > maxx) {
246 maxx = x;
247 }
248 if (y < miny) {
249 miny = y;
250 } else if (y > maxy) {
251 maxy = y;
252 }
253 }
254 if (!added) {
255 return SDL_FALSE;
256 }
257 } else {
258 /* Special case: if no result was requested, we are done */
259 if (result == NULL) {
260 return SDL_TRUE;
261 }
262
263 /* No clipping, always add the first point */
264 minx = maxx = points[0].x;
265 miny = maxy = points[0].y;
266
267 for (i = 1; i < count; ++i) {
268 x = points[i].x;
269 y = points[i].y;
270
271 if (x < minx) {
272 minx = x;
273 } else if (x > maxx) {
274 maxx = x;
275 }
276 if (y < miny) {
277 miny = y;
278 } else if (y > maxy) {
279 maxy = y;
280 }
281 }
282 }
283
284 if (result) {
285 result->x = minx;
286 result->y = miny;
287 result->w = (maxx-minx)+1;
288 result->h = (maxy-miny)+1;
289 }
290 return SDL_TRUE;
291 }
292
293 /* Use the Cohen-Sutherland algorithm for line clipping */
294 #define CODE_BOTTOM 1
295 #define CODE_TOP 2
296 #define CODE_LEFT 4
297 #define CODE_RIGHT 8
298
299 static int
ComputeOutCode(const SDL_Rect * rect,int x,int y)300 ComputeOutCode(const SDL_Rect * rect, int x, int y)
301 {
302 int code = 0;
303 if (y < rect->y) {
304 code |= CODE_TOP;
305 } else if (y >= rect->y + rect->h) {
306 code |= CODE_BOTTOM;
307 }
308 if (x < rect->x) {
309 code |= CODE_LEFT;
310 } else if (x >= rect->x + rect->w) {
311 code |= CODE_RIGHT;
312 }
313 return code;
314 }
315
316 SDL_bool
SDL_IntersectRectAndLine(const SDL_Rect * rect,int * X1,int * Y1,int * X2,int * Y2)317 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
318 int *Y2)
319 {
320 int x = 0;
321 int y = 0;
322 int x1, y1;
323 int x2, y2;
324 int rectx1;
325 int recty1;
326 int rectx2;
327 int recty2;
328 int outcode1, outcode2;
329
330 if (!rect) {
331 SDL_InvalidParamError("rect");
332 return SDL_FALSE;
333 }
334
335 if (!X1) {
336 SDL_InvalidParamError("X1");
337 return SDL_FALSE;
338 }
339
340 if (!Y1) {
341 SDL_InvalidParamError("Y1");
342 return SDL_FALSE;
343 }
344
345 if (!X2) {
346 SDL_InvalidParamError("X2");
347 return SDL_FALSE;
348 }
349
350 if (!Y2) {
351 SDL_InvalidParamError("Y2");
352 return SDL_FALSE;
353 }
354
355 /* Special case for empty rect */
356 if (SDL_RectEmpty(rect)) {
357 return SDL_FALSE;
358 }
359
360 x1 = *X1;
361 y1 = *Y1;
362 x2 = *X2;
363 y2 = *Y2;
364 rectx1 = rect->x;
365 recty1 = rect->y;
366 rectx2 = rect->x + rect->w - 1;
367 recty2 = rect->y + rect->h - 1;
368
369 /* Check to see if entire line is inside rect */
370 if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
371 y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
372 return SDL_TRUE;
373 }
374
375 /* Check to see if entire line is to one side of rect */
376 if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
377 (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
378 return SDL_FALSE;
379 }
380
381 if (y1 == y2) {
382 /* Horizontal line, easy to clip */
383 if (x1 < rectx1) {
384 *X1 = rectx1;
385 } else if (x1 > rectx2) {
386 *X1 = rectx2;
387 }
388 if (x2 < rectx1) {
389 *X2 = rectx1;
390 } else if (x2 > rectx2) {
391 *X2 = rectx2;
392 }
393 return SDL_TRUE;
394 }
395
396 if (x1 == x2) {
397 /* Vertical line, easy to clip */
398 if (y1 < recty1) {
399 *Y1 = recty1;
400 } else if (y1 > recty2) {
401 *Y1 = recty2;
402 }
403 if (y2 < recty1) {
404 *Y2 = recty1;
405 } else if (y2 > recty2) {
406 *Y2 = recty2;
407 }
408 return SDL_TRUE;
409 }
410
411 /* More complicated Cohen-Sutherland algorithm */
412 outcode1 = ComputeOutCode(rect, x1, y1);
413 outcode2 = ComputeOutCode(rect, x2, y2);
414 while (outcode1 || outcode2) {
415 if (outcode1 & outcode2) {
416 return SDL_FALSE;
417 }
418
419 if (outcode1) {
420 if (outcode1 & CODE_TOP) {
421 y = recty1;
422 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
423 } else if (outcode1 & CODE_BOTTOM) {
424 y = recty2;
425 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
426 } else if (outcode1 & CODE_LEFT) {
427 x = rectx1;
428 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
429 } else if (outcode1 & CODE_RIGHT) {
430 x = rectx2;
431 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
432 }
433 x1 = x;
434 y1 = y;
435 outcode1 = ComputeOutCode(rect, x, y);
436 } else {
437 if (outcode2 & CODE_TOP) {
438 y = recty1;
439 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
440 } else if (outcode2 & CODE_BOTTOM) {
441 y = recty2;
442 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
443 } else if (outcode2 & CODE_LEFT) {
444 x = rectx1;
445 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
446 } else if (outcode2 & CODE_RIGHT) {
447 x = rectx2;
448 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
449 }
450 x2 = x;
451 y2 = y;
452 outcode2 = ComputeOutCode(rect, x, y);
453 }
454 }
455 *X1 = x1;
456 *Y1 = y1;
457 *X2 = x2;
458 *Y2 = y2;
459 return SDL_TRUE;
460 }
461
462 SDL_bool
SDL_GetSpanEnclosingRect(int width,int height,int numrects,const SDL_Rect * rects,SDL_Rect * span)463 SDL_GetSpanEnclosingRect(int width, int height,
464 int numrects, const SDL_Rect * rects, SDL_Rect *span)
465 {
466 int i;
467 int span_y1, span_y2;
468 int rect_y1, rect_y2;
469
470 if (width < 1) {
471 SDL_InvalidParamError("width");
472 return SDL_FALSE;
473 }
474
475 if (height < 1) {
476 SDL_InvalidParamError("height");
477 return SDL_FALSE;
478 }
479
480 if (!rects) {
481 SDL_InvalidParamError("rects");
482 return SDL_FALSE;
483 }
484
485 if (!span) {
486 SDL_InvalidParamError("span");
487 return SDL_FALSE;
488 }
489
490 if (numrects < 1) {
491 SDL_InvalidParamError("numrects");
492 return SDL_FALSE;
493 }
494
495 /* Initialize to empty rect */
496 span_y1 = height;
497 span_y2 = 0;
498
499 for (i = 0; i < numrects; ++i) {
500 rect_y1 = rects[i].y;
501 rect_y2 = rect_y1 + rects[i].h;
502
503 /* Clip out of bounds rectangles, and expand span rect */
504 if (rect_y1 < 0) {
505 span_y1 = 0;
506 } else if (rect_y1 < span_y1) {
507 span_y1 = rect_y1;
508 }
509 if (rect_y2 > height) {
510 span_y2 = height;
511 } else if (rect_y2 > span_y2) {
512 span_y2 = rect_y2;
513 }
514 }
515 if (span_y2 > span_y1) {
516 span->x = 0;
517 span->y = span_y1;
518 span->w = width;
519 span->h = (span_y2 - span_y1);
520 return SDL_TRUE;
521 }
522 return SDL_FALSE;
523 }
524
525 /* vi: set ts=4 sw=4 expandtab: */
526