This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
tutorials:math_utilities [2011/07/07 11:20] – Added some explanation jollyblade | tutorials: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; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ====== 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, | ||
+ | |||
+ | <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: | ||
+ | |||
+ | + (SegmentIntersectionResult*) intersectSegmentsWithSegment: | ||
+ | + (BOOL) inSegmentWithPoint: | ||
+ | + (SegmentIntersectionResult*) segmentCircleIntersection: | ||
+ | + (BOOL) checkSegmentCircleIntersection: | ||
+ | |||
+ | @end | ||
+ | |||
+ | // Segment.m | ||
+ | |||
+ | #import " | ||
+ | |||
+ | #define SMALL_NUM | ||
+ | |||
+ | @implementation SegmentIntersectionResult | ||
+ | |||
+ | @synthesize i1, i2, resultValue; | ||
+ | |||
+ | @end | ||
+ | |||
+ | @implementation Segment | ||
+ | |||
+ | @synthesize p1, p2; | ||
+ | |||
+ | + (id) segmentWithP1: | ||
+ | |||
+ | Segment* seg = [[[Segment alloc] init] autorelease]; | ||
+ | seg.p1 = p1; | ||
+ | seg.p2 = p2; | ||
+ | return seg; | ||
+ | } | ||
+ | |||
+ | + (SegmentIntersectionResult*) intersectSegmentsWithSegment: | ||
+ | SegmentIntersectionResult* result = [[[SegmentIntersectionResult alloc] init] autorelease]; | ||
+ | SPPoint* | ||
+ | SPPoint* | ||
+ | SPPoint* | ||
+ | float D = [u perpPoint: | ||
+ | float puw = [u perpPoint: | ||
+ | float pvw = [v perpPoint: | ||
+ | |||
+ | 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){ | ||
+ | result.resultValue = 0; | ||
+ | return result; | ||
+ | } | ||
+ | result.i1 = s1.p1; | ||
+ | result.resultValue = 1; | ||
+ | return result; | ||
+ | } | ||
+ | if (du==0) { // S1 is a single point | ||
+ | if (![Segment inSegmentWithPoint: | ||
+ | result.resultValue = 0; | ||
+ | return result; | ||
+ | } | ||
+ | result.i1 = s1.p1; | ||
+ | result.resultValue = 1; | ||
+ | return result; | ||
+ | } | ||
+ | if (dv==0) { // S2 a single point | ||
+ | if (![Segment inSegmentWithPoint: | ||
+ | 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: | ||
+ | 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; | ||
+ | } | ||
+ | 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: | ||
+ | return result; | ||
+ | } | ||
+ | // they overlap in a valid subsegment | ||
+ | result.resultValue = 2; | ||
+ | result.i1 = [s2.p1 addPoint:[v scaleBy: | ||
+ | result.i2 = [s2.p1 addPoint:[v scaleBy: | ||
+ | return result; | ||
+ | } | ||
+ | |||
+ | // the segments are skew and may intersect in a point | ||
+ | // get the intersect parameter for S1 | ||
+ | float sI = [v perpPoint: | ||
+ | if (sI < 0 || sI > 1) { // no intersect with S1 | ||
+ | result.resultValue = 0; | ||
+ | return result; | ||
+ | } | ||
+ | |||
+ | // get the intersect parameter for S2 | ||
+ | float tI = [u perpPoint: | ||
+ | if (tI < 0 || tI > 1){ // no intersect with S2 | ||
+ | result.resultValue = 0; | ||
+ | return result; | ||
+ | } | ||
+ | |||
+ | result.resultValue = 1; | ||
+ | result.i1 = [s1.p1 addPoint:[u scaleBy: | ||
+ | return result; | ||
+ | } | ||
+ | |||
+ | // inSegment(): | ||
+ | // Return: YES when P is inside S | ||
+ | // NO when P is not inside S | ||
+ | + (BOOL) inSegmentWithPoint: | ||
+ | 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: | ||
+ | SPPoint* segV = [s.p2 subtractPoint: | ||
+ | SPPoint* ptV = [circlePosition subtractPoint: | ||
+ | float proj = [ptV dot:[segV normalize]]; | ||
+ | | ||
+ | SPPoint* projV = [[segV normalize] scaleBy: | ||
+ | SPPoint* closest; | ||
+ | if(proj < 0) { | ||
+ | closest = s.p1; | ||
+ | } else if(proj > [segV length]){ | ||
+ | closest = s.p2; | ||
+ | } else { | ||
+ | closest = [s.p1 addPoint: | ||
+ | } | ||
+ | | ||
+ | SPPoint* distV = [circlePosition subtractPoint: | ||
+ | if([distV length] < radius){ | ||
+ | return true; | ||
+ | } | ||
+ | return false; | ||
+ | } | ||
+ | |||
+ | |||
+ | + (SegmentIntersectionResult*) segmentCircleIntersection: | ||
+ | | ||
+ | SegmentIntersectionResult* result = [[[SegmentIntersectionResult alloc] init] autorelease]; | ||
+ | |||
+ | SPPoint* d = [s.p1 subtractPoint: | ||
+ | SPPoint* D = [s.p1 subtractPoint: | ||
+ | float a = [D dot: | ||
+ | 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: | ||
+ | result.i2 = [s.p1 addPoint:[D scaleBy: | ||
+ | return result; | ||
+ | } | ||
+ | |||
+ | @end | ||
+ | </ | ||
+ | |||
+ | ====== Hermite spline ====== | ||
+ | |||
+ | Hermite is a very useful spline implementation, | ||
+ | |||
+ | <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*) interpolate: | ||
+ | |||
+ | @end | ||
+ | |||
+ | // Hermite2D.m | ||
+ | #import " | ||
+ | |||
+ | @implementation Hermite2D | ||
+ | |||
+ | @synthesize a, b, t1, t2; | ||
+ | |||
+ | -(id) initWithData: | ||
+ | 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 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: | ||
+ | return p; | ||
+ | } | ||
+ | |||
+ | - (void) dealloc | ||
+ | { | ||
+ | [a release]; | ||
+ | [b release]; | ||
+ | [t1 release]; | ||
+ | [t2 release]; | ||
+ | [super dealloc]; | ||
+ | } | ||
+ | |||
+ | @end | ||
+ | </ | ||
+ | |||
+ | |||