c# - 如何通过 points3D 的无序列表绘制闭合样条 3D(闭合曲线 3d)。如何安排points3D？

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。 a) 点的最近邻

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。 b) 运输服务商

    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

Spline 看起来比 1.a 中的更好，但仍然不够。

<强>3。 c) 使用两个样条的一些奇怪的方法

我的一些 friend 告诉我，我应该将剖面分成两部分(上部和下部)，然后计算并绘制两条样条线。可悲的是我不知道该怎么做，我的意思是我不知道如何确定点应该在上半部分还是下半部分。请帮助我。

那么我该如何解决这个问题呢？有什么想法吗？

Answer 1

听起来您正在寻找 Concave Hull数据集。

不幸的是，我不知道任何预先设定的算法，但该链接引用了另一位开发人员开始的一篇论文，以及一些示例代码，所以也许这会帮助您朝着正确的方向前进。