find the projected distance between two curves

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

linesnormalsketch.png

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
Matplotlib-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/matplotlib-users

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

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

Thanks Andrew, conceptually it's clear. Now I have to code it :slight_smile:
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@...106...>:

···

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