SDL  2.0
SDL_rect.c
Go to the documentation of this file.
1 /*
2  Simple DirectMedia Layer
3  Copyright (C) 1997-2018 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 
28 SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B)
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 
128 void
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 
191 SDL_bool
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
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
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  /* 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 
468 SDL_bool
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: */
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
#define CODE_TOP
Definition: SDL_rect.c:295
GLuint GLfloat GLfloat GLfloat x1
GLuint64EXT * result
GLint GLint GLint GLint GLint x
Definition: SDL_opengl.h:1574
GLuint GLuint GLsizei count
Definition: SDL_opengl.h:1571
SDL_Rect rect
Definition: testrelative.c:27
SDL_bool SDL_HasIntersection(const SDL_Rect *A, const SDL_Rect *B)
Determine whether two rectangles intersect.
Definition: SDL_rect.c:28
#define CODE_RIGHT
Definition: SDL_rect.c:297
GLfixed GLfixed GLfixed y2
The structure that defines a point.
Definition: SDL_rect.h:48
#define CODE_BOTTOM
Definition: SDL_rect.c:294
static int ComputeOutCode(const SDL_Rect *rect, int x, int y)
Definition: SDL_rect.c:300
#define SDL_InvalidParamError(param)
Definition: SDL_error.h:54
SDL_FORCE_INLINE SDL_bool SDL_RectEmpty(const SDL_Rect *r)
Returns true if the rectangle has no area.
Definition: SDL_rect.h:82
GLfixed GLfixed x2
GLint GLint GLsizei width
Definition: SDL_opengl.h:1572
GLfixed GLfixed GLint GLint GLfixed points
GLfixed y1
int x
Definition: SDL_rect.h:50
int y
Definition: SDL_rect.h:51
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
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
#define CODE_LEFT
Definition: SDL_rect.c:296
GLint GLint GLint GLint GLint GLint y
Definition: SDL_opengl.h:1574
int x
Definition: SDL_rect.h:66
int w
Definition: SDL_rect.h:67
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 SDL_assert(condition)
Definition: SDL_assert.h:169
#define NULL
Definition: begin_code.h:164
SDL_bool
Definition: SDL_stdinc.h:139
GLint GLint GLsizei GLsizei height
Definition: SDL_opengl.h:1572
int h
Definition: SDL_rect.h:67
GLenum GLenum void void void * span
EGLSurface EGLint * rects
Definition: eglext.h:282
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
int y
Definition: SDL_rect.h:66
A rectangle, with the origin at the upper left.
Definition: SDL_rect.h:64
SDL_bool SDL_GetSpanEnclosingRect(int width, int height, int numrects, const SDL_Rect *rects, SDL_Rect *span)
Definition: SDL_rect.c:469