Amazon.com Widgets Exercise 8.7 (is there a better algorithm?)
Welcome, Guest. Please login or register.
Did you miss your activation email?
September 02, 2014, 09:47:32 AM
Home Help Search chat Login Register 
News: Read this please.The Great Kangaroo Escape Looking for reviews of the 4th ed on Amazon!   Twitter:  @skochan
                     

+ Official Forum for Programming in Objective-C (the iPhone Programming Language) - Stephen Kochan
|-+ Programming in Objective-C, 4th edition
| |-+ Exercises
| | |-+ Chapter 8
| | | |-+ Exercise 8.7 (is there a better algorithm?)
Pages: [1] Go Down
Print
Author Topic: Exercise 8.7 (is there a better algorithm?) (Read 1193 times)
Hesadanza
Newbie
*
Posts: 28






on: February 05, 2012, 07:50:52 PM

I've looked at several of the methods others have written to solve this exercise, and they look as verbose and lengthy as my own.  Is there no other way to solve this exercise in a more concise manner?  Do we really need to test 16 cases?  I'd love to see someone solve this in like 25 lines.  Is there a loop that could be developed, or a simpler algorithm?

If this is what is really going on behind the scenes when I do an intersect in Adobe Illustrator with two rectangles, then I have a new found respect for that program.  I can't imagine how they're doing intersections between complex curved shapes!

Here's the code for my Rectangle class.  It's been converted to floating points. Note, I added a few more helper methods, to break it down into more bite-sized pieces so I could wrap my brain around it easier, and make it more readable.  I also added a good number of comments to help explain things:
Code: (Objective-C)
#import "Rectangle.h"

@implementation Rectangle

-(float) area
{
    return self.width * self.height;
}
-(float) perimeter
{
    return (self.width + self.height) * 2;
}

//Methods to get corner coordinates
-(XYPoint *) topRight
{
    XYPoint *temp = [[XYPoint alloc] init];
    temp.x = self.origin.x + self.width;
    temp.y = self.origin.y + self.height;
    return temp;
}
-(XYPoint *) topLeft
{
    XYPoint *temp = [[XYPoint alloc] init];
    temp.x = self.origin.x;
    temp.y = self.origin.y + self.height;
    return temp;
}
-(XYPoint *) bottomRight
{
    XYPoint *temp = [[XYPoint alloc] init];
    temp.x = self.origin.x + self.width;
    temp.y = self.origin.y;
    return temp;
}
-(XYPoint *) bottomLeft
{
    XYPoint *temp = [[XYPoint alloc] init];
    temp.x = self.origin.x;
    temp.y = self.origin.y;
    return temp;
}

//Methods to return x or y coordinates of the sides of the rectangle
-(float) rightSideX
{
    return self.origin.x + self.width;
}
-(float) leftSideX
{
    return self.origin.x;
}
-(float) topSideY
{
    return self.origin.y + self.height;
}
-(float) bottomSideY
{
    return self.origin.y;
}

// Is a point contained inside self?
-(BOOL) containsPoint: (XYPoint *) aPoint
{
    if ((aPoint.x > self.leftSideX && aPoint.x < self.rightSideX) &&
        (aPoint.y > self.bottomSideY && aPoint.y < self.topSideY))
        return YES;
    else return NO;
}

