Re: Working with mathematical errors
Re: Working with mathematical errors
- Subject: Re: Working with mathematical errors
- From: Graham Cox <email@hidden>
- Date: Mon, 28 Jul 2008 14:23:51 +1000
On 28 Jul 2008, at 11:41 am, Ashley Perrien wrote:
Given a couple points on a line I can find the intersection point
but since 2 line segments may not intersect, I then check:
if([lineOne containsPoint: intersectionPoint])
That will nearly always fail
Yep, it nearly always will. It's not so much because of the floating
point inaccuracies but because the methodology is flawed. A line in
mathematical terms is infinitely thin, so it cannot really "contain" a
point unless the point is exactly on the line. So using this as a test
for intersection requires infinite precision.
Luckily there are simple solutions that don't require this kind of
precision. Here's one I use frequently:
NSPoint Intersection2( const NSPoint p1, const NSPoint p2, const
NSPoint p3, const NSPoint p4 )
{
// return the intersecting point of two line SEGMENTS p1-p2 and p3-
p4, whose end points are given. If the lines are parallel or do not
intersect,
// the result is -1,-1. Uses an alternative algorithm from
Intersection() - this is faster and more usable. This only returns a
// point if the two segments actually intersect - it doesn't project
the lines.
float d = (p4.y - p3.y)*(p2.x - p1.x) - (p4.x - p3.x)*(p2.y - p1.y);
// if d is 0, then lines are parallel and don't intersect
if ( d == 0.0 )
return NSMakePoint( -1, -1 );
float ua = ((p4.x - p3.x)*(p1.y - p3.y) - (p4.y - p3.y)*(p1.x -
p3.x))/d;
float ub = ((p2.x - p1.x)*(p1.y - p3.y) - (p2.y - p1.y)*(p1.x -
p3.x))/d;
// if ua or ub is outside the range 0..1 then the lines don't
intersect within their length
if( ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0 )
{
// segments do intersect
NSPoint ip;
ip.x = p1.x + ua*(p2.x - p1.x);
ip.y = p1.y + ub*(p2.y - p1.y);
return ip;
}
else
return NSMakePoint( -1, -1 );
}
This utility function takes two lines in the form of four end points -
easy enough to derive. What I like about this method over the more
usual line intersection code you find online is that this inherently
tests for intersection at the same time as deriving the intersection
point. Most code treats the lines as extending to infinity and returns
the point where they would intersect if of infinite length. For
practical graphics work, that's usually not what you require.
For use with NSBezierPath, you have to do more work to extract
segments in this form. You can flatten a curve to a series of line
segments using -bezierPathByFlatteningPath: or there are other
mathematical ways to find an intersection of a curved segment (at some
level they all involve flattening to a line segment however since
there is no known mathematical solution to the intersection of a
bezier curve that can be derived purely from its control points
alone). If your paths don't contain any curve segments then there's no
need to flatten - just walk the path and use the above function.
Also, I recently discovered some similar code as part of the public-
domain stuff that was released by Omni as part of their public
frameworks. NSBezierPath-OAExtensions includes some utilities that
find all the intersections of any two NSBezierPaths which saves a lot
of time figuring out how to implement all this.
hth,
Graham
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden