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