-(Rectangle *) intersect: (Rectangle *) rec
{
    Rectangle *newRec = [[Rectangle alloc] init];
    
    // First check to see if bottom left corner of rec is inside self. Covers 4 cases:
    // #1 1 corner of rec is inside self, other 3 corners are outside.
    // #2 2 corners of rec are inside self (including rec bottom right), other 2 corners outside.
    // #3 2 corners of rec are inside self (including rec top left), other 2 corners outside.
    // #4 all 4 corners of rec are inside self, that is, rec is wholly inside self.
    if ([self containsPoint:rec.bottomLeft])
    {
        // origin same as rec in all 4 cases
        newRec.origin = rec.origin;
        
        // to find width in cases #1 & #3 (true), or #2 & #4 (false)
        newRec.width = self.rightSideX < rec.rightSideX ? self.rightSideX - rec.leftSideX : rec.width;
        
        // to find the height in cases #1 & #2 (true), or #3 & #4 (false)
        newRec.height = self.topSideY < rec.topSideY ? self.topSideY - rec.bottomSideY : rec.height;
        
        return newRec;
    }
    
    // Next, test to see if the bottom right corner of rec is inside self.  Covers 2 cases.
    // #5 1 corner of rec is inside self, other 3 outside
    // #6 2 corners of rec are inside self (including rec top right), other 2 outside
    else if ([self containsPoint:rec.bottomRight])
    {
        XYPoint *neworigin = [[XYPoint alloc] init];
        
        // Origin is the same in both cases
        [neworigin setX:self.leftSideX andY:rec.bottomSideY];
        newRec.origin = neworigin;
        
        // Width is the same in both cases
        newRec.width = rec.rightSideX - self.leftSideX;
        
        // to find height in case #5 (true), and #6 (false)
        newRec.height = self.topSideY < rec.topSideY ? self.topSideY - rec.bottomSideY : rec.height;

        return newRec;
    }
    
    // Next, test to see if the top right corner of rec is inside self.  Covers 2 cases.
    // #7 1 corner of rec inside self, other 3 outside
    // #8 2 corners of rec inside self (including top left corner), other 2 outside.
    else if ([self containsPoint:rec.topRight])
    {
        XYPoint *neworigin = [[XYPoint alloc] init];
        
        // Origin for case #7
        if (rec.leftSideX < self.leftSideX)
            newRec.origin = self.origin;
        // Origin for case #8
        else
        {
            [neworigin setX:rec.leftSideX andY:self.bottomSideY];
            newRec.origin = neworigin;
        }
        
        // To find width in case #7 (true), and case #8 (false)
        newRec.width = rec.leftSideX < self.leftSideX ? rec.rightSideX - self.leftSideX : rec.width;
        
        // To find height in both cases is the same
        newRec.height = rec.topSideY - self.bottomSideY;
        
        return newRec;
    }
    
    // Next, test to see if top left corner of rec is inside self. Case #9.
    // (Other cases where top left corner of rec was inside self were taken care of in cases #3 and #8.)
    else if ([self containsPoint:rec.topLeft])
    {
        XYPoint *neworigin = [[XYPoint alloc] init];
        [neworigin setX:rec.leftSideX andY:self.bottomSideY];
        newRec.origin = neworigin;
        
        newRec.width = self.rightSideX - rec.leftSideX;
        newRec.height = rec.topSideY - self.bottomSideY;
        return newRec;
    }
    
    // Next, test to see if self is contained totally within rec.  If it is, the intersection is self.  Case #10.
    else if ([rec containsPoint:self.bottomLeft] && [rec containsPoint:self.bottomRight] && [rec containsPoint:self.topLeft] && [rec containsPoint:self.topRight])
    {
        newRec.origin = self.origin;
        newRec.width = self.width;
        newRec.height = self.height;
        return newRec;
    }
    // Next, test if two corners of self are inside rec, starting with top left.
    else if ([rec containsPoint:self.topLeft])
    {
        // Top left and right corners of self are inside rec. Case #11
        if ([rec containsPoint:self.topRight])
        {
            XYPoint *neworigin = [[XYPoint alloc] init];
            [neworigin setX:rec.bottomSideY andY:self.leftSideX];
            newRec.origin = neworigin;
            
            newRec.width = self.width;
            newRec.height = self.topSideY - rec.bottomSideY;
            return newRec;
        }
        // Top left and bottom left corners of self are inside rec. Case #12
        else if ([rec containsPoint:self.bottomLeft])
        {
            newRec.origin = self.origin;
            
            newRec.width = rec.rightSideX - self.leftSideX;
            newRec.height = self.height;
            return newRec;
        }
    }
    
    // Next, test to see if other corners of self are inside rec, starting with bottom right;
    else if ([rec containsPoint:self.bottomRight])
    {
        // Bottom right and bottom left of self are inside rec. Case #13
        if ([rec containsPoint:self.bottomLeft])
        {
            newRec.origin = self.origin;
            
            newRec.width = self.width;
            newRec.height = rec.topSideY - self.bottomSideY;
            return newRec;
        }
        // Bottom right and top right of self are inside rec. Case #14
        else if ([rec containsPoint:self.topRight])
        {
            XYPoint *neworigin = [[XYPoint alloc] init];
            [neworigin setX:rec.leftSideX andY:self.bottomSideY];
            newRec.origin = neworigin;
            
            newRec.width = self.rightSideX - rec.leftSideX;
            newRec.height = self.height;
            return newRec;
        }
    }
    
    //Next, if both rectangles are exactly the same, have the same origin, width & height, then they intersect, but have no corners inside each other. Case #15.
    else if (self.origin.x == rec.origin.x && self.origin.y == rec.origin.y && self.width == rec.width && self.height == rec.height)
    {
        newRec.origin = self.origin;
        newRec.width = self.width;
        newRec.height = self.height;
        return newRec;
    }
    
    // Lastly, the only other option is that the rectangles don't intersect at all, or may be only sharing a side.  Case #16.
    else
    {
        XYPoint *neworigin = [[XYPoint alloc] init];
        [neworigin setX:0 andY:0];
        newRec.origin = neworigin;
        newRec.width = 0;
        newRec.height = 0;
        
        return newRec;
    }
    
    // There should be no other options, and method should have already returned.
    NSLog(@"Error: intersect method not functioning correctly.");
    
    return newRec;
}

