====== Additions to SPPoint ======
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 implementation ======
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 spline ======
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