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