-(void) draw
{
    int w = 0, h = 0;
    while (w < self.width)
    {
        printf("-");
        w++;
    }
    printf("\n");
    while (h < self.height)
    {
        printf("|");
        for (int i=0; i<self.width-2; i++) printf(" ");
        printf("|\n");
        h++;
    }
    w = 0;
    while (w < self.width)
    {
        printf("-");
        w++;
    }
    printf("\n");
    
}
@end
Last Edit: February 05, 2012, 07:58:06 PM by Hesadanza Logged
Sebastiaan76
Newbie
*
Posts: 7


Email




Reply #1 on: February 08, 2012, 04:49:08 AM

Hey there.

I'm also pretty stumped by this problem. The closest I've got so far is ( what I think ) some pretty cool code to test when the rectangle's don't intersect ( i.e. the Rectangle object is wholly to the right, left, below, above or inside our Self rectangle ).

I'm really struggling to get my head around this problem without having to test for so many options! I've even done some searching on how these problems are solved in the Maths world using Co-ordinate Geometry but it gets way over my head very fast!

Anyway, keen to hear anyone's view as to whether the code below is atleast a nifty way to test for non-intersecting..........I'm still a fair way off testing and returning the intersection stuff.

pls, note, the below is not the completed method, just what I've got so far.

