src/video/SDL_rect.c
author Sam Lantinga <slouken@libsdl.org>
Sat, 02 Mar 2013 20:44:16 -0800
changeset 6950 1ddb72193079
parent 6885 700f1b25f77f
child 7014 3e0d048e1c14
permissions -rw-r--r--
Added a mouse ID to the mouse events, which set to the special value SDL_TOUCH_MOUSEID for mouse events simulated by touch input.
     1 /*
     2   Simple DirectMedia Layer
     3   Copyright (C) 1997-2013 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_config.h"
    22 
    23 #include "SDL_rect.h"
    24 #include "SDL_rect_c.h"
    25 
    26 
    27 SDL_bool
    28 SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B)
    29 {
    30     int Amin, Amax, Bmin, Bmax;
    31 
    32     if (!A || !B) {
    33         // TODO error message
    34         return SDL_FALSE;
    35     }
    36 
    37     /* Special cases for empty rects */
    38     if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) {
    39         return SDL_FALSE;
    40     }
    41 
    42     /* Horizontal intersection */
    43     Amin = A->x;
    44     Amax = Amin + A->w;
    45     Bmin = B->x;
    46     Bmax = Bmin + B->w;
    47     if (Bmin > Amin)
    48         Amin = Bmin;
    49     if (Bmax < Amax)
    50         Amax = Bmax;
    51     if (Amax <= Amin)
    52         return SDL_FALSE;
    53 
    54     /* Vertical intersection */
    55     Amin = A->y;
    56     Amax = Amin + A->h;
    57     Bmin = B->y;
    58     Bmax = Bmin + B->h;
    59     if (Bmin > Amin)
    60         Amin = Bmin;
    61     if (Bmax < Amax)
    62         Amax = Bmax;
    63     if (Amax <= Amin)
    64         return SDL_FALSE;
    65 
    66     return SDL_TRUE;
    67 }
    68 
    69 SDL_bool
    70 SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
    71 {
    72     int Amin, Amax, Bmin, Bmax;
    73 
    74     if (!A || !B || !result) {
    75         // TODO error message
    76         return SDL_FALSE;
    77     }
    78 
    79     /* Special cases for empty rects */
    80     if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) {
    81         return SDL_FALSE;
    82     }
    83     
    84     /* Horizontal intersection */
    85     Amin = A->x;
    86     Amax = Amin + A->w;
    87     Bmin = B->x;
    88     Bmax = Bmin + B->w;
    89     if (Bmin > Amin)
    90         Amin = Bmin;
    91     result->x = Amin;
    92     if (Bmax < Amax)
    93         Amax = Bmax;
    94     result->w = Amax - Amin;
    95 
    96     /* Vertical intersection */
    97     Amin = A->y;
    98     Amax = Amin + A->h;
    99     Bmin = B->y;
   100     Bmax = Bmin + B->h;
   101     if (Bmin > Amin)
   102         Amin = Bmin;
   103     result->y = Amin;
   104     if (Bmax < Amax)
   105         Amax = Bmax;
   106     result->h = Amax - Amin;
   107 
   108     return !SDL_RectEmpty(result);
   109 }
   110 
   111 void
   112 SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
   113 {
   114     int Amin, Amax, Bmin, Bmax;
   115 
   116     if (!A || !B || !result) {
   117         return;
   118     }
   119 
   120     /* Special cases for empty Rects */
   121     if (SDL_RectEmpty(A)) {
   122       if (SDL_RectEmpty(B)) {
   123        /* A and B empty */
   124        return;
   125       } else {
   126        /* A empty, B not empty */
   127        *result = *B;
   128        return;
   129       }
   130     } else {      
   131       if (SDL_RectEmpty(B)) {
   132        /* A not empty, B empty */
   133        *result = *A;
   134        return;
   135       } 
   136     }
   137     
   138     /* Horizontal union */
   139     Amin = A->x;
   140     Amax = Amin + A->w;
   141     Bmin = B->x;
   142     Bmax = Bmin + B->w;
   143     if (Bmin < Amin)
   144         Amin = Bmin;
   145     result->x = Amin;
   146     if (Bmax > Amax)
   147         Amax = Bmax;
   148     result->w = Amax - Amin;
   149 
   150     /* Vertical union */
   151     Amin = A->y;
   152     Amax = Amin + A->h;
   153     Bmin = B->y;
   154     Bmax = Bmin + B->h;
   155     if (Bmin < Amin)
   156         Amin = Bmin;
   157     result->y = Amin;
   158     if (Bmax > Amax)
   159         Amax = Bmax;
   160     result->h = Amax - Amin;
   161 }
   162 
   163 SDL_bool
   164 SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip,
   165                   SDL_Rect * result)
   166 {
   167     int minx = 0;
   168     int miny = 0;
   169     int maxx = 0;
   170     int maxy = 0;
   171     int x, y, i;
   172 
   173     if (!points) {
   174         /* TODO error message */
   175         return SDL_FALSE;
   176     }
   177 
   178     if (count < 1) {
   179         /* TODO error message */
   180         return SDL_FALSE;
   181     }
   182 
   183     if (clip) {
   184         SDL_bool added = SDL_FALSE;
   185         const int clip_minx = clip->x;
   186         const int clip_miny = clip->y;
   187         const int clip_maxx = clip->x+clip->w-1;
   188         const int clip_maxy = clip->y+clip->h-1;
   189 
   190         /* Special case for empty rectangle */
   191         if (SDL_RectEmpty(clip)) {
   192             return SDL_FALSE;
   193         }
   194         
   195         for (i = 0; i < count; ++i) {
   196             x = points[i].x;
   197             y = points[i].y;
   198 
   199             if (x < clip_minx || x > clip_maxx ||
   200                 y < clip_miny || y > clip_maxy) {
   201                 continue;
   202             }
   203             if (!added) {
   204                 /* Special case: if no result was requested, we are done */
   205                 if (result == NULL) {
   206                     return SDL_TRUE;
   207                 }
   208 
   209                 /* First point added */
   210                 minx = maxx = x;
   211                 miny = maxy = y;
   212                 added = SDL_TRUE;
   213                 continue;
   214             }
   215             if (x < minx) {
   216                 minx = x;
   217             } else if (x > maxx) {
   218                 maxx = x;
   219             }
   220             if (y < miny) {
   221                 miny = y;
   222             } else if (y > maxy) {
   223                 maxy = y;
   224             }
   225         }
   226         if (!added) {
   227             return SDL_FALSE;
   228         }
   229     } else {
   230         /* Special case: if no result was requested, we are done */
   231         if (result == NULL) {
   232             return SDL_TRUE;
   233         }
   234         
   235         /* No clipping, always add the first point */
   236         minx = maxx = points[0].x;
   237         miny = maxy = points[0].y;
   238 
   239         for (i = 1; i < count; ++i) {
   240             x = points[i].x;
   241             y = points[i].y;
   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     }
   255 
   256     if (result) {
   257         result->x = minx;
   258         result->y = miny;
   259         result->w = (maxx-minx)+1;
   260         result->h = (maxy-miny)+1;
   261     }
   262     return SDL_TRUE;
   263 }
   264 
   265 /* Use the Cohen-Sutherland algorithm for line clipping */
   266 #define CODE_BOTTOM 1
   267 #define CODE_TOP    2
   268 #define CODE_LEFT   4
   269 #define CODE_RIGHT  8
   270 
   271 static int ComputeOutCode(const SDL_Rect * rect, int x, int y)
   272 {
   273     int code = 0;
   274     if (y < 0) {
   275         code |= CODE_TOP;
   276     } else if (y >= rect->y + rect->h) {
   277         code |= CODE_BOTTOM;
   278     }
   279     if (x < 0) {
   280         code |= CODE_LEFT;
   281     } else if (x >= rect->x + rect->w) {
   282         code |= CODE_RIGHT;
   283     }
   284     return code;
   285 }
   286 
   287 SDL_bool
   288 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
   289                          int *Y2)
   290 {
   291     int x = 0;
   292     int y = 0;
   293     int x1, y1;
   294     int x2, y2;
   295     int rectx1;
   296     int recty1;
   297     int rectx2;
   298     int recty2;
   299     int outcode1, outcode2;
   300 
   301     if (!rect || !X1 || !Y1 || !X2 || !Y2) {
   302         // TODO error message
   303         return SDL_FALSE;
   304     }
   305 
   306     /* Special case for empty rect */
   307     if (SDL_RectEmpty(rect)) {
   308         return SDL_FALSE;
   309     }
   310     
   311     x1 = *X1;
   312     y1 = *Y1;
   313     x2 = *X2;
   314     y2 = *Y2;
   315     rectx1 = rect->x;
   316     recty1 = rect->y;
   317     rectx2 = rect->x + rect->w - 1;
   318     recty2 = rect->y + rect->h - 1;
   319 
   320     /* Check to see if entire line is inside rect */
   321     if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
   322         y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
   323         return SDL_TRUE;
   324     }
   325 
   326     /* Check to see if entire line is to one side of rect */
   327     if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
   328         (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
   329         return SDL_FALSE;
   330     }
   331 
   332     if (y1 == y2) {
   333         /* Horizontal line, easy to clip */
   334         if (x1 < rectx1) {
   335             *X1 = rectx1;
   336         } else if (x1 > rectx2) {
   337             *X1 = rectx2;
   338         }
   339         if (x2 < rectx1) {
   340             *X2 = rectx1;
   341         } else if (x2 > rectx2) {
   342             *X2 = rectx2;
   343         }
   344         return SDL_TRUE;
   345     }
   346 
   347     if (x1 == x2) {
   348         /* Vertical line, easy to clip */
   349         if (y1 < recty1) {
   350             *Y1 = recty1;
   351         } else if (y1 > recty2) {
   352             *Y1 = recty2;
   353         }
   354         if (y2 < recty1) {
   355             *Y2 = recty1;
   356         } else if (y2 > recty2) {
   357             *Y2 = recty2;
   358         }
   359         return SDL_TRUE;
   360     }
   361 
   362     /* More complicated Cohen-Sutherland algorithm */
   363     outcode1 = ComputeOutCode(rect, x1, y1);
   364     outcode2 = ComputeOutCode(rect, x2, y2);
   365     while (outcode1 || outcode2) {
   366         if (outcode1 & outcode2) {
   367             return SDL_FALSE;
   368         }
   369 
   370         if (outcode1) {
   371             if (outcode1 & CODE_TOP) {
   372                 y = recty1;
   373                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   374             } else if (outcode1 & CODE_BOTTOM) {
   375                 y = recty2;
   376                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   377             } else if (outcode1 & CODE_LEFT) {
   378                 x = rectx1;
   379                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   380             } else if (outcode1 & CODE_RIGHT) {
   381                 x = rectx2;
   382                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   383             }
   384             x1 = x;
   385             y1 = y;
   386             outcode1 = ComputeOutCode(rect, x, y);
   387         } else {
   388             if (outcode2 & CODE_TOP) {
   389                 y = recty1;
   390                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   391             } else if (outcode2 & CODE_BOTTOM) {
   392                 y = recty2;
   393                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   394             } else if (outcode2 & CODE_LEFT) {
   395                 x = rectx1;
   396                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   397             } else if (outcode2 & CODE_RIGHT) {
   398                 x = rectx2;
   399                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   400             }
   401             x2 = x;
   402             y2 = y;
   403             outcode2 = ComputeOutCode(rect, x, y);
   404         }
   405     }
   406     *X1 = x1;
   407     *Y1 = y1;
   408     *X2 = x2;
   409     *Y2 = y2;
   410     return SDL_TRUE;
   411 }
   412 
   413 SDL_bool
   414 SDL_GetSpanEnclosingRect(int width, int height,
   415                          int numrects, SDL_Rect * rects, SDL_Rect *span)
   416 {
   417     int i;
   418     int span_y1, span_y2;
   419     int rect_y1, rect_y2;
   420 
   421     if (width < 1 || height < 1) {
   422         // TODO error message
   423         return SDL_FALSE;
   424     }
   425 
   426     if (!rects || !span) {
   427         // TODO error message
   428         return SDL_FALSE;
   429     }
   430 
   431     if (numrects < 1) {
   432         // TODO error message
   433         return SDL_FALSE;
   434     }
   435 
   436     /* Initialize to empty rect */
   437     span_y1 = height;
   438     span_y2 = 0;
   439 
   440     for (i = 0; i < numrects; ++i) {
   441         rect_y1 = rects[i].y;
   442         rect_y2 = rect_y1 + rects[i].h;
   443 
   444         /* Clip out of bounds rectangles, and expand span rect */
   445         if (rect_y1 < 0) {
   446             span_y1 = 0;
   447         } else if (rect_y1 < span_y1) {
   448             span_y1 = rect_y1;
   449         }
   450         if (rect_y2 > height) {
   451             span_y2 = height;
   452         } else if (rect_y2 > span_y2) {
   453             span_y2 = rect_y2;
   454         }
   455     }
   456     if (span_y2 > span_y1) {
   457         span->x = 0;
   458         span->y = span_y1;
   459         span->w = width;
   460         span->h = (span_y2 - span_y1);
   461         return SDL_TRUE;
   462     }
   463     return SDL_FALSE;
   464 }
   465 
   466 /* vi: set ts=4 sw=4 expandtab: */