Re: Finding crossing of Bezie curves

On Mon, 05 Sep 2005 06:53:38 -0500, Richard J Kinch
<kinch@xxxxxxxxxxx> wrote:
>Just d' FAQs writes:
>> Sorry, no. In fact, two degree 3 Bezier curves may intersect in 9
>> points, the solutions of a degree 9 equation. ...
>> split one of the curves in half
>> and test the two halves against the other curve bounds. Repeat until
>> satisfied (or bored with splitting). This is a simple as it gets.
>
>This only works for nice cases having incisive intersections. The general
>problem is far more difficult.

This works for all cases, depending on the definition of "satisfied".
Given the level of the question (and language skills), belaboring the
niceties seemed premature. But, yes, we can easily construct two
curves meeting at a point with the same first and second derivatives;
slight perturbations (deliberate, or caused by floating point) can
turn that into a nightmare.

----------
BezierIntersection.svg
----------
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20010904//EN"
"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd";>
<svg width="420px" height="297px" viewBox="0 0 140 99"
xmlns="http://www.w3.org/2000/svg"; xml:lang="en-US">
<style type="text/css">
.bord {stroke: none; stroke-width: 0.010; fill: #eeeeee}
.crv {stroke: black; stroke-linecap: round}
.eYellow {stroke: #fec200; fill: #fec200}
.eBlue {stroke: #0081cd; fill: #0081cd}
.crv {stroke-width: 0.20; fill: none}
.fat {stroke-width: 0.40}
</style>
<title>Bezier intersection</title>
<desc>Nasty tangency for Bezier intersection</desc>
<rect x="0" y="0" width="140" height="99" class="bord" />
<g transform="translate(10,50) scale(1,-1) scale(15)">
<path d="M8,3 C -4,-3 0,3 4,-3" class="crv fat eBlue" />
<path d="M0,0 C 0,0 2,0 4,3" class="crv eYellow" />
</g>
</svg>
----------

.

Relevant Pages

  • Re: Finding crossing of Bezie curves
    ... Just d' FAQs writes: ... two degree 3 Bezier curves may intersect in 9 ...
    (comp.graphics.algorithms)
  • Re: Quadratic Bezier intersection (a special case)
    ... Both are monotone in the x- and y-components. ... I also need to estimate whether the curves can potentially ... intersect to get rid of expensive operations in most cases ... rather small one Q0Q1Q2, the triangle Q is completely inside in P, then ...
    (comp.graphics.algorithms)
  • Overlap of two Bezier curves
    ... As in my former thread, I have two Bezier curves B1 and B2, differing only in their control point. ... I use the code posted by Eduardo to find the parameters t and u in for which the curves intersect. ... Now I need to determine the overlap of the areas bounded by each curve and the stright line between begin and end point. ...
    (comp.graphics.algorithms)
  • Re: Ilford Multigrade IV vs. Kentmere Fineprint?
    ... I wouldn't put much faith in the published curves. ... intersect at density 0.2 to 0.4, which could be useful and ... I think I see what you mean on the Ilford curves between densities 1.0 to ...
    (rec.photo.darkroom)
  • Re: Quadratic Bezier intersection (a special case)
    ... Both are monotone in the x- and y-components. ... I also need to estimate whether the curves can potentially ... intersect to get rid of expensive operations in most cases ... curves may potentially intersect (false positives are OK, ...
    (comp.graphics.algorithms)
Loading