矩形重叠问题,碰撞算法,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: @end20:实现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 XYPoint12:13: @synthesize x,y;14:15: -(void)setX:(double)xVal andY:(double)yVal16: {17: x=xVal;18: y=yVal;19:20: }21:22: @end23:实现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 Rectangle11: @synthesize width,height;12: -(void)setWidth:(double)w andHeight:(double)h13: {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 *)origin27: {28: return origin;
29: }30:31: -(Rectangle *)intersect:(Rectangle *)vRect32: {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 *)ptv98: {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: @end133:测试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
试试别的参数,应该也是正确的。.