StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Intersection of Bezier curves is done by the (very cool) <a href="http://asymptote.sourceforge.net/" rel="noreferrer">Asymptote</a> vector graphics language: look for <code>intersect()</code> <a href="http://asymptote.sourceforge.net/doc/Paths-and-guides.html" rel="noreferrer">here</a>.</p> <p>Although they don't explain the algorithm they actually use there, except to say that it's from p. 137 of "The Metafont Book", it appears that the key to it is two important properties of Bezier curves (which are explained elsewhere on that site though I can't find the page right now):</p> <ul> <li>A Bezier curve is always contained within the bounding box defined by its 4 control points</li> <li>A Bezier curve can always be subdivided at an arbitrary <em>t</em> value into 2 sub-Bezier curves</li> </ul> <p>With these two properties and an algorithm for intersecting polygons, you can recurse to arbitrary precision:</p> <h2>bezInt(B<sub>1</sub>, B<sub>2</sub>):</h2> <ol start="2"> <li>Does bbox(B<sub>1</sub>) intersect bbox(B<sub>2</sub>)? <ul> <li>No: Return false.</li> <li>Yes: Continue.</li> </ul></li> <li>Is area(bbox(B<sub>1</sub>)) + area(bbox(B<sub>2</sub>)) < threshold? <ul> <li>Yes: Return true.</li> <li>No: Continue.</li> </ul></li> <li>Split B<sub>1</sub> into B<sub>1a</sub> and B<sub>1b</sub> at <em>t</em> = 0.5</li> <li>Split B<sub>2</sub> into B<sub>2a</sub> and B<sub>2b</sub> at <em>t</em> = 0.5</li> <li>Return bezInt(B<sub>1a</sub>, B<sub>2a</sub>) || bezInt(B<sub>1a</sub>, B<sub>2b</sub>) || bezInt(B<sub>1b</sub>, B<sub>2a</sub>) || bezInt(B<sub>1b</sub>, B<sub>2b</sub>).</li> </ol> <p>This will be fast if the curves don't intersect -- is that the usual case?</p> <p><strong>[EDIT]</strong> It looks like the algorithm for splitting a Bezier curve in two is called <a href="http://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm" rel="noreferrer">de Casteljau's algorithm</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload