From: G. Allegri <giohappy@gm...>  20090219 13:35:49
Attachments:
linesnormalsketch.png

Hello list, I'm completely new to matplotlib and I'm not a computer scientist (not a good starting point!) but I need to solve a geometric/graphical problem. I've been asked to find a method, in Python, to find the distance between a 2D polynomial curve, derived from least squares interpolation on a set of points, and a curve locallly interpolating another set of points.  the starting line is a smooth line, while the second should describe a path passing exactly thorugh the given points.  the distance should be the one along the normal to the first line I attach a sketch to explain this. Is there an heuristic, an algorithm, to solve this problem in an efficient way (I have to apply it to thousands couples of sets from sonar and seismic acquisitions)? Is the mapltolip API useful for this? Thanks in advance, Giovanni 
From: Andrew Straw <strawman@as...>  20090220 06:21:36

G. Allegri wrote: > Hello list, > I'm completely new to matplotlib and I'm not a computer scientist (not > a good starting point!) but I need to solve a geometric/graphical > problem. > I've been asked to find a method, in Python, to find the distance > between a 2D polynomial curve, derived from least squares > interpolation on a set of points, and a curve locallly interpolating > another set of points. Do you really need the distance to be relative to the interpolated curve? Why not to the points which are being interpolated? Then the answer is just: Sum_i dist(point_i,polynomial_curve) Where dist() can be arrived at in closed form... Otherwise, I guess it would depend on the interpolation, which you didn't really specify. > >  the starting line is a smooth line, while the second should > describe a path passing exactly thorugh the given points. >  the distance should be the one along the normal to the first line > > I attach a sketch to explain this. > > Is there an heuristic, an algorithm, to solve this problem in an > efficient way (I have to apply it to thousands couples of sets from > sonar and seismic acquisitions)? Is the mapltolip API useful for this? > > Thanks in advance, > Giovanni > > >  > > >  > >  > Open Source Business Conference (OSBC), March 2425, 2009, San Francisco, CA > OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise > Strategies to boost innovation and cut costs with open source participation > Receive a $600 discount off the registration fee with the source code: SFAD > http://p.sf.net/sfu/XcvMzF8H > > >  > > _______________________________________________ > Matplotlibusers mailing list > Matplotlibusers@... > https://lists.sourceforge.net/lists/listinfo/matplotlibusers 
From: G. Allegri <giohappy@gm...>  20090220 08:51:26

Hi Andrew. With dist(point_i,polynomial_curve) do you mean point_i belonging to the Line 2 set of points and pol_curve as Line 1? In this case it could be reasonably ok for me. How can I derive the closed form for dist()? Excuse my ignorance with geometry.... 
From: Andrew Straw <strawman@as...>  20090220 10:32:43

G. Allegri wrote: > Hi Andrew. > With dist(point_i,polynomial_curve) do you mean point_i belonging to > the Line 2 set of points and pol_curve as Line 1? yes > In this case it > could be reasonably ok for me. How can I derive the closed form for > dist()? Excuse my ignorance with geometry.... > Take the equation for line 1parameterized by s. Something like f(s) = (x,y) = (as**2 + bs +c, ds**2 + es + f ) for your polynomial model. Now, the distance for that point on line 1 from point i is dist(point_i, f(s)), where dist can be Euclidean distance, for example. So, the question is what value of s minimizes the distance. Since this function will be smallest at an inflection, just take the derivative of your distance function and solve for it to be equal to zero. Hopefully this function will be convex and you'll have only one zero, which will tell you the value of s where distance is a minimum. Otherwise, pick the inflection at the closest distance. Finally, repeat for all points i and sum the results. Hopefully that helps on the conceptual side. Sympy will be more useful than matplotlib on the coding side... 
From: G. Allegri <giohappy@gm...>  20090220 11:02:20

Thanks Andrew, conceptually it's clear. Now I have to code it :) I will have a look to SimPy, and also to SciPy/NumPy I will let you know how it's going on. 2009/2/20 Andrew Straw <strawman@...>: > G. Allegri wrote: >> >> Hi Andrew. >> With dist(point_i,polynomial_curve) do you mean point_i belonging to >> the Line 2 set of points and pol_curve as Line 1? > > yes > >> In this case it >> could be reasonably ok for me. How can I derive the closed form for >> dist()? Excuse my ignorance with geometry.... >> > > Take the equation for line 1parameterized by s. Something like f(s) = (x,y) > = (as**2 + bs +c, ds**2 + es + f ) for your polynomial model. Now, the > distance for that point on line 1 from point i is dist(point_i, f(s)), where > dist can be Euclidean distance, for example. > > So, the question is what value of s minimizes the distance. Since this > function will be smallest at an inflection, just take the derivative of your > distance function and solve for it to be equal to zero. Hopefully this > function will be convex and you'll have only one zero, which will tell you > the value of s where distance is a minimum. Otherwise, pick the inflection > at the closest distance. Finally, repeat for all points i and sum the > results. > > Hopefully that helps on the conceptual side. Sympy will be more useful than > matplotlib on the coding side... > 