SDL  2.0
SDL_rect.c
Go to the documentation of this file.
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 
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  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
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: */
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 GLsizei width
Definition: SDL_opengl.h:1565
GLint GLint GLint GLint GLint x
Definition: SDL_opengl.h:1567
GLuint GLuint GLsizei count
Definition: SDL_opengl.h:1564
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
GLint GLint GLsizei GLsizei height
Definition: SDL_opengl.h:1565
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
GLfixed GLfixed GLint GLint GLfixed points
GLfixed y1
int x
Definition: SDL_rect.h:50
GLint GLint GLint GLint GLint GLint y
Definition: SDL_opengl.h:1567
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
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 NULL
Definition: begin_code.h:143
SDL_bool
Definition: SDL_stdinc.h:130
int h
Definition: SDL_rect.h:67
SDL_Rect rects[MAX_RECTS]
GLenum GLenum void void void * span
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:463