如何对一个二十面体的面进行索引？

Question

我正在编写一个模拟程序，对映在球面表面上的网格进行操作。这个网格本身是一个细分的二十面体(不事先知道细分级别)。

对于一个正方形网格，很容易找到相邻的单元格，因为它们在x或y轴上会加或减1。但是对于这些三角形来说，情况完全不同，我的思维很难想象一种索引单元格的方法。

是否有任何坐标系统可以用于寻址二十面体的面，至少使得轻松获得与二十面体中任意单元格相邻的3个单元格？

- Anne Quinn

---

这个网格非常小，因此为每个三角形简单地存储相邻三角形的查找表是否有问题？ - cfh

@cfh - 没有细分时它很小，但是每个三角形在每个细分级别上被分成四个三角形，因此面数以20*4^n的速率增加。 - Anne Quinn

好的，我现在明白了。所以似乎底层的二十面体实际上与问题无关，你只是想要一个快速访问三角形邻居的数据结构？ - cfh

@cfh - 我想是的！底层形状似乎很重要，但最终我可能是错的。 - Anne Quinn

你的主要考虑因素是什么？低内存使用、速度、简单性？ - samgak

Answer 1

基本上，您希望将几何图形预处理成一种特定的数据结构，以便快速查找三角形的邻居。

如果这是您唯一的要求，则很容易“自己动手”。例如，对于每个三角形，您将存储其三条边，可以是指向边缘结构的指针或作为边表中的索引。然后，对于每条边，您将存储其两个相邻的三角形（再次作为指针或三角形索引）。

此设置允许您轻松地从一个三角形到达其各个边缘，并从边缘结构中找到另一个相邻的三角形。

有更高级的用于三角剖分表面的数据结构，允许执行更有趣的操作，例如双连通边缘列表或有翼边缘数据结构。

如果您想使用现成的库，则GTS库可以满足您的需求并提供更多功能。

- cfh

Answer 2

这是一个有趣的问题。确切的答案取决于如何细分二十面体的面，您没有说明。但我将提供攻击该问题的框架。

首先，让我说一下在正方形网格的情况下，我认为什么使这个问题变得容易：存在反映网格对称性的数学群结构。准确地说，有一对简单的变换（向上移动；向右移动），它们与它们的逆一起生成将一个网格单元转换为另一个网格单元的每个变换。此外，向上移动和向右移动操作是可交换的：应用一系列操作的顺序不会改变结果。向上和向右的操作生成了单元格网格上的可交换变换群。该群同构于ZxZ，因此好的坐标由整数对(m,n)给出。

在二十面体上缺乏这样的结构是你提出问题的难点之一。在二十面体上有一个群结构，其中包含两个生成元，有时被称为“a”和“b”，其中“a”是将给定边反转并映射到其自身的180度旋转，而“b”是给定面的120度旋转。问题在于该群不是交换群，因此ab！= ba。这严重复杂化了使用群生成元进行计算的过程。另一个问题是该方法会使每个面三倍覆盖（每个旋转一次）。在二十面体的旋转对称群A5中有60个元素，但在二十面体上只有20个面。

威廉·哈密顿在伊科西亚微积分中发现了一种非常有趣的解决这些问题的方法，并在伊科西亚游戏中推广。值得注意的是，在群和生成元的概念被发明（或至少被充分理解）之前，哈密顿就给出了二十面体旋转群的生成元（他用希腊字母iota和kappa代替了a和b）。然后，哈密顿使用他的伊科西亚微积分在十二面体的顶点图（或等价地，正二十面体的面图，因为十二面体和正二十面体是对偶的）上找到了一个哈密顿回路。请在此处查看图形。

那个图表可以用来按循环顺序从0到19索引二十面体的面。将十二面体的顶点图中的点从0到19沿着哈密顿回路编号，这对应于沿着哈密顿回路也编号相邻的二十面体面。给定一个面m，它的两个相邻面分别是m-1模20和m+1模20；第三个相邻面由graph中的虚线给出。也许有一个关于第三个相邻面的索引的好的公式或者模式，但我一时想不到；把它存储在表格中也很容易。

如果按照某种方式将面细分，就可以将哈密顿回路延伸到面内。通过在每个面的中心引入一个新点，将每个面细分为三个面。然后，您可以在面内的三角形中找到一条哈密顿路径（只需沿着它们按顺时针或逆时针方向走，具体取决于入口边和出口边之间的关系）。如果以这种方式进一步细分面，您将得到一条哈密顿路径，该路径通过空间填充曲线的方式穿过进一步细分的三角形。该面细分的问题在于三角形边长的最大值不会减小。

对于更常见的三角形细分方式（通过细分边缘而不是在面的中心引入新点），我找不到一种将哈密顿回路扩展到新图形上的方法。因此，您可能更容易使用其他提议用于索引三角形面的方法之一，以查找面内相邻的三角形，并将其与我提出的索引icosahedron面的方法相结合，以查找另一个面内的相邻三角形。

更新

我一直在考虑对面进行索引。使用三角形平铺维基百科页面上的图像，一个面将由无限平铺的大三角形部分组成。

一个仿射变换（不影响索引）将该图像转换为

