折叠三维立方体上的点

Question

我试图为以下三维立方体选择问题找到一种有效的算法：

想象一个二维的点数组(让它变成x大小的平方)，并称它为边。

为了便于计算，让我们宣布最大值为大小-1创建一个六边立方体，保持0,0在左下角和最大值，最大值在右上。使用z跟踪一侧，一个立方体被定位，y为up，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;
}

现在，我想找一种方法来选择任意形状(像预定义的随机气泡)在一个随机点。但会把它调整成正方形或锯齿状的圆圈。

实际的表面面积会被弯曲并折叠在角上，这是很好的，不需要补偿(想象一下在立方体的角上贴一个贴纸，如果这个角与贴纸的中心相匹配，那么它就需要被移除，这样它才能粘在角上并折叠起来)。同样，这也是期望的效果。

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

这个函数在包含立方体两侧的类中的委托如下:委托T[] SelectShape(Point3D点，int大小)；

目前，我正在考虑检查立方体的每一边，看看选择的哪一部分位于这一边。

计算选择的哪一部分位于所选Point3D的同一侧，将是非常简单的，因为我们不需要转换位置，只需要转换边界。接下来是5个翻译，然后检查其他5个边，看看所选区域的一部分是否在这一侧。

我在解决这样的问题上已经生疏了，所以我想知道是否有人能找到更好的解决这个问题的方法。

@arghbleargh要求进一步解释：

我们将使用一个6面的立方体，大小为16，每边16点。作为一个三维数组存储，我使用z作为side、y、x来启动数组: new Point3Dz、y、x，对于交错数组来说，它的工作方式几乎相同，这些数组在默认情况下是可序列化的(因此这也不错) zx，但是需要对每个子数组进行单独的初始化。

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

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

6-2和6+2均在16x16阵列的范围内，易于选择。

然而，将选择点转移到x=0和y=6将被证明更具挑战性。因为x-2需要向左面看一看我们选择的一侧。幸运的是，我们选择了侧0或x+，因为只要我们不是在顶部或底部，并且没有到立方体的顶部或底部，所有的轴都是x+ = right，y+ = up。因此，要得到左边的坐标，只需要减去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是问题真正开始出现的地方。就像现在一样，左右两边都需要绕到另一边。更重要的是，即使是细分的部分也会有一个区域落在外面。这个伤口上唯一的药膏是，我们不关心选择的重叠部分。因此，我们可以在可能的情况下跳过它们，或者稍后从结果中筛选它们。

现在，我们从“法线轴”的一侧移动到底部，我们需要旋转和匹配正确的坐标，这样点就可以正确地围绕着边缘。

由于每一侧的轴折叠在一个立方体，一些轴可能需要翻转或旋转，以选择正确的点。

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

Answer 1

找到了一个很好的解决方案，不需要多少精力来实现。

为大小为n+ 2的空心立方体创建存储，其中n是数据中包含的多维数据集的大小。这就满足了:双方是接触的，但不重叠或分享某些观点。

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

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

在选择点时，我们可以再次使用相同的函数(或使用存储的数据)和减法(以获得AA或min位置)和加(获得BB或最大值位置)。

然后，我们只需查找AA.xyz和BB.xyz坐标之间的每个条目。应该跳过每个空项。

如果需要优化，则使用一种类型的数组，如果z不是0或大小-1，则返回空值，因此不需要在中间存储“空心立方体”的空引用。

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

由于对多维数据集内外的空值进行测试，计算开销很小，但是数组访问速度太快，因此对于我当前的项目来说，这个解决方案是很好的。