Shortest algorithm for 8.7

[bmbernie]

Code: (Objective-C)

-(Rectangle *) intersect:(Rectangle *)testRect
{
    XYPoint *currPos = [[XYPoint alloc] init];
    XYPoint *intersectOrigin = [[XYPoint alloc] init];
    Rectangle *intersectionRectangle = [[Rectangle alloc] init];
    BOOL firstRun = TRUE;
    int n, e, s, w;
    
    // traverse through the screen as if it were a matrix of points, integer cartesian coord system 
    for (int xCoord = self.origin.x; xCoord <= self.origin.x + self.width; xCoord++) {
        for (int yCoord = self.origin.y; yCoord <= self.origin.y + self.height; yCoord++) {
            [currPos setX:xCoord setY:yCoord];
            if(firstRun && [testRect containsPoint:currPos]){
                // assign point for all corners
                e = w = currPos.x;
                n = s = currPos.y;
                // set new origin
                [intersectOrigin setX:e setY:n];
                // assign origin to rectangle
                [intersectionRectangle setOrigin:intersectOrigin];
                firstRun = FALSE;
            }
            else if ([testRect containsPoint: currPos]) {
                //check all 4 corner etc
                
                //check both y bounds
                if(currPos.x < w)
                    w = currPos.x;
                else if(currPos.x > e)
                    e = currPos.x;
                //check both x bounds
                if (currPos.y < s)
                    s = currPos.y;
                else if(currPos.y > n)
                    n = currPos.y;
            }
        }
    }
    
    [intersectionRectangle setWidth:(e-w) andHeight:(n-s)];
    
    return intersectionRectangle;
}

[rue]

What if the Rectangle has an origin of 0,0  with a length of 1,000,000 and width of 500,000?

You're doing nested loops then of 1Million iterations, and then another inside loop of 500,000 iterations....

That's A LOT of looping!

[bmbernie]

Good thing computers can do trillions of calculations a second! A million iterations is nothing.  There may be situations where this algorithm maybe not be the best approach, but this would work fine for most any application.  Also it is very easily readable, and the number of bugs in code goes down when you can code fewer lines of code.  So I believe this is a perfectly acceptable, easy to debug, easy to read solution, that covers all cases in a nice generic fashion.

The performance aspects are minimal when compared to everything else.