Hi Jake, I've just started to calculate the case of Bezier2, in order to obtain the algorithm. I am glad that you found the solution. This also saved me from the calculation.
If a curve is defined by a bunch of points, I propose a simple algorithm that should work for most of the cases (excluding some cases with inflection points): (1) Calculate the 3 distances - 2 to the end points of the curve and one to a middle point. (2) Continue with the curve limited by the end point with shortest distance and the middle point. Now you are left with a curve of about half of the length of the previous. (3). Calculate the distance of the middle point of the new curve. (4). You have now again two end points and and one middle. From here on repeat (2) and (3) till you get the required minimal distance. This algorithm lets you calculate number of distances much lower than the number of the total points of the curve. For instance if you have 1000 points in total, you'll finish with calculating about 10 distances. Good luck, Samy --- In svg-developers@yahoogroups.com, "Jake Beard" <[EMAIL PROTECTED]> wrote: > > I found the solution in Graphics Gems, by way of www.algorithmist.net/, a > very excellent web site and blog that seems to have many resources for > people attempting to do serious computer graphics work in ActionScript and > Flash: > > http://tog.acm.org/GraphicsGems/ > http://tog.acm.org/GraphicsGems/gems/NearestPoint.c > > There are also a few implementations of this code in ActionScript: > > http://code.google.com/p/bezier/ > http://algorithmist.wordpress.com/2008/08/15/closest-point-on-bezier-code/ > > In the next day or two, I'll attempt to do a clean re-implementation of the > C implementation in JavaScript, in such a way that it does not depend on > external libraries, but makes heavy use of SVG's data structures and API's, > the goal being to make it general and reusable, but specific to SVG. > > Jake > > On Thu, Sep 11, 2008 at 4:12 PM, ddailey <[EMAIL PROTECTED]> wrote: > > > Not exactly the same subject, but an important reference for folks whose > > calculus with parametric curves is not what it used to be: > > > > http://www.kevlindev.com/geometry/index.htm > > > > David > > I recall someone (maybe Samy) posted a full solution to such a problem here > > within the past three months. Sounds like something to put in the community > > web site? > > > > > > ----- Original Message ----- > > From: Jake Beard > > To: svg-developers@yahoogroups.com <svg-developers%40yahoogroups.com> > > Sent: Thursday, September 11, 2008 3:55 PM > > Subject: Re: [svg-developers] Re: efficient method for calculating min > > distance from point to curve > > > > Samy, > > > > Thank you for the quick response. I am not very familiar with the > > mathematics of bezier curves. Is there a deterministic way of converting > > converting an SVG path from its representation in XML markup to an analytic > > representation, so that the calculus minimization may be applied? > > > > Thanks and I look forward to hearing what you think, > > > > Jake > > > > On Thu, Sep 11, 2008 at 3:37 PM, Samuel Dagan <[EMAIL PROTECTED]<dagan%40post.tau.ac.il>> > > wrote: > > > > > Hi Jake, > > > If the curve is known analytically, it is an elementary minimization > > > exercise of calculus. If your curve is just a bunch of points, then > > > you do it numerically in JavaScript. The time depends on the number of > > > points and the accuracy depends on the density of the points. There is > > > no better way to estimate the time, but just by experimenting. Cheers, > > > Samy > > > > > > --- In svg-developers@yahoogroups.com <svg-developers%40yahoogroups.com><svg-developers% > > 40yahoogroups.com>, > > > "Jake Beard" <otakuj462@> wrote: > > > > > > > > I have what I think must be a fairly common requirement: I need an > > > efficient > > > > method for calculating the minimum distance from a point to a curve. It > > > > would be possible to solve this problem numerically in JavaScript, > > > but I'm > > > > not confident that JavaScript would be efficient enough, and I'm > > > wondering > > > > if there isn't something built into the SVG spec that might be > > > leveraged to > > > > help with this. > > > > > > > > I'd appreciate any guidance anyone can offer. Thanks, > > > > > > > > Jake > > > > > > > > > > > > [Non-text portions of this message have been removed] > > > > > > > > > > > > > > > > > [Non-text portions of this message have been removed] > > > > [Non-text portions of this message have been removed] > > > > > > > > > [Non-text portions of this message have been removed] > ------------------------------------ ----- To unsubscribe send a message to: [EMAIL PROTECTED] -or- visit http://groups.yahoo.com/group/svg-developers and click "edit my membership" ----Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/svg-developers/ <*> Your email settings: Individual Email | Traditional <*> To change settings online go to: http://groups.yahoo.com/group/svg-developers/join (Yahoo! ID required) <*> To change settings via email: mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] <*> To unsubscribe from this group, send an email to: [EMAIL PROTECTED] <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/
