Re: NSBezierPath intersection
Re: NSBezierPath intersection
- Subject: Re: NSBezierPath intersection
- From: Nicko van Someren <email@hidden>
- Date: Fri, 29 Apr 2005 09:53:31 +0100
On 28 Apr 2005, at 22:19, glenn andreas wrote:
On Apr 28, 2005, at 4:01 PM, Linea Tessile srl wrote:
Does anybody know how calculate the intersection point between two
lines created using an NSBezierPath?
Since NSBezierPath's contain curves, there is no "the intersection
point". Even if both are just a single curve (and an NSBezierPath is
more like a complex polygon since it can contain multiple "line to"s
and "curve to"s, not to mention multiple discontinuous shapes - an
entire page of text outlines could be a single NSBezierPath), there
still isn't a single interesection point (I can think of a case that
gives six points of intersection).
It should be noted that you can actually find the intersection between
two curve segments, but the math is hideous. You can boil it down to a
ninth order polynomial and as such the curves can cross at anywhere
between zero and nine places. My advice is don't bother; instead...
You're best bet is to use bezierPathByFlatteningPath to get a bezier
path composed only of straight lines and then do standard line
intersection tests between each segment of each of the bezier paths
(and yes, this can get real expensive real quick).
There are some tricks for speeding this up, especially if you know that
you'll be checking the intersection of various different paths against
some path that remains constant. There is an algorithm called the
"line sweep" method, which relies on the fact that if two line segments
intersect each other then they must both at some point either intersect
or be parallel to the same vertical line as it is swept across the
field. The bulk of the running time in this is due to sorting the list
of segments (e.g. by the x co-ordinate of the left hand end) which is
an n.log(n) process and if one of your paths is constant you can
pre-sort that set of line segments.
Cheers,
Nicko
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden