algorithm - 将一个矩形分成任意形状的多边形

Question

正如标题所说，我需要将一个矩形分成随机形状的多边形。

例如，有 7 个多边形：

+--------+--------+
|\       |   2    |
| \  1   |''--..__|
|  ------|  5     |
| 3  /   \________|
|   /    /\   6   |
|__/ 4  /  \______|
|      /  7       |
+-----+-----------+

我不知道是否已经有一种算法可以解决这个问题，但我似乎无法理解这一点。

我并不特别关心你用什么语言回答，但我会用 Java/Swing 来实现。

Answer 1

您可以在矩形上放置一堆随机点，然后计算 Voronoi 图。

这是一个 Java/Swing 实现。

我做了一些示例（但使用 Mathematica，而不是上述实现）

！

Answer 2

I'd draw a bunch of random lines across the full rectangle and then "split" the lines at each line intersection, so that you basically have some kind of net of lines. Then remove as many random line segments as you like until you reach the desired number of polygons.

Edit: So for your sample it would have been like this after adding the lines:

+----+---+----+---+
|\'--.\_/|   /    |
| \    X |''/-..__|
|--\--+-\+-/------|
|___\/___\/_______|
|   /\   /\       |
|__/__\_/|_\______|
| /    X |  \     |
++----+-++---+----+