php - 将一种形状变形为另一种形状的算法。

Question

我正在尝试开发一种算法，将一个“形状”变成另一个“形状”。两种形状都是任意的，甚至可能有更小、不连贯的形状。

到目前为止，我的基本想法如下:定位形状的边缘，沿着这些边缘放置点，然后对目标图像执行相同的操作，然后将这些点移动到它们的目标。

这是一个例子:

我只是不知道从哪里开始。上图是一种简化，实际用例具有更复杂的形状/轮廓。我的主要问题是:如何处理不相交的形状？我能想到的最好办法是找出两部分之间最近的点，并将它们连接在一起作为路径的一部分。但我将如何实现呢？

我还没有任何代码，我还在计划阶段。我想我要问的是，是否有人可以将我链接到任何可能有帮助的资源，或提供任何指示。搜索谷歌已经产生了一些有趣的变形算法，但它们都处理完整的图像并涉及将图像分解成碎片以 reshape 它们，这不是我想要的。

请注意，这将在 JavaScript 中使用，但如果更容易，也可以在 PHP 中预先计算。

Answer 1

最好将问题分解成多个可以独立解决的小问题。这样你在解决这个问题后也拥有独立的功能，可以添加到一些全局模块集合中。

首先我们需要弄清楚 from_shape 中的哪个像素到 to_shape 中的哪个像素。
我们可以用以下方法计算:

1. 将 to_shape 放在 from_shape 上。
   

2. 对于 from_shape 中的每个像素，找到其最接近的 to_shape 像素。
   形状中的每个像素都必须有一个唯一的 ID，例如，该 ID 可以是它的 xy 位置。

3. 现在您可以记录 from_shape 中的每个唯一像素，以及它在 to_shape 中到达的唯一像素。

4. 删除重叠的形状，回到原来的形状，
   现在 from_shape 中的每个像素都知道它在 to_shape 中的目的地。

我们还需要知道每个像素有哪些“ sibling ”。
兄弟是紧挨着另一个像素的像素。
要找到它，请转到给定像素，从它收集半径为 1 的所有像素，所有这些像素都是黑色的……是来自像素的 sibling 。当像素行进到目的地时，此信息对于将形状保持为一个单元是必需的。跳过 sibling 会大大加快和简化变形，但如果没有它们，变形过程中形状可能会变得支离 splinter 。可能想从无兄弟版本开始，看看结果如何。

最后我们实现变形:

1. 有 morph_time_duration。
   对于 from_shape 中的每个像素，在 to_shape 中找到它到目的地的距离。
   该距离除以 morph_time_duration，就是变形期间像素的速度。
   此外，朝向目的地的 Angular 是行进的 Angular 。
   所以现在你有了速度和 Angular 。

2. 因此在变形过程中的每一帧，给定的 from_pixel 现在知道行进的方向、速度，并且它也知道它的 sibling 。因此，在每一帧中，在以其速度沿其方向行进后，只需在其新位置绘制像素。然后为所有这些像素兄弟画一条线。

这将显示您的变形。