algorithm - 用矩形填充 2D 形状

Question

我希望用矩形填充任意 2D 形状，例如通过查看矩形的合成图像可以看到 2d 形状。最终结果应该类似于此应用程序生成的图像：http: //www.shapecollage.com/（不，我不是要复制所述应用程序，但我想提供类似的功能作为更大应用程序的一部分） .

我从这个SO question 中知道，可能不存在针对我的问题的最佳解决方案，但是应该有一个相当好的结果，并且足以满足我的要求。到目前为止，我已经基于洪水填充算法的思想尝试了以下两种方法：

方法一

1. 从形状中的任意点开始，在此点绘制一个矩形。

2. 检查上一个图像的右下左上的一个点，例如如果与上一个图像并排绘制，则检查的点对应于下一个图像的中心

   // 为右移寻找新的 x 坐标的示例

   newCenter.x = oldCenter.x + oldWidth + newWidth;

3. 检查新的中心点是否 a) 在 2D 形状中和 b) 不在已绘制的矩形内。如果两个条件都满足，则绘制矩形并继续第 2 步，否则不执行任何操作。

方法二

与方法 1 相同，但没有条件，即矩形的新中心不允许在绘制的矩形内。而是添加了所有方向的填充。

// Example of finding new x-coordinate for right move
newCenter.x = oldCenter.x + oldWidth + newWidth + padding;

两种方法都提供了极其有限的结果，并且无法完全填充形状，尽管有时部分轮廓在方法 1 中变得可见。

我很高兴我可以尝试获得与上述示例类似的结果的任何输入、想法或经过验证的方法。谢谢！

Answer 1

尝试 Weiler-Atherton 裁剪算法；我用它来填充矩形形状的多边形。 http://en.wikipedia.org/wiki/Weiler%E2%80%93Atherton_clipping_algorithm

Answer 2

如果您只需要密切（不完美）复制形状而不是颜色，只需将您的形状放在假想的网格上，然后用随机选择的矩形或图片填充形状内部的单元格。你也可以旋转它们，这样就不会太无聊。