SDL 2.0
SDL_rect.c
Go to the documentation of this file.
1/*
2 Simple DirectMedia Layer
3 Copyright (C) 1997-2019 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#include "SDL_assert.h"
26
29{
30 int Amin, Amax, Bmin, Bmax;
31
32 if (!A) {
34 return SDL_FALSE;
35 }
36
37 if (!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
76{
77 int Amin, Amax, Bmin, Bmax;
78
79 if (!A) {
81 return SDL_FALSE;
82 }
83
84 if (!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
128void
130{
131 int Amin, Amax, Bmin, Bmax;
132
133 if (!A) {
135 return;
136 }
137
138 if (!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
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
299static int
300ComputeOutCode(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
317SDL_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) {
337 return SDL_FALSE;
338 }
339
340 if (!Y1) {
342 return SDL_FALSE;
343 }
344
345 if (!X2) {
347 return SDL_FALSE;
348 }
349
350 if (!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 /* If this assertion ever fires, here's the static analysis that warned about it:
445 http://buildbot.libsdl.org/sdl-static-analysis/sdl-macosx-static-analysis/sdl-macosx-static-analysis-1101/report-b0d01a.html#EndPath */
446 SDL_assert(x2 != x1); /* if equal: division by zero. */
447 x = rectx1;
448 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
449 } else if (outcode2 & CODE_RIGHT) {
450 /* If this assertion ever fires, here's the static analysis that warned about it:
451 http://buildbot.libsdl.org/sdl-static-analysis/sdl-macosx-static-analysis/sdl-macosx-static-analysis-1101/report-39b114.html#EndPath */
452 SDL_assert(x2 != x1); /* if equal: division by zero. */
453 x = rectx2;
454 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
455 }
456 x2 = x;
457 y2 = y;
458 outcode2 = ComputeOutCode(rect, x, y);
459 }
460 }
461 *X1 = x1;
462 *Y1 = y1;
463 *X2 = x2;
464 *Y2 = y2;
465 return SDL_TRUE;
466}
467
470 int numrects, const SDL_Rect * rects, SDL_Rect *span)
471{
472 int i;
473 int span_y1, span_y2;
474 int rect_y1, rect_y2;
475
476 if (width < 1) {
477 SDL_InvalidParamError("width");
478 return SDL_FALSE;
479 }
480
481 if (height < 1) {
482 SDL_InvalidParamError("height");
483 return SDL_FALSE;
484 }
485
486 if (!rects) {
487 SDL_InvalidParamError("rects");
488 return SDL_FALSE;
489 }
490
491 if (!span) {
492 SDL_InvalidParamError("span");
493 return SDL_FALSE;
494 }
495
496 if (numrects < 1) {
497 SDL_InvalidParamError("numrects");
498 return SDL_FALSE;
499 }
500
501 /* Initialize to empty rect */
502 span_y1 = height;
503 span_y2 = 0;
504
505 for (i = 0; i < numrects; ++i) {
506 rect_y1 = rects[i].y;
507 rect_y2 = rect_y1 + rects[i].h;
508
509 /* Clip out of bounds rectangles, and expand span rect */
510 if (rect_y1 < 0) {
511 span_y1 = 0;
512 } else if (rect_y1 < span_y1) {
513 span_y1 = rect_y1;
514 }
515 if (rect_y2 > height) {
516 span_y2 = height;
517 } else if (rect_y2 > span_y2) {
518 span_y2 = rect_y2;
519 }
520 }
521 if (span_y2 > span_y1) {
522 span->x = 0;
523 span->y = span_y1;
524 span->w = width;
525 span->h = (span_y2 - span_y1);
526 return SDL_TRUE;
527 }
528 return SDL_FALSE;
529}
530
531/* vi: set ts=4 sw=4 expandtab: */
#define SDL_assert(condition)
Definition: SDL_assert.h:169
#define SDL_InvalidParamError(param)
Definition: SDL_error.h:54
GLint GLint GLint GLint GLint GLint y
Definition: SDL_opengl.h:1574
GLuint GLuint GLsizei count
Definition: SDL_opengl.h:1571
GLint GLint GLsizei width
Definition: SDL_opengl.h:1572
GLint GLint GLint GLint GLint x
Definition: SDL_opengl.h:1574
GLint GLint GLsizei GLsizei height
Definition: SDL_opengl.h:1572
GLfixed GLfixed GLint GLint GLfixed points
GLfixed GLfixed GLfixed y2
GLuint64EXT * result
GLfixed y1
GLuint GLfloat GLfloat GLfloat x1
GLfixed GLfixed x2
GLenum GLenum void void void * span
static int ComputeOutCode(const SDL_Rect *rect, int x, int y)
Definition: SDL_rect.c:300
#define CODE_BOTTOM
Definition: SDL_rect.c:294
SDL_bool SDL_IntersectRect(const SDL_Rect *A, const SDL_Rect *B, SDL_Rect *result)
Calculate the intersection of two rectangles.
Definition: SDL_rect.c:75
SDL_bool SDL_EnclosePoints(const SDL_Point *points, int count, const SDL_Rect *clip, SDL_Rect *result)
Calculate a minimal rectangle enclosing a set of points.
Definition: SDL_rect.c:192
#define CODE_RIGHT
Definition: SDL_rect.c:297
SDL_bool SDL_GetSpanEnclosingRect(int width, int height, int numrects, const SDL_Rect *rects, SDL_Rect *span)
Definition: SDL_rect.c:469
SDL_bool SDL_HasIntersection(const SDL_Rect *A, const SDL_Rect *B)
Determine whether two rectangles intersect.
Definition: SDL_rect.c:28
#define CODE_LEFT
Definition: SDL_rect.c:296
void SDL_UnionRect(const SDL_Rect *A, const SDL_Rect *B, SDL_Rect *result)
Calculate the union of two rectangles.
Definition: SDL_rect.c:129
SDL_bool SDL_IntersectRectAndLine(const SDL_Rect *rect, int *X1, int *Y1, int *X2, int *Y2)
Calculate the intersection of a rectangle and line segment.
Definition: SDL_rect.c:317
#define CODE_TOP
Definition: SDL_rect.c:295
SDL_FORCE_INLINE SDL_bool SDL_RectEmpty(const SDL_Rect *r)
Returns true if the rectangle has no area.
Definition: SDL_rect.h:108
SDL_bool
Definition: SDL_stdinc.h:162
@ SDL_TRUE
Definition: SDL_stdinc.h:164
@ SDL_FALSE
Definition: SDL_stdinc.h:163
return Display return Display Bool Bool int int int return Display XEvent Bool(*) XPointer return Display return Display Drawable _Xconst char unsigned int unsigned int return Display Pixmap Pixmap XColor XColor unsigned int unsigned int return Display _Xconst char char int char return Display Visual unsigned int int int char unsigned int unsigned int in i)
Definition: SDL_x11sym.h:50
#define NULL
Definition: begin_code.h:167
EGLSurface EGLint * rects
Definition: eglext.h:282
The structure that defines a point (integer)
Definition: SDL_rect.h:49
A rectangle, with the origin at the upper left (integer).
Definition: SDL_rect.h:78
int h
Definition: SDL_rect.h:80
int w
Definition: SDL_rect.h:80
int y
Definition: SDL_rect.h:79
int x
Definition: SDL_rect.h:79
SDL_Rect rect
Definition: testrelative.c:27