Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
tutorials:math_utilities [2011/07/08 08:07]
daniel [Segment implementation]
tutorials:math_utilities [2013/03/05 10:19] (current)
Line 1: Line 1:
 +====== Additions to SPPoint ======
 +
 +The following two functions are used in the below classes, that could go to SPPoint implementation. ​
 +
 +<code objc>
 +- (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;
 +}
 +</​code>​
 +
 +====== 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. ​
 +
 +<code objc>
 +// 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
 +</​code>​
 +
 +====== Hermite spline ======
 +
 +Hermite is a very useful spline implementation,​ easy to create wavelike surfaces, enemy movements, make motion look more natural. ​
 +
 +<code objc>
 +// 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
 +</​code>​
 +
 +
  
  tutorials/math_utilities.txt · Last modified: 2013/03/05 10:19 (external edit)
 
Powered by DokuWiki