logo标签列表

将矩形分割成随机形状的多边形

algorithmpolygonshapes
8

就像标题所说的那样，我需要将一个矩形分割成不规则的多边形。

例如，分成7个多边形：

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

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

我并不在意你用什么语言回答，但我会使用Java/Swing进行实现。

2
我认为你的意思不是“随机形状”的多边形；因为你示例中的多边形并非随机形状。你是指你不关心多边形的形状吗？这与“随机形状”是不同的。 - Paul Sonier
@McWafflestix：那么你所说的“随机形状”是什么意思？我的意思是，如果你运行这个算法多次，生成的多边形将会每次都不同。 - Austin Hyde
“随机”意味着与集合中的其他成员没有关系；对于按您指示分割的矩形，一些成员与其他成员有关系（例如，共同的边长）。 - Paul Sonier
@McWafflestix：我现在明白你的意思了。我的意思是，随机性应该在每次运行算法时都有所变化，但所有内容仍应适合原始矩形。 - Austin Hyde
2个回答
15
+1，因为你想到了我想到的 :) 请注意，Voronoi图形是凸的，而原始示例有一些凹形的部分。您可以随机合并几个Voronoi邻居以获得凹形的部分。 - celion
@celion 我认为“随意形状”只是一个直观的概念...而沃罗诺伊图则提供了一个很好的游乐场，可以通过删除一些边来获得奇怪的形状。（哎呀！又在想同样的事情:D） - Dr. belisarius
我们可以为每个多边形定义最小面积吗？ - Amit Kumar Gupta
5
我会把一堆随机的线条画在整个矩形上，然后在每个线交点处“分割”线条，这样你就有了某种线网。然后删除尽可能多的随机线段，直到达到所需的多边形数量。
编辑：因此，在添加线条后，您的示例将如下所示：
+----+---+----+---+
|\'--.\_/|   /    |
| \    X |''/-..__|
|--\--+-\+-/------|
|___\/___\/_______|
|   /\   /\       |
|__/__\_/|_\______|
| /    X |  \     |
++----+-++---+----+
这让我想起了一个二维版本的断层算法。 - Seth
我觉得这个问题在于很难通过程序来确定需要删除哪些行。此外，这可能会生成非常小的多边形，如果有可能的话，我想避免这种情况。 - Austin Hyde
我不知道错误算法，但是确实非常相似！ - Lucero
奥斯汀，你增加的线段越少，多边形就会变得越大。至于哪些线段需要删减，可以随机选择，如果需要可以使用规则集（例如仅删除与边框接触的多边形中的线段），或者按多边形大小选择（例如从最小接触多边形表面选择线段）。 - Lucero
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接