0

我正在尝试为以下 3D 立方体选择问题找到一种有效的算法：

想象一个 2D 点数组（让它大小为 x 大小的正方形）并将其称为边。

为了便于计算，让我们将 max 声明为 size-1 创建一个有六个边的立方体，在左下角保持 0,0，在右上角保持 max,max。使用 z 跟踪单个立方体所在的边，y 为上，x 为右

public class Point3D {
    public int x,y,z;

    public Point3D(){}
    public Point3D(int X, int Y, int Z) {
        x = X;
        y = Y;
        z = Z;
    }
}

Point3D[,,] CreateCube(int size)
{
    Point3D[,,] Cube = new Point3D[6, size, size];
    for(int z=0;z<6;z++)
    {           
        for(int y=0;y<size;y++)
        {
            for(int x=0;x<size;x++)
            {
                Cube[z,y,x] = new Point3D(x,y,z);
            }
        }
    }
    return Cube;
}

现在要选择一个随机单点，我们可以使用三个随机数，这样：

Point3D point = new Point(
Random(0,size), // 0 and max
Random(0,size), // 0 and max
Random(0,6));   // 0 and 5

要选择一个加号，我们可以检测给定方向是否适合当前边。否则，我们会发现立方体位于接触中心点的一侧。

使用 4 个函数，例如：

private T GetUpFrom<T>(T[,,] dataSet, Point3D point) where T : class {
    if(point.y < max)
        return dataSet[point.z, point.y + 1, point.x];
    else {
        switch(point.z) {
            case 0: return dataSet[1, point.x, max];      // x+
            case 1: return dataSet[5, max, max - point.x];// y+
            case 2: return dataSet[1, 0, point.x];        // z+
            case 3: return dataSet[1, max - point.x, 0];  // x-
            case 4: return dataSet[2, max, point.x];      // y-
            case 5: return dataSet[1, max, max - point.x];// z-
        }
    }
    return null;
}

现在我想找到一种在随机点选择任意形状（如预定义的随机 blob）的方法。但会满足于将其调整为方形或锯齿形圆形。

实际的表面积会在拐角处弯曲并折叠到自身上，这很好，不需要补偿（想象一下在立方体的拐角上贴一个贴纸，如果拐角与贴纸的中心匹配，则需要四分之一的贴纸将其移除以使其粘在角落上并折叠）。这又是想要的效果。

不允许重复选择，因此需要以某种方式过滤将被选择两次的多维数据集（或以不发生重复的方式计算）。这可能很简单，例如使用 HashSet 或 List 并使用辅助函数来检查条目是否唯一（这很好，因为选择总是远低于最大 1000 个立方体）。

包含立方体边的类中此函数的委托如下所示： delegate T[] SelectShape(Point3D point, int size);

目前我正在考虑检查多维数据集的每一侧，以查看选择的哪一部分位于该侧。

计算选择的哪一部分位于所选 Point3D 的同一侧，因为我们不需要平移位置，只需平移边界即可。接下来是 5 次翻译，然后检查其他 5 面以查看所选区域的一部分是否在该面。

我在解决这样的问题方面变得生疏了，所以想知道是否有人有更好的解决方案来解决这个问题。

@arghbleargh 要求进一步解释：

我们将使用一个 6 面的立方体，大小为 16。每面是 16x16 点。存储为一个三维数组，我将 z 用于边、y、x，这样数组将使用：new Point3D[z,y,x] 启动，它对于锯齿状数组的工作方式几乎相同，默认情况下可序列化（所以那也很好）[z][y][x] 但需要单独初始化每个子数组。

让我们选择一个大小为 5x5 的正方形，以选定点为中心。要找到这样一个 5x5 的正方形减法并将 2 添加到相关轴：x-2 到 x+2 和 y-2 到 y+2。

随机选择一个边，我们选择的点是z = 0（立方体的x+边），y = 6，x = 6。

6-2 和 6+2 都很好地在边的 16 x 16 阵列的范围内，并且易于选择。

然而，将选择点移动到 x=0 和 y=6 将证明更具挑战性。因为 x - 2 需要查看我们选择的一侧的左侧。幸运的是，我们选择了边 0 或 x+，因为只要我们不在立方体的顶部或底部并且不进入立方体的顶部或底部，所有轴都是 x+ = 右，y+ = 上。因此，要获得左侧的坐标只需要减去 max (size - 1) - x。请记住 size = 16, max = 15, x = 0-2 = -2, max - x = 13。因此，这一边的小节将是 x = 13 到 15，y = 4 到 8。将其添加到我们的部分可以在原始一侧选择将给出整个选择。

将选择移至 0,6 会更复杂，因为现在我们无法隐藏在知道所有轴对齐的安全性之后。可能需要进行一些轮换。只有 4 种可能的翻译，所以它仍然是可管理的。

转移到 0,0 是问题真正开始出现的地方。现在左右两边都需要绕到另一边。此外，即使细分的部分也会有一个区域落在外面。唯一能治愈这个伤口的是我们不关心选择的重叠部分。因此，我们可以在可能的情况下跳过它们，也可以稍后从结果中过滤它们。

现在我们从“法线轴”一侧移动到底部，我们需要旋转并匹配正确的坐标，以便点正确地环绕边缘。

由于每边的轴都折叠在一个立方体中，因此某些轴可能需要翻转或旋转才能选择正确的点。

如果有更好的解决方案可以选择区域内立方体上的所有点，问题仍然存在。也许我可以给每一边一个平移矩阵并在世界空间中测试坐标？

4

1 回答 1

0

找到了一个很好的解决方案，只需很少的努力即可实施。

为大小为 n + 2 的空心立方体创建一个存储，其中 n 是数据中包含的立方体的大小。这满足 : 边是接触的，但不重叠或共享某些点。

这将通过创建使用笛卡尔坐标的查找数组来简化计算和转换。使用单个平移函数获取选定点的坐标，获取“世界位置”。

使用该函数，我们可以将每个点存储到笛卡尔查找数组中。

选择一个点时，我们可以再次使用相同的功能（或使用存储的数据）并减去（获取AA或min位置）并添加（获取BB或Max位置）。

然后我们可以查找 AA.xyz 和 BB.xyz 坐标之间的每个条目。应跳过每个空条目。

如果需要，通过使用如果 z 不是 0 或 size-1 则返回 null 的数组类型进行优化，因此不需要在中间存储“空心立方体”的 null 引用。

现在立方体可以选择 3D 立方体，其他形状很简单，给定一个 3D 点，定义一个 3D 形状并使用查找数组测试形状中的每个部分，如果不为空，则将其添加到选择中。每个点只选择一次，因为我们只检查每个位置一次。

由于对多维数据集内部和外部的空进行测试，计算开销很小，但数组访问速度非常快，因此该解决方案适用于我当前的项目。

于 2013-09-02T16:11:44.307 回答