Re: Benchmarked: [NSBezierPath containsPoint:]
Re: Benchmarked: [NSBezierPath containsPoint:]
- Subject: Re: Benchmarked: [NSBezierPath containsPoint:]
- From: "Erik M. Buck" <email@hidden>
- Date: Mon, 1 Oct 2001 15:21:54 -0500
The general technique for fast point intersection with arbitrary paths is to
cull the paths being searched.
Each path element (curve) has a bounding rectangle. If the point is not in
the rectangle, don't bother trying to intersect the path element (curve)
with the point.
Once you have found the collection of curves who's bounding rectangles
include the point, you can use a loop similar to the one shown to find an
intersection. Curves are not allowed to cross. In other words, there are
no figure eights made with a single curve. Therefore, once the path of a
curve has moved from one side of the point to the other side, you can be
sure that you have either found the intersection or there isn't one so stop
searching. The determination of "side" is as follows: Imagine a Cartesian
coordinate system with origin aligned with the point of interest. As you
walk a curve, if you are in Quadrant I of the coordinate system, mark it as
"already checked". Do the same for quadrant II and so on. If at any time
all quadrants are marked "already checked" and you still don't have a match
then you can stop searching because there can't be a match. Having crossed
through all of the quadrants, there is no way for the curve to loop back to
hit the point.
----- Original Message -----