0

这是一个让我彻夜难受的问题。

给定一组点，说：

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

最大的多边形是一个 4x4 的正方形。为了这：

0 0 1 1 1 
0 1 1 1 1
1 1 1 1 1

最大的是梯形，但也会有不规则的，还有其他的变化……

如何确定最大可能？（最大意味着不能被任何其他多边形包围）我应该使用什么样的算法？

他们还需要其他属性，如面积、周长、凸面（t/f）和不变旋转的数量......

这是在说明中提供的，但我真的不明白它到底是什么......

调用编码大小在 2x2 和 50x50 之间（两个维度可以不同）之间的任何二维数组，其所有元素都是 0 或 1。调用编码成员的邻居m最多八个数组成员其值为 1，并且两个索引中的每一个与m的相应索引最多相差 1。给定特定编码，我们归纳地确定所有自然数d的深度多边形集d（对于此编码），如下所示：

给定一个自然数d，并假设对于所有 d 0 < d，深度为 d 0的多边形集合已经确定。将确定这些多边形的所有 1 的编码更改为 0。然后将深度 d 的多边形集确定为可以从该编码中获得的多边形集，方法是将 1 与它们的一些邻居以我们获得的方式连接一个最大多边形（即，一个不包含在任何其他多边形中的多边形，该多边形是通过将 1 与它们的一些邻居连接而从该编码获得的）。

4

2 回答 2

1

也许我太不耐烦了，但我发现你给出的指令很笨拙，我明白你为什么觉得它们难以理解。

您已经指定了答案，但这里有一些您可能希望探索的相关主题。

凸包可能是您想要的。凸包通常被描述为好像 2D 空间中的点都是钉板上的钉子。围绕钉子外侧的橡皮筋的形状是凸包。

http://en.m.wikipedia.org/wiki/Convex_hull_algorithms

此外，缩小（或增长）1 并用 0 替换它们的操作听起来像是形态学“侵蚀”操作。

http://en.m.wikipedia.org/wiki/Erosion_（形态学）

于 2013-10-27T02:56:22.673 回答
0 
Declare some integer B, set it to zero.

For every point p:
    If p has not been marked as "been":
        Mark p as "been"
        BFS/DFS from p and count the number of adjacent reachable points. Also mark each of these points as "been".
        If the number of reachable points + 1 is greater than B:
            B = the number of reachable points + 1

最后，B = 多边形的最大尺寸（以“覆盖”点为单位）。

于 2013-10-06T01:48:03.950 回答