是否有已知的算法来检测像素，以确保形状的连续性？

Question

我试图在Javascript中创建一个程序，使一个小形状在二进制2D空间中随机演化。

第一条规则是形状使用的像素数保持不变。这是一个非常小的数字(目前9)。

第二条规则是，所有像素都应该保持连续(至少在它们的角处)。

在每个步骤中，一个像素被随机移除并移动到与其余像素相接触的位置。但是，只有在不破坏形状的连续性的情况下，像素才能被删除。

在附图中，蓝色像素可以移动，而红色像素不能移动。

​

​

我不知道如何检测哪些像素是必须的，以保持连续性。有什么已知的算法吗？这个问题似乎接近康威的“生命游戏”，但据我所知，康威的规则忽略了连续性的概念，也没有保持一定数量的活化细胞。到目前为止，我还没有找到合适的元胞自动机算法。

Answer 1

形状的约束非常简单，如果移动一个像素破坏了形状，那么它就是无效的移动。

因为我们知道形状的大小总是9像素，所以您可以通过计数像素数来确认形状是否有效，如果您对形状进行了填充，则可以通过计算填充的像素数来确定形状是否有效。

所以把它分解成几个阶段。

1. 选择一个随机像素，这是形状的一部分。
2. 选择另一个随机像素，它是形状的一部分，与第一个不相同。
3. 移动随机像素。
4. 使用自定义的填充算法，从像素2开始。在填充形状时，计算填充的像素数。
5. 如果填充的像素数不等于9，则移动像素是无效的移动。回到原版。

下面是一个例子，当然有一些地方是可以优化的，但这应该是一个很好的起点。

更新:为了处理多个形状，并防止它们合并，这也将工作。只需要一个小模块，在填充过程中，请确保您移动的像素也包括在内。

​

const canvas = document.querySelector('canvas');
const ctx = context = canvas.getContext('2d');
canvas.width = 20;
canvas.height = 10;
ctx.imageSmoothingEnabled = false;

let i = ctx.getImageData(0, 0, canvas.width, canvas.height);

const pp = (x,y) => (x + (y*canvas.width)) * 4;

function putpixel(x, y, t) {
  const s = pp(x,y);
  i.data[s] = t ? 255 : 0;
  i.data[s + 3] = t ? 255 : 0;
}

function getpixel(x, y) {
  const s = pp(x,y);
  return i.data[s] === 255;
}
  
  

for (let y = 0; y < 3; y += 1) 
  for (let x = 0; x < 3; x += 1)
    putpixel(x + 4,y + 4,true);
//let add 2 shapes, still work?    
for (let y = 0; y < 3; y += 1) 
  for (let x = 0; x < 3; x += 1)
    putpixel(x,y,true);



ctx.putImageData(i, 0, 0);

function findPixel(active) {
  while (true) {
    const x = Math.trunc(Math.random() * canvas.width);
    const y = Math.trunc(Math.random() * canvas.height);
    const p = getpixel(x,y);
    if (p === active) return {x,y, p:y*canvas.width + x};
  }
}


function isValid(p, p2) {
  let count = 0; 
  let hit = false;
  const done = {};
  function fill(x, y) {
    const pstr = `${x}:${y}`;
    if (done[pstr]) return;
    if (x < 0) return;
    if (x >= canvas.width) return;
    if (y < 0) return;
    if (y >= canvas.height) return;
    if (!getpixel(x, y)) return;
    count += 1;
    
    if (!hit) {
      if (p2.x === x && p2.y === y) hit = true;
    }
    
    done[pstr] = true;
    fill(x -1, y - 1);
    fill(x   , y - 1);
    fill(x +1, y - 1);
    
    fill(x -1, y);
    fill(x +1, y);
    
    fill(x -1, y + 1);
    fill(x   , y + 1);
    fill(x +1, y + 1);   
  }
  fill(p.x, p.y);
  return count === 9 && hit;
}
    
function evolve() {
  i = ctx.getImageData(0, 0, canvas.width, canvas.height);
  
  const movePixel = findPixel(true);
  const otherPixel = findPixel(true);
  if (movePixel.p !== otherPixel.p) {
    const rndPixel = findPixel(false);
    putpixel(movePixel.x, movePixel.y, false);
    putpixel(rndPixel.x ,rndPixel.y, true);
    if (isValid(otherPixel, rndPixel))  
      ctx.putImageData(i, 0, 0);
  }
  setTimeout(evolve, 0);
}


setTimeout(evolve, 0);

* { 
  padding: 0;
  box-sizing: border-box;
  margin: 0;
}

html {
  height: 100%;
}

body {
  background-color: black;
  display: grid;
  justify-content: center;
  align-content: center;
  height: 100%;
}

canvas {
  transform: scale(19);
  image-rendering: pixelated; 
}

<canvas>
</canvas>

​

Answer 2

这些被称为切点或连接点，是的，有一个算法来找到它们。