C算法确定点阵中最大的多边形

Question

这是一个让我烦恼了一夜的问题。

给定一组点，说:

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) 和不变旋转数...

---

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

Call encoding any 2-dimensional array of size between between 2x2 and 50x50 (both dimensions can be different), all of whose elements are either 0 or 1. Call neighbour of a member m of an encoding any of the at most eight members of the array whose value is 1, and each of both indexes differs from m's corresponding index by at most 1. Given a particular encoding, we inductively determine for all natural numbers d the set of polygons of depth d (for this encoding) as follows:

Let a natural number d be given, and suppose that for all d₀ < d, the set of polygons of depth d₀ has been determined. Change in the encoding all 1's that determine those polygons to 0. Then the set of polygons of depth d is determined as the set of polygons which can be obtained from that encoding by connecting 1's with some of their neighbours in such a way that we obtain a maximal polygon (that is, a polygon which is not included in any other polygon obtained from that encoding by connecting 1's with some of their neighbours).

Answer 1

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

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

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

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

此外，缩小(或增大)1 并将其替换为 0 的操作听起来像是形态学上的“腐 eclipse ”操作。

http://en.m.wikipedia.org/wiki/Erosion_(morphology)