2

你好我有一个我认为很难解决的问题，我到处寻找解决方案，但我没有找到任何东西。

我想从点列表中绘制轮廓。

我的问题是：

  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) 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.a 中的要好，但仍然不够。

3. c) 一些使用两条样条的奇怪方法

我的一些朋友告诉我，我应该将轮廓分成两部分（上部分和下部分），然后计算并绘制两条样条线。可悲的是我不知道该怎么做，我的意思是我不知道如何确定点应该在上部还是下部。请帮我。

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

4

1 回答 1

1

听起来您正在寻找数据集的凹壳。

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

于 2013-08-22T17:53:41.917 回答