矩形重叠问题，碰撞算法，Objective-C实现

这个实际上是《Objective-C 2.0 程序设计》第八章 练习题第6题，觉得挺有意思，就分享一下。还没看答案，这个是我能想到的最优算法了，一会儿去看看答案如何。

已知矩形Rectangle类继承自GraphicObject类（这个类 和本次的操作没有任何关系）； 座标 XYPoint类，代码如下：

Rectangle类,Rectangle声明一个intersect方法，该方法传入一个矩形作为参数， 返回一个重叠的Recangle类型的对象，Rectangle类有座标origin作为属性，origin是XYPoint类型。

  1: //
  2: //  Rectangle.h
  3: //  Rectangle_prac_S4
  4: //
  5: //  Created by Jeff on 04.01.11.
  6: //  Copyright 2011  Uspython. All rights reserved.
  7: //
  8:
  9: #import <Foundation/Foundation.h>
 10: #import "XYPoint.h"
 11: #import "GraphicObject.h"
 12: @interface Rectangle : GraphicObject
 13: {
 14: 	double width;
 15: 	double height;
 16: 	XYPoint *origin;
 17: }
 18:
 19: @property double width,height;
 20:
 21: -(XYPoint *)origin;
 22: -(void)setOrigin:(XYPoint *)pt;
 23: -(void)setWidth:(double)w andHeight:(double)h;
 24: -(double)area;
 25: -(double)perimeter;
 26: -(XYPoint *)translate:(XYPoint *)ptv;
 27:
 28: -(Rectangle *)intersect:(Rectangle *)vRect;
 29: -(void)draw;
 30:
 31: -(void)dealloc;
 32:
 33:
 34: @end
这个类里面目前只有intersect方法，setOrigin方法，setWidth andHeight方法，以及width,height,origin属性是有用的；其余的没有用，不喜欢的可以删掉。
XYPoint类，定义座标的X,Y：
  1: //
  2: //  XYPoint.h
  3: //  Rectangle_prac_S4
  4: //
  5: //  Created by Jeff on 04.01.11.
  6: //  Copyright 2011 Uspython. All rights reserved.
  7: //
  8:
  9: #import <Foundation/Foundation.h>
 10:
 11: @interface XYPoint : NSObject
 12: {
 13: 	double x,y;
 14: }
 15: @property double x,y;
 16:
 17: -(void)setX:(double)xVal andY:(double)yVal;
 18:
 19: @end
 20:
实现XYPoint：
  1: //
  2: //  XYPoint.m
  3: //  Rectangle_prac_S4
  4: //
  5: //  Created by Jeff on 04.01.11.
  6: //  Copyright 2011 __MyCompanyName__. All rights reserved.
  7: //
  8:
  9: #import "XYPoint.h"
 10:
 11: @implementation XYPoint
 12:
 13: @synthesize  x,y;
 14:
 15: -(void)setX:(double)xVal andY:(double)yVal
 16: {
 17:   x=xVal;
 18:   y=yVal;
 19:
 20: }
 21:
 22: @end
 23:
