Re: fast intersection calculation between bezier & rectangle

On May 20, 12:39 am, "Dave Eberly" <dNOSPAMebe...@xxxxxxxxxxxxxxx>
wrote:
<Ylem...@xxxxxxxxx> wrote in message

news:1179564418.999716.61620@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

I'm currently working on a 2D drawing app which allows users to
drag their mouses in the canvas to select from a lot of bezier curves.
To figure out which bezier curves are selected seems a bit difficult
to me.
I tried to sample the bezier into dozens of line segments and
calculate the intersection between the line segments and the selection
rectangle, but it seems not very efficient (especially when the number
of curves grows to 50+)

Can anyone give me some suggestions on how to figure out the
intersect set much more efficiently, please?

Using your approach, preprocess the line segments of the polylines
that approximate the curves. Compute the axis-aligned bounding boxes
of the segments. Sort the projections of these relative to the x-axis.
Now when a user creates a tracking rectangle, you can quickly locate
which segments the rectangle edges potentially intersect by locating
those axis-aligned boxes that the rectangle edges intersect. The idea
is effectively that ofhttp://www.cs.cmu.edu/~baraff/sigcourse/notesd2.pdf.

Also look at the recent thread in this newsgroup; the subject is
"Intersection of bezier and straight line". You can compute the
intersection of rectangle edge and Bézier curve directly by converting
the problem to computing the roots of a polynomial. Finding roots can
also be computationally expensive. As a quick "no intersection", you
can use Sturm sequences for the polynomial and test whether the
polynomial has no real-valued roots, in which case the edge does not
intersect the curve. These tests involve only basic arithmetic operations.

--
Dave Eberlyhttp://www.geometrictools.com

thanks for your help
it helps me greatly :)

PS: Dave, I can't open geometrictools.com in my browser when I was
trying to find some material (many people suggest your web site) on
this topic. (from China)

The firefox says:
"The connection was reset
The connection to the server was reset while the page was loading."

.

Relevant Pages

  • Re: fast intersection calculation between bezier & rectangle
    ... drag their mouses in the canvas to select from a lot of bezier curves. ... those axis-aligned boxes that the rectangle edges intersect. ... "Intersection of bezier and straight line". ...
    (comp.graphics.algorithms)
  • Re: [help] fast intersection calculation between bezier & rectangle
    ... drag their mouses in the canvas to select from a lot of bezier curves. ... those axis-aligned boxes that the rectangle edges intersect. ... "Intersection of bezier and straight line". ...
    (comp.graphics.algorithms)
  • Re: [help] fast intersection calculation between bezier & rectangle
    ... drag their mouses in the canvas to select from a lot of bezier curves. ... Now when a user creates a tracking rectangle, ... "Intersection of bezier and straight line". ...
    (comp.graphics.algorithms)
  • Re: Curve implicitization from parametrization
    ... it's hard for me to judge the likelihood that Tony knows, ... In general, for K either C or R, there exist polynomials F_1,.., ... it is not always the case that G is such an intersection *as ... space curves G is incomplete and may remain so forever). ...
    (sci.math)
  • Re: approximating rational curves
    ... The curves I deal with usually come from an iges file, ... I am aware of the existence of interval arithmetic for Bezier curves ... Also approximating a rational Bezier curve by non rational cubic ... "Approximating Rational Curves Using Polynomial Curves" ...
    (comp.graphics.algorithms)