The following two functions are used in the below classes, that could go to SPPoint implementation.
- (float) perpPoint: (SPPoint*) point { return self.x * point.y - self.y * point.x; } - (float) dot: (SPPoint*) p { return self.x * p.x + self.y * p.y; }
Segment is specified by two SPPoints. The below intersection algorithm is very useful when programming AI, movement, collision detection for point or line-like entities, or if you just need to decide if two paths will cross each other or not in the future. Intersection result may give back a few results, 0 if no intersection, 1 if a single point, and 2, if the segments are overlapping, then it returns the overlapping common segment defined by the result points.
// Segment.h @interface SegmentIntersectionResult : NSObject { int resultValue; SPPoint* i1; SPPoint* i2; } @property (nonatomic, retain) SPPoint* i1; @property (nonatomic, retain) SPPoint* i2; @property int resultValue; @end @interface Segment : NSObject { SPPoint* p1; SPPoint* p2; } @property (nonatomic, retain) SPPoint* p1; @property (nonatomic, retain) SPPoint* p2; + (id) segmentWithP1: (SPPoint*) p1 p2: (SPPoint*) p2; + (SegmentIntersectionResult*) intersectSegmentsWithSegment: (Segment*) s1 s2: (Segment*) s2; + (BOOL) inSegmentWithPoint: (SPPoint*) p s: (Segment*) s; + (SegmentIntersectionResult*) segmentCircleIntersection: (Segment*) s circlePosition: (SPPoint*) circlePosition radius: (float) radius; + (BOOL) checkSegmentCircleIntersection: (Segment*) s circlePosition: (SPPoint*) circlePosition radius: (float) radius; @end // Segment.m #import "Segment.h" #define SMALL_NUM 0.00000001 @implementation SegmentIntersectionResult @synthesize i1, i2, resultValue; @end @implementation Segment @synthesize p1, p2; + (id) segmentWithP1: (SPPoint*) p1 p2: (SPPoint*) p2 { Segment* seg = [[[Segment alloc] init] autorelease]; seg.p1 = p1; seg.p2 = p2; return seg; } + (SegmentIntersectionResult*) intersectSegmentsWithSegment: (Segment*) s1 s2: (Segment*) s2 { SegmentIntersectionResult* result = [[[SegmentIntersectionResult alloc] init] autorelease]; SPPoint* u = [s1.p2 subtractPoint: s1.p1]; SPPoint* v = [s2.p2 subtractPoint: s2.p1]; SPPoint* w = [s1.p1 subtractPoint: s2.p1]; float D = [u perpPoint:v]; float puw = [u perpPoint:w]; float pvw = [v perpPoint:w]; if (fabs(D) < SMALL_NUM) { // s1 and s2 are parallel if (puw != 0 || pvw != 0) { result.resultValue = 0; // they are NOT collinear return result; } // they are collinear or degenerate // check if they are degenerate points float du = [u dot:u]; float dv = [v dot:v]; if (du==0 && dv==0) { // both segments are points if (s1.p1 != s2.p1){ // they are distinct points result.resultValue = 0; return result; } result.i1 = s1.p1; // they are the same point result.resultValue = 1; return result; } if (du==0) { // S1 is a single point if (![Segment inSegmentWithPoint: s1.p1 s: s2]){ // but is not in S2 result.resultValue = 0; return result; } result.i1 = s1.p1; result.resultValue = 1; return result; } if (dv==0) { // S2 a single point if (![Segment inSegmentWithPoint:s2.p1 s: s1]) { // but is not in S1 result.resultValue = 0; return result; } result.i1 = s2.p1; result.resultValue = 1; return result; } // they are collinear segments - get overlap (or not) float t0, t1; // endpoints of S1 in eqn for S2 SPPoint* w2 = [s1.p2 subtractPoint: s2.p1]; if (v.x != 0) { t0 = w.x / v.x; t1 = w2.x / v.x; } else { t0 = w.y / v.y; t1 = w2.y / v.y; } if (t0 > t1) { // must have t0 smaller than t1 float t=t0; t0=t1; t1=t; // swap if not } if (t0 > 1 || t1 < 0) { result.resultValue = 0; return result; // NO overlap } t0 = t0<0? 0 : t0; // clip to min 0 t1 = t1>1? 1 : t1; // clip to max 1 if (t0 == t1) { // intersect is a point result.resultValue = 1; result.i1 = [s2.p1 addPoint:[v scaleBy:t0]]; return result; } // they overlap in a valid subsegment result.resultValue = 2; result.i1 = [s2.p1 addPoint:[v scaleBy:t0]]; result.i2 = [s2.p1 addPoint:[v scaleBy:t1]]; return result; } // the segments are skew and may intersect in a point // get the intersect parameter for S1 float sI = [v perpPoint:w] / D; if (sI < 0 || sI > 1) { // no intersect with S1 result.resultValue = 0; return result; } // get the intersect parameter for S2 float tI = [u perpPoint:w] / D; if (tI < 0 || tI > 1){ // no intersect with S2 result.resultValue = 0; return result; } result.resultValue = 1; result.i1 = [s1.p1 addPoint:[u scaleBy:sI]]; return result; } // inSegment(): determine if a point is inside a segment // Return: YES when P is inside S // NO when P is not inside S + (BOOL) inSegmentWithPoint: (SPPoint*) p s: (Segment*) s { if (s.p1.x != s.p2.x) { // S is not vertical if (s.p1.x <= p.x && p.x <= s.p2.x) return YES; if (s.p1.x >= p.x && p.x >= s.p2.x) return YES; } else { // S is vertical, so test y coordinate if (s.p1.y <= p.y && p.y <= s.p2.y) return YES; if (s.p1.y >= p.y && p.y >= s.p2.y) return YES; } return NO; } + (BOOL) checkSegmentCircleIntersection: (Segment*) s circlePosition: (SPPoint*) circlePosition radius: (float) radius { SPPoint* segV = [s.p2 subtractPoint:s.p1]; SPPoint* ptV = [circlePosition subtractPoint:s.p1]; float proj = [ptV dot:[segV normalize]]; SPPoint* projV = [[segV normalize] scaleBy:proj]; SPPoint* closest; if(proj < 0) { closest = s.p1; } else if(proj > [segV length]){ closest = s.p2; } else { closest = [s.p1 addPoint:projV]; } SPPoint* distV = [circlePosition subtractPoint:closest]; if([distV length] < radius){ return true; } return false; } + (SegmentIntersectionResult*) segmentCircleIntersection: (Segment*) s circlePosition: (SPPoint*) circlePosition radius: (float) radius { SegmentIntersectionResult* result = [[[SegmentIntersectionResult alloc] init] autorelease]; SPPoint* d = [s.p1 subtractPoint:circlePosition]; SPPoint* D = [s.p1 subtractPoint:s.p2]; float a = [D dot:D]; float b = [d dot: D]; float c = [d dot: d] - radius * radius; float disc = b * b - a * c; if (disc < 0.0f) { result.resultValue = 0; return result; } float sqrtDisc = sqrtf(disc); float invA = 1.0f / a; float t[2]; t[0] = (-b - sqrtDisc) * invA; t[1] = (-b + sqrtDisc) * invA; result.i1 = [s.p1 addPoint:[D scaleBy:t[0]]]; result.i2 = [s.p1 addPoint:[D scaleBy:t[1]]]; return result; } @end
Hermite is a very useful spline implementation, easy to create wavelike surfaces, enemy movements, make motion look more natural.
// Hermite2D.h @interface Hermite2D : NSObject { SPPoint* a; SPPoint* b; SPPoint* t1; SPPoint* t2; } @property (nonatomic, retain) SPPoint* a; @property (nonatomic, retain) SPPoint* b; @property (nonatomic, retain) SPPoint* t1; @property (nonatomic, retain) SPPoint* t2; -(id) initWithData: (SPPoint*) start: (SPPoint*) end: (SPPoint*) tangentStart: (SPPoint*) tangentEnd; -(SPPoint*) interpolate: (float) s; @end // Hermite2D.m #import "Hermite2D.h" @implementation Hermite2D @synthesize a, b, t1, t2; -(id) initWithData: (SPPoint*) start: (SPPoint*) end: (SPPoint*) tangentStart: (SPPoint*) tangentEnd { self = [super init]; if(self){ self.a = start; self.b = end; self.t1 = tangentStart; self.t2 = tangentEnd; } return self; } // s goes from 0 - 1, returns the point on the curve between the start point and // endpoint, 0 means you are in startpoint, 1 means you are in end point. -(SPPoint*) interpolate: (float) s { float h1 = (2 * s*s*s) - (3 * s * s) + 1; float h2 = (-2 * s*s*s) + (3 * s * s); float h3 = (s*s*s) - (2 * s * s) + s; float h4 = (s*s*s) - (s * s); SPPoint* p = [[[[a scaleBy:h1] addPoint:[b scaleBy:h2]] addPoint:[t1 scaleBy:h3]] addPoint:[t2 scaleBy:h4]]; return p; } - (void) dealloc { [a release]; [b release]; [t1 release]; [t2 release]; [super dealloc]; } @end