Within a lattice composed of variously hued cubes, how can one locate the corresponding clusters?

Question

Within a lattice composed of variously hued cubes, how can one locate the corresponding clusters?

Explaining Clusters

A cluster is a group of cubes of the same color that are touching face planes, not their corners, forming a solid geometric shape.

To Aid in Visualization

Imagine each Lego piece to be 1x1 units in size.

https://i.sstatic.net/z9qFm.png

For instance, let's consider a 2x2x2 mesh composed of 1x1x1 cubes:

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 )
];

https://i.sstatic.net/7CCrT.jpg

Each cube within the mesh is assigned a color:

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

javascript algorithm sorting vector three.js

Answer 1

Answer №1

The solution to this problem lies in utilizing a technique called flood fill. The Wikipedia article provides comprehensive guidance for handling situations in two dimensions:

Flood-fill (node, target-color, replacement-color):
 1. If the target-color matches the replacement-color, stop.
 2. If the color of the current node does not match the target-color, do nothing.
 3. Change the color of the current node to the replacement-color.
 4. Apply Flood-fill (one step south of the node, target-color, replacement-color).
    Apply Flood-fill (one step north of the node, target-color, replacement-color).
    Apply Flood-fill (one step west of the node, target-color, replacement-color).
    Apply Flood-fill (one step east of the node, target-color, replacement-color).
 5. Finish.

To adapt this method to three dimensions, we can establish that two cells are considered adjacent if their separation is only 1. In simpler terms, if they differ by one dimension, you can navigate through all six neighboring cells rather than just four as in two-dimensional cases.

Answer 2

The solution to this problem lies in utilizing a technique called flood fill. The Wikipedia article provides comprehensive guidance for handling situations in two dimensions:

Flood-fill (node, target-color, replacement-color):
 1. If the target-color matches the replacement-color, stop.
 2. If the color of the current node does not match the target-color, do nothing.
 3. Change the color of the current node to the replacement-color.
 4. Apply Flood-fill (one step south of the node, target-color, replacement-color).
    Apply Flood-fill (one step north of the node, target-color, replacement-color).
    Apply Flood-fill (one step west of the node, target-color, replacement-color).
    Apply Flood-fill (one step east of the node, target-color, replacement-color).
 5. Finish.

To adapt this method to three dimensions, we can establish that two cells are considered adjacent if their separation is only 1. In simpler terms, if they differ by one dimension, you can navigate through all six neighboring cells rather than just four as in two-dimensional cases.

Answer 3

Answer №2

If you're looking for a practical demonstration on how to apply flood-fill to your mesh, check out my custom npm package n-dimensional-flood-fill:

// For a smoother approach, organize your mesh as nested arrays:
var mesh = [
  [
    // 0,0,0  0,0,1
    ["red", "red"],

    // 0,1,0  0,1,1
    ["red", "green"],
  ],
  [
    // 1,0,0  1,0,1
    ["green", "green"],

    // 1,1,0  1,1,1
    ["red", "green"]
  ]
];

var redFill = floodFill({
  getter: function (x, y, z) { return mesh[x][y][z] },
  seed: [0, 0, 0]
});

var greenFill = floodFill({
  getter: function (x, y, z) { return mesh[x][y][z] },
  seed: [1, 1, 1]
});

console.log("redFill: " + JSON.stringify(redFill.flooded));
// redFill: [[0,0,0],[0,1,0],[1,1,0],[0,0,1]]

console.log("greenFill: " + JSON.stringify(greenFill.flooded));
// greenFill: [[1,1,1],[1,0,1],[1,0,0],[0,1,1]]

If needed, you can customize the getter function to suit your mesh structure.

From the output, you can observe that floodFill should be executed separately for each region. To identify all regions within the mesh, you may run floodFill from various starting points, ensuring not to repeat coordinates already included in previous regions. While this method is effective, there are more advanced techniques for detecting all regions in a single iteration.

Answer 4

If you're looking for a practical demonstration on how to apply flood-fill to your mesh, check out my custom npm package n-dimensional-flood-fill:

// For a smoother approach, organize your mesh as nested arrays:
var mesh = [
  [
    // 0,0,0  0,0,1
    ["red", "red"],

    // 0,1,0  0,1,1
    ["red", "green"],
  ],
  [
    // 1,0,0  1,0,1
    ["green", "green"],

    // 1,1,0  1,1,1
    ["red", "green"]
  ]
];

var redFill = floodFill({
  getter: function (x, y, z) { return mesh[x][y][z] },
  seed: [0, 0, 0]
});

var greenFill = floodFill({
  getter: function (x, y, z) { return mesh[x][y][z] },
  seed: [1, 1, 1]
});

console.log("redFill: " + JSON.stringify(redFill.flooded));
// redFill: [[0,0,0],[0,1,0],[1,1,0],[0,0,1]]

console.log("greenFill: " + JSON.stringify(greenFill.flooded));
// greenFill: [[1,1,1],[1,0,1],[1,0,0],[0,1,1]]

If needed, you can customize the getter function to suit your mesh structure.

From the output, you can observe that floodFill should be executed separately for each region. To identify all regions within the mesh, you may run floodFill from various starting points, ensuring not to repeat coordinates already included in previous regions. While this method is effective, there are more advanced techniques for detecting all regions in a single iteration.

Within a lattice composed of variously hued cubes, how can one locate the corresponding clusters?

Explaining Clusters

To Aid in Visualization

Answer №1

Answer №2

Similar questions

Form Validation behaving differently than anticipated

Counting Slides in a Slick Carousel

Problem with RadioButton click event not triggering

Can anyone tell me the best way to access the name attribute of an HTML element in TypeScript?

Encountering a problem when trying to dynamically change the value in a dropdown menu with Angular.js

How can I create a rectangular border around text using the HTML5 canvas?

Updating the redux state in react by passing a variable from a child component to the parent

sending ajax information to create a pie chart displaying data percentages

Create a new column in Material UI Grid by adding an empty div element instead of using padding

Question: How can I use the jQuery datepicker to ensure that the selected date remains in the

Unable to locate the value of the query string

Develop a duplication of the selected text without the need for the clipboard

The json loader in three.js gets an upgrade post r71

The unattractive visual outcome of Three.js rendering

Enhancing JavaScript Asynchronous Programming with EventLoop and async/await

Assign a class to an element depending on its position using JavaScript/jQuery

Selenium unable to interact with Javascript pop-up box

Bug in canvas rendering for Chrome versions 94 and 95

"Struggling with a basic Javascript function to refresh parts of a web page by calling a .php

Assign Monday as the selected day of the week in the MUI Datepicker 6