然而，后一幅图像包含了方块，因此三角形可以通过方块底部角落的x坐标、方块底部角落的y坐标以及单个位（0或1）来轻松索引。黄色三角形（m，n，0）旁边的三个三角形是（m-1，n，1）、（m，n-1，1）和（m，n，1），绿色三角形（m，n，1）旁边的三个三角形是（m，n，0）、（m+1，n，0）和（m，n+1，0）；所有这些操作都是快速的递减、递增或位翻转。将三角形数量加倍是通过在（m，n）处将正方形分成四个具有坐标（2m+0，2n+0）、（2m+1，2n+0）、（2m+0，2n+1）和（2m+1，2n+1）的小正方形来完成的，因此（m，n，0）处的黄色三角形被分成了（2m，2n，0）、（2m+1，2n，0）、（2m，2n+1，0）处的黄色三角形和（2m，2n，1）处的绿色三角形，（m，n，1）处的绿色三角形被分成了（2m+1，2n，1）、（2m，2n+1，1）、（2m+1，2n+1，1）处的绿色三角形和（2m+1，2n+1，0）处的黄色三角形；所有这些操作都是快速的移位、无进位加法和位翻转。最后，我们可以通过快速运算来确定三角形（x，y，c）是否越界：如果y坐标为负，则在底部越界；如果x坐标为负，则在左侧越界；如果x+y+c>三角形大小，则在对角线上越界。没有乘法。

“底部”指的是三维图形的哪一面？哈密顿回路也给出了答案：任何一个面的“底部”都是有向哈密顿回路进入的那一侧。这为每个面提供了明确的方向。

因此，现在每个子三角形都有一个很好的坐标：(f，x，y，c)，其中f是沿着哈密顿回路计算的二十面体的面，x是包含三角形的平行四边形的x坐标，y是平行四边形的y坐标，c是颜色（0（黄色）表示左下角，1（绿色）表示右上角）。邻居可以通过三个快速操作加上简单的越界测试来计算，只需进行一些移位和不带进位的加法即可完成细分。如果邻居测试越界，则只需将f mod 20减1，f mod 20加1或查找侧面的“点线面”。您还可以简单地迭代遍历每个三角形，首先遍历面，然后在每个面内遍历x+y+c =常数的三角形。

- Edward Doolittle

Answer 3

对于二十面体的每个面，您可以将三角形映射到一个网格上，每个网格正方形分为两部分，例如（为了方便格式化的十六进制编号）：

 A
 +
 |\
 |0\
 +--+
 |\2|\
 |1\|3\
 +--+--+
 |\5|\7|\
 |4\|6\|8\
 +--+--+--+
 |\A|\C|\E|\
 |9\|B\|D\|F\
 +--+--+--+--+
B             C

对于一个被分成n个部分的侧面，每个侧面中有4的n次方个三角形。因此，您可以为正二十面体的每个侧面创建一个这样大小的数组，以存储模拟中每个三角形的数据。

三角形的引用可以存储为(side, row, column)。

行和列索引从0开始。列索引基于行中的三角形数量（即每个网格方块中的2个三角形）。

如果您知道侧面、行和列，可以像这样计算侧面数组的索引：

index = (row * row) + column

所以你可以将数据存储在二维数组中，并像这样访问它：

value = data[side][(row * row) + column]

对于一列为偶数的三角形，相邻的三角形如下：

(side, row, column - 1)
(side, row, column + 1)
(side, row + 1, column + 1)

对于列数为奇数的三角形，相邻的三角形：

(side, row, column - 1)
(side, row, column + 1)
(side, row - 1, column - 1)

这样可以在不显式存储相邻信息的情况下轻松引用细分三角网格中的三角形。

问题在于当将其组织成一个二十面体时。计算相邻三角形的引用后，需要验证新的引用是否在边界内：

int rows = 1 << subdivision_count;
if(row >= rows)
{
    // compute (side, row, column) in adjacent side of icosahedron to B-C edge
}
else if(column < 0)
{
    // compute (side, row, column) in adjacent side of icosahedron to A-B edge
}
else if(column >= ((row * 2) + 1))
{
    // compute (side, row, column) in adjacent side of icosahedron to A-C edge
}

您需要为每个边存储邻接信息以及其类型（AB、BC、AC）。

您需要找出9种不同的可能映射，每种映射对应一种边缘类型的组合。例如，如果相邻的三角形横跨AC边缘，并且该边缘与相邻侧的AB边缘匹配，则

side = adjacent side (from table)
row = row
column = column - ((row * 2) + 1)

这种方法在某些方面更加复杂，但在其他方面更加简单。所有这些的优点包括：

• 不需要为每个三角形存储邻接信息，只需为二十面体边存储
• 如果您为每个边存储了A、B、C的3D位置，则可以计算出给定（边、行、列）参考的三角形的3D三角形坐标，因此也无需为每个三角形存储它们

- samgak

---

获取相邻的边A-B，应该是“列 < 0”吗？ - Anne Quinn

Answer 4

将每个三角形分配一个元组{s,x,y}是很简单的，其中s表示边，x,y表示在该边内的位置：

   /\ /Y
  /__\
 /\  /\
/__\/__\ ->X

这将有三角形 {0,0}, {1,1} (中间), {2,0} 和 {0,2}。在平面内，(相同的s)，x和y坐标会告诉你哪些三角形相邻。你需要一张包含30条边的表格，表示每条边两侧的三角形以及它们的X、Y坐标如何排序。 (也许你可以想出一个更智能的编号方法，但我没能做到。)

- MSalters