enter image description here

First of all, this is for image processing. The small circles above is on an image and are my list of points. The points are always in order from p1, p2, p3 to pn. And I am to create a curve that must pass through all the points and the curve must close itself just like in the figure above. Each point has a coordinate of x and y (and I got the list of these coordinates) and the curve will be drawn on the image.

I have been suggested to use Lagrange polynomial, Cubic Hermite spline and splines, but from what I understand, in mathematics, a function f(x) can only output one result. In this case, the points are on a 2D image and the curve will end up closing itself, which cannot be true for a function.

So I come up with a few ideas for this:

  1. Use polar coordinates. This may work valid if we have a list of points that will form a curve that will not "bend back" on itself.

  2. Apply the function f(x) n times, using a few points at a time.

So I want to ask mathematicians here. Normally, in the case like this, what do you do?


You should use a function that maps to $\mathbb{R^2}$ rather than $\mathbb{R}$. To formulate your question in a mathematical sense you are given a list of points $(x_1 \leq x_2 \leq \ldots \leq x_n)$ and $(y_1,y_2,\ldots,y_n)$ and you call $p_i = (x_i, y_i)$ for $i=1,\ldots,n$. Now you look for a continuous function

$\gamma: [0,1] \rightarrow \mathbb{R}^2 \supset [x_1,x_n] \times [y_1,y_n]$ such that $\gamma(0)=\gamma(1)$ and $\{p_1,\ldots,p_n\} \subset \gamma([0,1])$. Where image is defined as in wikipedia. A naive approach is to split the interval up into $n$ parts and connect each $p_0$ with the closest point $p_*$ to it by a line in $[0,\frac{1}{n})$ then $p_*$ to the closest point to it in $[\frac{1}{n},\frac{2}{n})$ and so on where finally you connect $p_{last}$ with $p_0$ in the interval $[\frac{n-1}{n},1]$. You could also take $3$ or more points on every step using similar methods to the ones you already mentioned, of course it will be more difficult that way.

  • $\begingroup$ I get your point, but I'm not sure how can I achieve the "mapping to 2D part". You mean, there is a method to manipulate function in such way? $\endgroup$ – Karl Jul 5 '11 at 15:23
  • $\begingroup$ What do you mean? The function value will be a point in $\mathbb{R}^2$ so you can just connect the points $\gamma(x)$ and $\gamma(x+\epsilon)$ for $\epsilon$ small enough and get your graph. $\endgroup$ – Listing Jul 5 '11 at 17:06
  • $\begingroup$ Yes, but I don't know what is such function. I only know that it is mapped to R^2. $\endgroup$ – Karl Jul 6 '11 at 3:06
  • $\begingroup$ The definition is easy. Basically if the points are not on a vertical line you can map $x \mapsto (x,\alpha x+\beta)$ and otherwise $x \mapsto (\alpha' x+\beta',\alpha x+\beta)$ for example. $\endgroup$ – Listing Jul 6 '11 at 5:40
  • 1
    $\begingroup$ Hmm thanks for accept I think we could help you more if you directly say what you need this for. Then you maybe wouldn't even need such a function, which is probably useful in theory but not practically. $\endgroup$ – Listing Jul 6 '11 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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