javascript - 在由不同颜色的立方体组成的网格中，如何找到匹配的簇？

Question

定义集群

任何一组相同颜色的立方体，接触面平面，而不是它们的 Angular 。

一个簇会形成一个实心的几何形状。

帮助可视化问题

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

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

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 解决.维基百科页面对两个维度具有指导意义:

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)，或者更简单地说，如果它们在一个维度上相差一，那么您可以遍历所有六个邻居而不是四个邻居维度。