matplotlib-users

[Matplotlib-users] find the projected distance between two curves

[G. A. <gio...@gm...>]

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

Re: [Matplotlib-users] find the projected distance between two curves

[Andrew S. <str...@as...>]

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 24-25, 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
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Matplotlib-users mailing list
> Mat...@li...
> https://lists.sourceforge.net/lists/listinfo/matplotlib-users

Re: [Matplotlib-users] find the projected distance between two curves

[G. A. <gio...@gm...>]

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....

Re: [Matplotlib-users] find the projected distance between two curves

[Andrew S. <str...@as...>]

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...

Re: [Matplotlib-users] find the projected distance between two curves

[G. A. <gio...@gm...>]

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 <str...@as...>:
> 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...
>