Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi. Imagine that a user draws on the canvas any path. I want to approximate this path with a path $P(x,y)=0$ where $P(x,y)$ - is unknown polynom. May be somebody can suggest an appropriate algorithm?

1) I tried to use the method of least squares to find this polynom. Just choosed on the path a lot of points $(x_i,y_i)$ . And minimized unknown $\sum\limits_i P(x_i,y_i)^2$ among all polinoms of degree n. This problem of minimization is a problem of finding an eigen vector of huge matrix that grows as $n^2\times n^2$. Already for $n=7$ this matrix has a size $36\times36$ it's hard work for PC to find the solution. And for $n=7$ it doesn't give appropriate result.

2) Spline doesn't work for me. Because spline - is a union of curves $P_i(x,y)=0$. To each spline of course we can correspond $P(x,y)=\prod\limits_i P_i(x,y) $. But this union $P(x,y)=0$ will have a lot of bifurcation points on the curve. And for my project it is very bad

share|improve this question
    
What sort of path is it (e.g. a simple closed loop), of what regularity, and in what sense (in what norm) do you want to approximate it. –  Pietro Majer Jun 5 '12 at 12:48
    
I want to write following a programm. User draw any path (let say his signature) and programm costruct the mechanical linkage that can draw this path. Because of the "Kempe linkage theorem" I know that it is poossible for any algebraic path P(x,y)=0. –  David Jun 5 '12 at 14:18
1  
About your first solution: the matrix size should not be a problem. I just measured the execution time of Matlab function eig(), which computes eigenvalues: it runs 6 milliseconds for 500 x 500 matrix. Have you implemented the eigenvalue computation by yourself? Which programming language have you used? –  Stanislav Jun 5 '12 at 17:52
    
Stanislav, because I am writing web application I write everything on Javascript and use JS library "numeric". Thank you for your comment. It seems that it exists much faster algorithms that in my library. Then I'll try to write my own eig() function. –  David Jun 6 '12 at 12:08
4  
@David, given your comments, you are actually interested in a slightly different problem: Given a map $f:[a,b]\to R^2$, approximate $f$ by a polynomial map $p:[a,b]\to R^2$. This should be easier to do than your original problem. Once you find such p, then you can construct a "functional" mechanical linkage L which would "draw" the map p. We explain how to do it in the paper with John Millson "Universality theorems for configuration spaces of planar linkages", which you can find at arxiv.org/abs/math/9803150 –  Misha Jun 8 '12 at 17:22
show 5 more comments

1 Answer 1

This is a very hard problem to do right. The simplest solution is to sample your polynomial on a grid, and for every pair of adjacent grid points where the sign changes, find a zero (exactly or approximately) on the relevant edge, then connect nearby zeros by segments. This is easily modified to be adaptive (that is, if there is a lot of action in a region, you refine the grid), but will still miss singularities. Splinification is bad, because it introduces smoothness where it is not warranted.

share|improve this answer
    
Thank you for your answer. But the problem is to find the polynom that approximate the given path but not find the path from the polynom. –  David Jun 5 '12 at 14:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.