Как нарисовать замкнутый сплайн 3D (закрытая кривая 3d) через неупорядоченный список точек3D. Как организовать точки3D?

Question

Здравствуйте, у меня есть проблема, которую, я считаю, очень трудно решить, я искал везде решение, но ничего не нашел.

Я хочу нарисовать профили из списка пунктов.

Моя проблема:

1. У меня есть список Points3D из текстового файла, они Арент в любом порядке, так же, как случайные точки. Конечно, я добавил их в список. Я рисую эти точки в 3D-пространстве, используя небольшие 3D-эллипсы. Все идет нормально.
2. Теперь я хочу нарисовать 3D-сплайн, проходящий через все точки из списка. Поэтому я создал класс Spline3D, который использует кубическую интерполяцию для определения положений точек кривой между заданными точками из текстового файла. В моем сплайне я вычисляю так, как 400 новых точек, тогда я рисую маленькие 3D-цилиндры между каждой парой точек: точка i и точка i + 1 имеют маленький цилиндр между ними + цилиндры вращаются правильно, поэтому все выглядит как настоящий сплайн (в теория).

Основная проблема заключается в том, что точки неупорядоченные, так что если я просто делаю, что я получаю сплайн, как это:

http://img5.imageshack.us/img5/4659/2b61.jpg

исходные точки начертить в пространстве выглядит следующим образом:

http://img194.imageshack.us/img194/9016/hv8e.jpg

http://img5.imageshack.us/img5/659/nsz1.jpg

Так я выяснить, что у меня есть два решения

1. ставить точки в каком-то порядке, а затем добавить их в Spline3D и рассчитать сплайн.

2. Вычислить сплайн каким-либо другим способом, который, вероятно, приведет к заказу точек в некотором роде, так что в основном все еще приводят меня к 1.

Так что я попробовал некоторые виды методов переупорядочения.

1. а) Ближайший сосед точки

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 

Это была моя первая идея, я думал, что это будет стало окончательное решение моей проблемы. Я выбираю случайным образом одну точку из списка точек, и эта точка стала первой точкой сплайна. Тогда я найти ближайшую точку к этой предыдущей точке я добавить его к сплайну и удалить из списка и так далее ...

http://img18.imageshack.us/img18/3650/mik0.jpg

http://img706.imageshack.us/img706/3834/u97b.jpg

К сожалению, иногда (особенно вблизи край моего профиля) точка вниз ближе, чем точка рядом, поэтому сплайн стал там кривым.

2.б) 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()); 

В основном я использую путешествие алгоритм проблемы коммивояжера, чтобы определить кратчайший сплайн (кратчайший путь) через все точки. К сожалению, эта проблема NP-Hard, поэтому для достижения хорошей производительности я использую некоторые эвристики.

http://img198.imageshack.us/img198/714/xiqy.jpg

http://img839.imageshack.us/img839/9530/exnu.jpg

сплайн выглядит лучше, чем в 1.а, но все-таки не хватает.

3. с) некоторые странные методы, использующие две шлицы

Некоторые из моих друзей сказал мне, что я должен разделить профиль на две части (верхний и нижней-части), а затем рассчитать и нарисовать две шлицы , К сожалению, я не знаю, как это сделать, я имею в виду, что я не знаю, как определить, должно ли точка быть в верхней части или нижней части. Пожалуйста, помогите мне.

Так как я могу решить эту проблему? Есть идеи?

Answer 1

Похоже, что вы ищете набор данных Concave Hull.

К сожалению, я не знаю никаких предварительно запрограммированных алгоритмов, но ссылка ссылается на документ, с которого начинал другой разработчик, а также с некоторым примером кода, поэтому, возможно, это поможет вам в правильном направлении.