Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
tutorials:math_utilities [2011/07/07 11:20] – Added some explanation jollybladetutorials:math_utilities [2013/03/05 10:19] (current) – external edit 127.0.0.1
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 by 127.0.0.1
 
Powered by DokuWiki