Code: (Objective-C)
-(Rectangle *) intersect: (Rectangle *) RectA
{
// first we test to see if one rectangle does indeed intersect any part of our rectangle
   
bool noIntOffRight, noIntOffLeft, noIntOffBelow, noIntOffAbove, noIntAllInside; //setup some variables to take our no intersect tests
    int temp_x, temp_y, temp_height, temp_width;
   
    noIntOffRight = RectA.origin.x > (self.origin.x + self.width);
    noIntOffLeft = (RectA.origin.x + RectA.width) < self.origin.x;
    noIntOffBelow = (RectA.origin.y + RectA.height) < self.origin.y;
    noIntOffAbove = RectA.origin.y > (self.origin.y + self.height);
   
    // the following tests to see if RectA is wholly inside our Self Rectangle
   
    noIntAllInside = RectA.origin.x > self.origin.x && (RectA.origin.x + RectA.width) < (self.origin.x + self.width) &&
                    RectA.origin.y > self.origin.y && (RectA.origin.y + RectA.height) < (self.origin.y + self.height);
   
    if ( noIntOffAbove || noIntOffBelow || noIntOffLeft || noIntOffRight || noIntAllInside )
    {
        RectA.origin.x = 0;
        RectA.origin.y = 0;
        RectA.width = 0;
        RectA.height = 0;
// not exactly sure how i'm going to return the 'nil' rectangle just yet, but the code for that would go here

    }
Logged
urbanlung
Newbie
*
Posts: 13






Reply #2 on: February 18, 2012, 04:52:02 PM

Hi, here is another way that might be of interest. There is some redundancy in what I've done, like specifying all the corners but I liked having them in any way. Also there is some additional stuff that I put in for my own edification. Sorry about the way I've included the code, I cannot for the life of me work out how to upload in that groovy style that almost everyone else uses.



//
//  Rectangle.m
//  Rectanglec4e8
//
//  Created by Matthew Donald on 18/01/2012.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#import "Rectangle.h"

@implementation Rectangle

{
    XYPoint *origin;;
    XYPoint *Acorner;
    XYPoint *Bcorner;
    XYPoint *Ccorner;
    XYPoint *Dcorner;
   
    Rectangle *interRect;
}

@synthesize width, height;



-(void) setOrigin: (XYPoint *) pt
{
    if (!origin) //-------test makes sure that origin doesnt exist before allocing it.
        origin = [[XYPoint alloc] init];
       
    origin.x = pt.x;
    origin.y = pt.y;
}

-(void) setWidth: (float) w andHeight: (float) h;
{
    width = w;
    height = h;
}

-(XYPoint *) origin
{
    return origin;
}

-(float) perimeter;
{
    return 2 * (width + height);
}
-(float) area;
{
    return height * width;
}

-(void) translateOrigin: (XYPoint*) trans;
{
    [origin translate:trans];
}

-(BOOL) hasOrigin//-------I've clearly got something wonky here, please pass the boolean bit
{
    if (origin)
        return YES;
}


//---------------------------------SET COORDS OF CORNERS----------------------

-(void) setCorners
{
    //----------------------corners are arranged anti-clockwise (or widershins) with Acorner being the same as origin
    // Dcorner----------Ccorner
    // |                |
    // |                |
    // |                |
    // Acorner----------Bcorner
   
    [self setAcorner];
    [self setBcorner];
    [self setCcorner];
    [self setDcorner];

}


-(void) setAcorner
{
    if (!Acorner) //-------test makes sure that A doesnt exist before allocing it.
        Acorner = [[XYPoint alloc] init];
   
   
    Acorner.x = origin.x;
    Acorner.y = origin.y;
}

-(void) setBcorner
{
    if (!Bcorner) //-------test makes sure that B doesnt exist before allocing it.
        Bcorner = [[XYPoint alloc] init];

    Bcorner.x = origin.x + width;
    Bcorner.y = origin.y;


}

-(void) setCcorner
{
    if (!Ccorner) //-------test makes sure that C doesnt exist before allocing it.
        Ccorner = [[XYPoint alloc] init];
    Ccorner.x = origin.x + width;
    Ccorner.y = origin.y + height;
}
-(void) setDcorner
{
    if (!Dcorner) //-------test makes sure that D doesnt exist before allocing it.
        Dcorner = [[XYPoint alloc] init];
    Dcorner.x = origin.x;
    Dcorner.y = origin.y + height;
}

//--------------------------------RETURN CORNER COORDS

-(XYPoint*) Acorner
{
    return Acorner;
}

-(XYPoint*) Bcorner
{
    return Bcorner;
}

-(XYPoint*) Ccorner
{
    return Ccorner;
}

-(XYPoint*) Dcorner
{
    return Dcorner;
}




-(Rectangle*) intersect: (Rectangle*) anotherRectangle
{
    if (! interRect) {
        interRect = [[Rectangle alloc] init];//---creates new rectangle if needed
    }
    [interRect setCorners];//------------------in effect creates and initializes corners
   
   
    interRect.Acorner.x = (anotherRectangle.Acorner.x > self.Acorner.x ? anotherRectangle.Acorner.x : self.Acorner.x);//--sets Acorner
   
   
   
    interRect.Acorner.y = (anotherRectangle.Acorner.y > self.Acorner.x ? anotherRectangle.Acorner.y : self.Acorner.y);
    interRect.origin = interRect.Acorner;//----------------------------------------------makes the origin the same as Acorner
   
    interRect.Bcorner.x = (anotherRectangle.Bcorner.x < self.Bcorner.x ? anotherRectangle.Bcorner.x : self.Bcorner.x);//--sets Bcorner
    interRect.Bcorner.y = (anotherRectangle.Bcorner.y > self.Bcorner.y ? anotherRectangle.Bcorner.y : self.Bcorner.y);

    interRect.Ccorner.x = (anotherRectangle.Ccorner.x < self.Ccorner.x ? anotherRectangle.Ccorner.x : self.Ccorner.x);//--sets Ccorner
    interRect.Ccorner.y = (anotherRectangle.Ccorner.y < self.Ccorner.y ? anotherRectangle.Ccorner.y : self.Ccorner.y);
   
    interRect.Dcorner.x = (anotherRectangle.Dcorner.x > self.Dcorner.x ? anotherRectangle.Dcorner.x : self.Dcorner.x);//--sets DCorner
    interRect.Dcorner.y = (anotherRectangle.Dcorner.y < self.Dcorner.y ? anotherRectangle.Dcorner.y : self.Dcorner.y);

    //---------if condition checks to see if there was intersection by comparing x and y values for Acorner and Bcor.. and Dcorner and Acor..
    if (interRect.Bcorner.x > interRect.Acorner.x && interRect.Dcorner.y > interRect.Acorner.y) {
       
        interRect.width = interRect.Bcorner.x - interRect.Acorner.x;//--------------------------Width
        interRect.height = interRect.Dcorner.y - interRect.Acorner.y;//-------------------------height
       
    //---------this bit is additional color fun for the intersecting rectangle
        interRect.fillColor=(anotherRectangle.fillColor>self.fillColor?anotherRectangle.fillColor-self.fillColor:self.fillColor-anotherRectangle.fillColor );//+++++++++++++++++++++sets fill color as difference between intersecting rectangles fill color
   
        interRect.lineColor=(anotherRectangle.lineColor>self.lineColor?anotherRectangle.lineColor-self.lineColor:self.lineColor-anotherRectangle.lineColor );//+++++++++++++++++++++sets line color as difference between intersecting rectangles line colo
       
        return interRect;
        }
       
    else//---------------this just makes every value zero if there is no intersection
        [[interRect Acorner]setX:0 andSetY:0 ];   
        [[interRect Bcorner]setX:0 andSetY:0 ];   
        [[interRect Ccorner]setX:0 andSetY:0 ];   
        [[interRect Dcorner]setX:0 andSetY:0 ]; 
        interRect.width = 0;
        interRect.height = 0;
        interRect.lineColor = 0;
        interRect.fillColor = 0;
   
        return interRect;

}

-(void) print//---------------prints it all so I don't have to, i find it useful to check where my efforts fail, or occasionaly succeed
{
    printf("your rectangle has the following properties...\n");
   
    printf("the origin is at (%f,%f)\n\n", origin.x, origin.y);
    printf("A coords are (%f,%f)\n", Acorner.x, Acorner.y);
    printf("B coords are (%f,%f)\n", Bcorner.x, Bcorner.y);
    printf("C coords are (%f,%f)\n", Ccorner.x, Ccorner.y);
    printf("D coords are (%f,%f)\n", Dcorner.x, Dcorner.y);

    printf("Has width...%f\n", self.width);
    printf("and height...%f\n", self.height);
   
    printf("and has area...%f\n", self.area);
    printf("and perimeter...%f\n\n\n", self.perimeter);
       
    [super print];//---------------for all those printy bits inherited from parent
   
   
   
}


-(void) printAllValues;//-------------redundant print method that only a fool would continue to use
{
    printf("Width is %f\nHeight is %f\nPerimeter is%f\nArea is %f", [self width], [self height], [self perimeter], [self area]);
}
@end





















Logged
thecheops
Newbie
*
Posts: 3


Email




Reply #3 on: February 23, 2012, 11:02:49 PM

This was my solution to the intersect: method:


-(Rectangle *)intersect:(Rectangle *)r {
   
    Rectangle *overlappingAreaRectangle = [[Rectangle alloc]init];
    XYPoint *overlappingRectangleOrigin = [[XYPoint alloc]init];
    XYPoint *rPoint1 = [[XYPoint alloc]init];
    XYPoint *rPoint2 = [[XYPoint alloc]init];
    XYPoint *rPoint3 = [[XYPoint alloc]init];
    XYPoint *rPoint4 = [[XYPoint alloc]init];
    [rPoint1 setX:r.origin.x andY:r.origin.y];
    [rPoint2 setX:(r.origin.x + r.width) andY:(r.origin.y)];
    [rPoint3 setX:(r.origin.x) andY:(r.origin.y+r.height)];
    [rPoint4 setX:(r.origin.x + r.width) andY:(r.origin.y+r.height)];
   
    if (([self containsPoint:rPoint1])||([self containsPoint:rPoint2])||([self containsPoint:rPoint3])||([self containsPoint:rPoint4])) {
   

   
            [overlappingRectangleOrigin setX:origin.x andY:r.origin.y];
            [overlappingAreaRectangle setOrigin:overlappingRectangleOrigin];
   
   
            overlappingAreaRectangle.width = ((r.origin.x + r.width)-origin.x);
            overlappingAreaRectangle.height = ((origin.y + height)-r.origin.y);
    }
         
    else {
        [overlappingRectangleOrigin setX:0 andY:0];
        [overlappingAreaRectangle setWidth:0 andHeight:0];
    }
    return overlappingAreaRectangle;
}
Logged
Hesadanza
Newbie
*
Posts: 28






Reply #4 on: February 24, 2012, 07:17:18 AM

This method only takes into account one configuration of the rectangles.  There are over 16 possible configurations.
Logged
urbanlung
Newbie
*
Posts: 13






Reply #5 on: February 27, 2012, 03:53:06 AM

Hi Hesadanza,

To which suggestion are you saying that only one configuration?

Ta
Logged
Pages: [1] Go Up
Print
Jump to:



Login with username, password and session length

Powered by MySQL Powered by PHP Powered by SMF 1.1.11 | SMF © 2006-2009, Simple Machines LLC Valid XHTML 1.0! Valid CSS!
Entire forum contents (c) 2009 classroomM.com. All rights reserved.