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
  tutorials/math_utilities.txt · Last modified: 2013/03/05 10:19 (external edit)
 
Powered by DokuWiki