5
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Pietro Majer
    Jun 5, 2012 at 12:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – David
    Jun 5, 2012 at 14:18
  • 3
    $\begingroup$ 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? $\endgroup$
    – Stanislav
    Jun 5, 2012 at 17:52
  • $\begingroup$ 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. $\endgroup$
    – David
    Jun 6, 2012 at 12:08
  • 6
    $\begingroup$ @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 $\endgroup$
    – Misha
    Jun 8, 2012 at 17:22

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – David
    Jun 5, 2012 at 14:26
2
$\begingroup$

Your reference to eigenvalues suggests that you are minimizing $\sum_i P(x_i, y_i)^2$ subject to a constraint like $\sum_{a,b} P_{ab}^2=1$, where $P(x,y) = \sum_{a,b} P_{ab} x^a y^b$. Why not instead minimize $\sum_i P(x_i, y_i)^2$ subject to a linear constraint like $P_{00}=1$?

This is a standard approach when fitting a conic through a cloud of points (see, for example, Paul L. Rosin, A note on the least squares fitting of ellipses, Pattern Recognition Letters, Volume 14, Issue 10, October 1993, Pages 799–808) and I don't see why it wouldn't be a good idea for higher degree.

This puts your problem in the form "minimize $\vec{x}^T A \vec{x}$, subject to $\vec{b} \cdot \vec{x}=1$", to which the solution is $\vec{x} = \frac{A^{-1} \vec{b}}{\vec{b}^T A^{-1} \vec{b}}$; no eigenvalues needed.

I suspect Misha's comment will be more useful than this answer, though.

I also second everyone who said that $36 \times 36$ is not large. It looks like this thread might be able to help you find a better linear algebra library.

Improve this answer
$\endgroup$
-1
$\begingroup$

New method for solving underdetermined systems of nonlinear equations. The first link describes (in Russian) calculations of linkages. The second gives an example from another area on mapleprimes (with the text, however, in Maple (answer from myself, "one man")).

http://www.exponenta.ru/educat/systemat/selitskiy-ivanov/index.asp

http://www.mapleprimes.com/questions/205606-Find-Root-Method

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Could someone who knows Russian comment on the first link? $\endgroup$
    – Todd Trimble ♦
    Dec 4, 2015 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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