在由不同颜色的立方体制成的网格中,如何找到匹配的簇？

Question

定义集群

任何一组相同颜色的立方体,触摸面平面,而不是它们的角落.

簇将形成实心几何形状.

帮助可视化问题

让我们假设这些乐高积木中的每一个都是1x1单位大的.

在一个简化的代码示例中 - 让我们看一下2x2x2由1x1x1立方体组成的网格:

var mesh = [ 

  // First layer   ( x, y, z )
  new THREE.Vector3( 0, 0, 0 ),
  new THREE.Vector3( 0, 0, 1 ),
  new THREE.Vector3( 1, 0, 0 ),
  new THREE.Vector3( 1, 0, 1 )

  //Second layer   ( x, y, z )
  new THREE.Vector3( 0, 1, 0 ),
  new THREE.Vector3( 0, 1, 1 ),
  new THREE.Vector3( 1, 1, 0 ),
  new THREE.Vector3( 1, 1, 1 )
];

网格中的每个立方体都有一个颜色:

//Indexes of mesh array sorted by color
var colors = {
  red: [0, 1, 4, 6],
  green: [2, 3, 5, 7]
}

Answer 1

这可以通过洪水填充来解决。维基百科页面对二维具有指导意义：

Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If the color of node is not equal to target-color, return.
 3. Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.

您可以将其扩展到三维，方法是观察两个单元格相邻（如果它们的距离为 1），或者更简单地说，如果它们在一维上相差 1，那么您可以迭代所有六个相邻单元格，而不是二维的四个相邻单元格。