Looking for a "closing curves connecting with respect to points" algorithm

4
votes

I am looking for an algorithm that can connect points together with a continuous curve line. Imagine drawing from point a to b to c until the last point, and when you draw from point to point, the line must be a curve and is continuous with respect to the previous point and next point, as if the given points are just samples of a closed loop. Please see figure below for illustration.

Are there such algorithm for something like this?

close_encircle

*The circles in the figure are my list of points.

2
algorithmimage-processing
You may find splines useful: en.wikipedia.org/wiki/Spline_(mathematics) – usul
Are the points ordered or unordered? – Mikola
@Mikola: The points are always in order. – Karl
@bo1024: you may wish to put your comment into as one of the answers. Let me give you some points. – Karl
It seems that this post gets downvoted for suggestive answers. I'll post here, if Karl likes it, i'll post as an answer thx. If your shape is almost guaranteed to be a convex shape, basically you are looking for top 2 'shortest' edges among all the vertexes. So say, the topmost vertex has an edge to all other vertices, you can establish the first two lines(or edges) by looking up the 'shortest' 2 lines(or edges). Then for your next node, you do this again until satisfied. This method will converge (an example criterion would be total distance of the edges). – Gary Tsui

2 Answers

4
votes

Given that your points are ordered, spline interpolation is definitely the best way to go here. (As indicated by by bo1024's comment) I highly recommend the following notes:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/

And specifically the section here would be most relevant to getting a closed loop like you asked for:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-curve-closed.html

EDIT: If the curve has to pass through the points, then the unique degree n solution is the Lagrange interpolating polynomial. You can just make one polynomial for each component of your points vectors using the formula on the wiki page:

http://en.wikipedia.org/wiki/Lagrange_polynomial

Unfortunately Lagrange interpolation can be pretty noisy if you have too many points. As a result, I would still recommend using some fixed degree spline interpolation. Instead of B-splines, another option are Hermite polynomials:

http://en.wikipedia.org/wiki/Cubic_Hermite_spline

These will guarantee that the curve passes through the points. To get a closed curve, you need to repeat the the first d points of your curve when solving for the coefficients, where d is the degree of the Hermite spline you are using to approximate your points.

-2
votes

The problem is very similar to the travelling salesman problem, you may be able to extend some of the algorithms used to solve it to suit your case.

For instance, evolutionary algorithms are easy to adapt and you will find lot of references about using them to solve the TSP.