实现Recangle :
  1: //
  2: //  Rectangle.m
  3: //  Rectangle_prac_S4
  4: //
  5: //  Created by Jeff on 04.01.11.
  6: //  Copyright 2011 __MyCompanyName__. All rights reserved.
  7: //
  8:
  9: #import "Rectangle.h"
 10: @implementation Rectangle
 11: @synthesize width,height;
 12: -(void)setWidth:(double)w andHeight:(double)h
 13: {
 14:   width=w;
 15:   height=h;
 16: }
 17: -(void)setOrigin:(XYPoint *)pt
 18: {
 19:   if(origin)
 20:   {
 21:     [origin release];
 22:   }
 23:   origin=[[XYPoint alloc] init];
 24:   [origin setX:pt.x andY:pt.y];
 25: }
 26: -(XYPoint *)origin
 27: {
 28:   return origin;
 29: }
 30:
 31: -(Rectangle *)intersect:(Rectangle *)vRect
 32: {
 33:   Rectangle *result=[[Rectangle alloc] init];
 34:   XYPoint *resultPoint=[[XYPoint alloc] init];
 35:
 36:   //得到两个矩形的中心点坐标
 37:
 38:   XYPoint *midPoint=[[XYPoint alloc] init];
 39:   XYPoint *vMidPoint=[[XYPoint alloc] init];
 40:
 41:   double mx,my,mvx,mvy;
 42:   mx=(origin.x+width)/2;
 43:   my=(origin.y+height)/2;
 44:   mvx=(vRect.origin.x+vRect.width)/2;
 45:   mvy=(vRect.origin.y+vRect.height)/2;
 46:   [midPoint setX:mx andY:my];
 47:   [vMidPoint setX:mvx andY:mvy];
 48:
 49:
 50:   //如果在x方向上 中心点间距离差的绝对值小于等于两个矩形宽的和的1/2，
 51:   //而且在y方向上中心点间距离差的绝对值小于等于两个矩形高的和的1/2，矩形重叠
 52:
 53:   if (abs(((midPoint.x+width/2)-(vMidPoint.x+vRect.width/2)))<=((width+vRect.width)/2) &&
 54:       abs(midPoint.y+height/2-vMidPoint.y-vRect.height/2)<=((height+vRect.height)/2))
 55:   {
 56:     //矩形重叠
 57:     //得到重叠矩形的原点坐标
 58:     double maxX,maxY,cX,cY;
 59:     //二者相比较，始终取坐标大的那个
 60:     maxX=origin.x>=vRect.origin.x?origin.x:vRect.origin.x;
 61:     maxY=origin.y>=vRect.origin.y?origin.y:vRect.origin.y;
 62:     //取原点坐标对角线上的另一个坐标（cX，cY）
 63:     //始终取坐标小的那个
 64:     cX=(vRect.origin.x+vRect.width)>=(origin.x+width)?(origin.x+width):(vRect.origin.x+vRect.width);
 65:     cY=(vRect.origin.y+vRect.height)>=(origin.y+height)?(origin.y+height):(vRect.origin.y+vRect.height);
 66:     //确定原点坐标，计算出长度和宽度
 67:     [resultPoint setX:maxX andY:maxY];
 68:     result.origin=resultPoint;
 69:     result.width=abs(maxX-cX);
 70:     result.height=abs(maxY-cY);
 71:     //释放两个矩形中间点坐标内存
 72:     [midPoint release];
 73:     [vMidPoint release];
 74:     return result;
 75:
 76:   }else {
 77:     [resultPoint setX:0 andY:0];
 78:     result.origin=resultPoint;
 79:     result.width=0;
 80:     result.height=0;
 81:     [midPoint release];
 82:     [vMidPoint release];
 83:     return result;
 84:   }
 85:
 86: }
 87:
 88: -(double)area
 89: {
 90:   return (double)height*width;
 91: }
 92: -(double)perimeter
 93: {
 94:   return ((double)height+width)*2;
 95: }
 96:
 97: -(XYPoint *)translate:(XYPoint *)ptv
 98: {
 99:
100:   XYPoint *result=[[XYPoint alloc] init];
101:   [result setX:origin.x+ptv.x andY:origin.y+ptv.y];
102:
103:   return result;
104:
105: }
106:
107: -(void)dealloc
108: {
109:   if (origin) {
110:     [origin release];
111:   }
112:   [super dealloc];
113: }
114:
115: -(void)draw
116: {
117:   for(int i=0;i<(int)width;i++)
118:     printf("-");
119:   printf("\n");
120:   for(int i=0;i<(int)height;i++)
121:   {
122:     printf("|");
123:     for(int j=0;j<(width-2);j++)
124:       printf(" ");
125:     printf("|");
126:     printf("\n");
127:   }
128:   for(int i=0;i<(int)width;i++)
129:     printf("-");
130:   printf("\n");
131: }
132: @end
133:
测试intersect方法：
  1: #import "Rectangle.h"
  2: #import "XYPoint.h"
  3:
  4: int main (int argc, const char * argv[]) {
  5:     NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
  6:   Rectangle *myRect=[[Rectangle alloc] init];
  7:   XYPoint *myPoint=[[XYPoint alloc] init];
  8:
  9:   [myPoint setX:200 andY:100];
 10:   [myRect setWidth:300 andHeight:200];
 11:   myRect.origin=myPoint;
 12:
 13:   NSLog(@"rectangle w=%g,h=%g",myRect.width,myRect.height);
 14:
 15:   NSLog(@"origin at (%g,%g)",myRect.origin.x,myRect.origin.y);
 16:
 17:   //重叠测试
 18:   Rectangle *testRect=[[Rectangle alloc] init],*newRect;
 19:   XYPoint *testPoint=[[XYPoint alloc] init];
 20:   [testPoint setX:300 andY:50];
 21:   testRect.origin=testPoint;
 22:   testRect.height=350;
 23:   testRect.width=100;
 24:   NSLog(@"testRect  w=%g,h=%g",testRect.width,testRect.height);
 25:
 26:   NSLog(@"origin at (%g,%g)",testRect.origin.x,testRect.origin.y);
 27:   newRect= [myRect intersect:testRect];
 28:   NSLog(@"重叠矩形原点坐标为(%g,%g)  width is %g height is %g",newRect.origin.x,newRect.origin.y,newRect.width,newRect.height);
 29:
 30:
 31:   [testPoint release];
 32:   [testRect release];
 33:   [newRect release];
 34:   [myRect release];
 35:   [myPoint release];
 36:
 37:
 38:     [pool drain];
 39:     return 0;
 40: }
 41:
测试结果：
2011-01-07 22:51:31.139 Rectangle_prac_S4[915:80f] rectangle w=300,h=200
2011-01-07 22:51:31.182 Rectangle_prac_S4[915:80f] origin at (200,100)
2011-01-07 22:51:31.207 Rectangle_prac_S4[915:80f] testRect  w=100,h=350
2011-01-07 22:51:31.218 Rectangle_prac_S4[915:80f] origin at (300,50)
2011-01-07 22:51:31.222 Rectangle_prac_S4[915:80f] 重叠矩形原点坐标为(300,100)  width is 100 height is 200
试试别的参数，应该也是正确的。.
全部代码打包下载猛击这里