How to draw closed spline 3D (closed curve 3d) through unordered list of points3D. How to arrange points3D?

How to draw closed spline 3D (closed curve 3d) through unordered list of
points3D. How to arrange points3D?

Hello I have a problem which I believe is very difficult to solve, I was
searching everywhere for solution but I didn't find anything.
I want to draw profiles from list of points.
My problem is:
I have a list of Points3D from text file, they arent in any order, just
like random points. Of course I added them to List. I draw those points in
3D space using small 3D Ellipses. So far so good.
Now I want to draw a 3D spline going through all the points from list. So
i created class Spline3D which is using cubic interpolation to determine
positions of points of curve between given points from text file. In my
spline I calculate say like 400 new points then I am drawing small 3D
Cylinders between each pair of points: point i and point i+1 have small
cylinder betwen them + the cylinders are rotated properly so everything is
looking like real spline (in theory).
The main problem is that points are unordered so if I am just doing that I
get spline like this:
img5.imageshack.us/img5/4659/2b61.jpg
the raw points draw in space look like this:
http://img194.imageshack.us/img194/9016/hv8e.jpg
img5.imageshack.us/img5/659/nsz1.jpg
So i figure out that I have two solutions
Put points in some sort of order, then add them to Spline3D and calculate
spline.
Calculate spline in some other way, which probably lead to order points in
some way, so basically it still lead me to 1.
So I tried some kinds of reordering methods.
1. a) Nearest neighbor of point
int firstIndex = (new
Random().Next(pointsCopy.Count));//0;//pointsCopy.Count / 2;//(new
Random().Next(pointsCopy.Count));
NPoint3D point = pointsCopy[firstIndex];
pointsCopy.Remove(point);
spline3D.addPoint(point.ToPoint3D());
NPoint3D closestPoint = new NPoint3D();
double distance;
double nDistance;
Point3D secondPoint = new Point3D();
bool isSecondPoint = true;
while (pointsCopy.Count != 0)
{
distance = double.MaxValue;
for (int i = 0; i < pointsCopy.Count; i++)
{
nDistance = point.distanceToPoint(pointsCopy[i]);
if (nDistance < distance)
{
distance = nDistance;
closestPoint = pointsCopy[i];
}
}
if (isSecondPoint)
{
isSecondPoint = false;
secondPoint = closestPoint.ToPoint3D();
}
spline3D.addPoint(closestPoint.ToPoint3D());
point = closestPoint;
pointsCopy.Remove(closestPoint);
}
spline3D.addPoint(points[firstIndex].ToPoint3D()); //first point is also
last point
This was my first idea, I thought that this will became ultimate solution
to my problem. I choose randomly one point from list of points and this
point became first point to spline. Then I find the closest point to this
previous point I add him to spline and remove from list and so on...
img18.imageshack.us/img18/3650/mik0.jpg
img706.imageshack.us/img706/3834/u97b.jpg
Sadly sometimes (especially near edges of my profile) point down is closer
then point near, so spline became there crooked.
2. b) TSP
distanceMatrix = new TSP.DistanceMatrix(pointsCopy,
NPoint3D.distanceBetweenTwoPoints);
int[] indexes = TSP.Algorithms.TSPgreedySearch(distanceMatrix);
for (int i = 0; i < indexes.Length; i++)
spline3D.addPoint(pointsCopy[indexes[i]].ToPoint3D());
spline3D.addPoint(pointsCopy[indexes[0]].ToPoint3D());
Basically I use traveling salesman problem algorithm to determine shortest
spline (shortest path) through all the points. Sadly this problem is
NP-Hard, so to get good performance I use some heuristics.
img198.imageshack.us/img198/714/xiqy.jpg
http://img839.imageshack.us/img839/9530/exnu.jpg
Spline looks better than in 1.a but still it isn't enough.
3. c) Some weird methods using two splines
Some of my friends told me that I should split profile in two parts
(upper-part and lower-part) and then calculate and draw two splines. Sadly
I dont know how to do that, I mean I don't know how to determine if point
should be in upper-part or lower-part. Please help me.
So how could I solve this problem? Any ideas?