我有一张图片，这是其中的一小部分：
如您所见，这是黑色背景上的白色像素。我们可以在这些像素（或更确切地说，点）之间画出想象中的线条。通过这些线条，我们可以将区域围起来。
我该如何找到这张图片中不包含白色像素的最大凸多边形黑色区域呢？
下面是我手绘的一个示例，它展示了最大凸黑色区域的意思：
P.S.：这张图片不是噪声，它表示小于10000000的质数按水平顺序排列。
在图像中找到最大的凸黑色区域
42
- orlp
26
5如果这些数是质数，为什么它们分布相对均匀？同时，你能否展示一个小的例子（10x10 的图片），并标出最大的区域？ - Karoly Horvath
3你确定这能得出有意义的结果吗？整数只有一个维度。你之所以得到一个面积是因为你在特定位置断开数字并开始新的一行。很可能根据你断开数字的位置，你会得到不同大小的最大黑色区域。 - Andreas
4无论这些数是否真的是质数 - 这个问题本身肯定是有趣的。 - Ingo
4你的问题并没有明确定义，因为如果区域可以是凹的，你可以画一个多边形包含所有点，这个区域将恰好是整个黑色区域。另一件事是如果你要求最大的凸面积。但在你的例子中，那个区域是凹的。 - Simone
2@John 我仍然认为定义不够清晰 ... 一个好的问题是找到最大的凸黑色区域，我会研究并发布关于此的答案。 - Simone
显示剩余21条评论
5个回答
12
试图找到最大凸面积是一个困难的任务。你是否只想找到最大面积的矩形？这个问题容易解决，可以在O(n) - 像素数的线性时间内解决。该算法如下。
假设你要找到自由（白色）像素的最大矩形（抱歉，我的图片是不同颜色的 - 白色等同于黑色，灰色等同于白色）。
你可以通过两次遍历的线性O(n)时间算法（其中n为像素数）来非常高效地完成这项工作：
1）在第一次遍历中，从底部到顶部按列遍历，对于每个像素，标记可用像素的数量：
重复操作，直到：
2）在第二次遍历中，逐行读取current_number。对于每个数字k，保持连续数字的总和>= k（即高度为k的潜在矩形）。关闭高度k > current_number以上的总和（潜在矩形），并查看总和（矩形面积）是否大于当前最大值 - 如果是，则更新最大值。在每行末尾，关闭所有打开的潜在矩形（对于所有k）。
这样你就可以得到所有的最大矩形了。当然，这不同于最大凸面积，但可能会给出一些提示（一些启发式）在哪里寻找最大凸面积。
- Tomas
2
正如我在问题评论中所写的：
https://dev59.com/YGw05IYBdhLWcg3wkirX 有一个类似的问题，但这个问题涉及矩形。我不认为我在那里看到了这个解决方案 还有一个维基百科页面介绍了这个问题：http://en.wikipedia.org/wiki/Largest_empty_rectangle - Sjoerd C. de Vries
@TMS 寻找最大矩形面积只是这个问题的重复：https://dev59.com/J3E95IYBdhLWcg3wDpmg - tommy.carstensen
11
I'll sketch a correct, poly-time algorithm. Undoubtedly there are data-structural improvements to be made, but I believe that a better understanding of this problem in particular will be required to search very large datasets (or, perhaps, an ad-hoc upper bound on the dimensions of the box containing the polygon).
主要循环包括猜测最大凸多边形中最低点p（优先选择最左侧的点），然后计算可以与p和点q一起构成的最大凸多边形，其中(q.y > p.y) || (q.y == p.y && q.x > p.x)。
该动态程序依赖于与 Graham's scan 相同的几何事实。不失一般性，假设p =（0,0），并按照逆时针角度与x轴成的顺序对点q进行排序（通过考虑它们的点积符号来比较两个点）。让排序后的点为q1，…，qn。让q0 = p。对于每个0 ≤ i < j ≤ n，我们将计算由点q0、q1，…，qi - 1，qi和qj组成的子集上的最大凸多边形。
基础情况下i = 0很容易，因为唯一的“多边形”是零面积线段q0qj。归纳地，要计算（i，j）条目，我们将尝试对所有0 ≤ k ≤ i进行扩展（k，i）多边形与（i，j）相连。什么时候可以这样做？首先，三角形q0qiqj不能包含其他点。另一个条件是角度qkqiqj最好不是右转（再次检查适当的点积符号）。最后，返回找到的最大多边形。为什么这有效？不难证明，凸多边形具有动态程序所需的最优子结构，并且该程序考虑了完全满足Graham凸性描述的那些多边形。
主要循环包括猜测最大凸多边形中最低点p（优先选择最左侧的点），然后计算可以与p和点q一起构成的最大凸多边形，其中(q.y > p.y) || (q.y == p.y && q.x > p.x)。
该动态程序依赖于与 Graham's scan 相同的几何事实。不失一般性，假设p =（0,0），并按照逆时针角度与x轴成的顺序对点q进行排序（通过考虑它们的点积符号来比较两个点）。让排序后的点为q1，…，qn。让q0 = p。对于每个0 ≤ i < j ≤ n，我们将计算由点q0、q1，…，qi - 1，qi和qj组成的子集上的最大凸多边形。
基础情况下i = 0很容易，因为唯一的“多边形”是零面积线段q0qj。归纳地，要计算（i，j）条目，我们将尝试对所有0 ≤ k ≤ i进行扩展（k，i）多边形与（i，j）相连。什么时候可以这样做？首先，三角形q0qiqj不能包含其他点。另一个条件是角度qkqiqj最好不是右转（再次检查适当的点积符号）。最后，返回找到的最大多边形。为什么这有效？不难证明，凸多边形具有动态程序所需的最优子结构，并且该程序考虑了完全满足Graham凸性描述的那些多边形。
- the guy formerly known as d
2
1事实证明，由于Edelsbrunner＆Guibas 1989年以及Dobkin，Edelsbrunner＆Overmars 1990年的算法，存在O（n ^ 3）的算法。我认为我的算法是O（n ^ 4）。 - the guy formerly known as d
4后一篇论文可以在http://www.cs.duke.edu/~edels/Papers/1990-J-05-EmptyConvexPolygons.pdf找到，前一篇则在http://www.cs.duke.edu/~edels/Papers/1989-J-01-TopologicalSweep.pdf。 - Sjoerd C. de Vries
5
您可以将像素视为顶点，并对点集执行Delaunay三角剖分。然后，您需要找到最大的一组连接三角形，这些三角形不会创建凹形状并且没有任何内部顶点。
- tkerwin
7
不错。一些泛洪填充算法可以解决这个问题，只要很容易检查添加一个三角形是否使当前配置成为凸形。 - Alexandre C.
我怀疑贪心算法不能用于寻找那些条件下的最大形状。可能需要一种动态规划的解决方案。 - tkerwin
每个三角形都包含在恰好一个极大凸连通分量中。由于这些组件预计很小，因此贪婪算法可以解决。 - Alexandre C.
3你的第二句话听起来像是把问题掩盖过去。 - Sjoerd C. de Vries
@Sjoerd 这并不重要，因为最大的凸多边形可能无论如何都不能满足 Delaunay 三角剖分。以一个边平行于 y 轴的单位六边形为例，然后在 (±1e6, 0) 处放置两个点。三角剖分会阻碍六边形，该六边形不包括六边形的顶部和底部。 - the guy formerly known as d
显示剩余2条评论
2
如果我正确理解了你的问题，那么这是一个连通组件标记的实例。你可以从这个链接开始学习：http://en.wikipedia.org/wiki/Connected-component_labeling
- Jean-Denis Muys
4
这并不是直接的问题，因为所有的黑色像素都是相连的。你可以称之为“凸包组件标记”，即使它们可能有关联，但它们是不同的问题。 - static_rtti
@static_rtti：这是因为凸性要求首先没有得到满足，因为我在这里没有表述好问题，也没有为自己制定好问题。对问题的评论启发了我。也许提问者可以撤回他的答案？ - orlp
是的，我在你的问题中漏掉了“凸”的部分。对此很抱歉。 - Jean-Denis Muys
Jean-Denis-Muys: 不用担心，我一个小时前就编辑了它，因为我的原始问题一点也不有趣（你可以连接除最外层点以外的所有点）。 - orlp
1
我想到了一种解决这个问题的方法：
从所有点的集合中生成所有可能的三点子集。这是您空间中所有三角形的集合。从该集合中删除包含另一个点的所有三角形，您将得到所有空三角形的集合。
对于每个空三角形，您都应该将其扩展到最大尺寸。也就是说，对于矩形外的每个点，您都应该将其插入到多边形的两个最近点之间，并检查此新三角形中是否有点。如果没有，则将记住该点及其添加的面积。要添加的每个新点都应该是最大化添加面积的那个点。当无法再添加更多点时，就构建出了最大的凸多边形。记录每个多边形的面积并记住具有最大面积的那个。
这种算法的性能关键在于您能否确定a）点是否在三角形内部以及b）在添加某个点后多边形是否仍然是凸多边形。
从所有点的集合中生成所有可能的三点子集。这是您空间中所有三角形的集合。从该集合中删除包含另一个点的所有三角形，您将得到所有空三角形的集合。
对于每个空三角形，您都应该将其扩展到最大尺寸。也就是说，对于矩形外的每个点，您都应该将其插入到多边形的两个最近点之间，并检查此新三角形中是否有点。如果没有，则将记住该点及其添加的面积。要添加的每个新点都应该是最大化添加面积的那个点。当无法再添加更多点时，就构建出了最大的凸多边形。记录每个多边形的面积并记住具有最大面积的那个。
这种算法的性能关键在于您能否确定a）点是否在三角形内部以及b）在添加某个点后多边形是否仍然是凸多边形。
我认为你可以把 b) 简化成 a) 的问题，然后只需要找到最有效的方法来确定一个点是否在三角形内。搜索空间的缩小可以通过以下方式实现：取一个三角形并将所有边延长至无限长度。这将使得三角形外部的区域分为 6 个子区域。对我们有利的是，只有其中的 3 个子区域可能包含符合凸性约束条件的点。因此，对于每个测试点，您需要确定它是否在凸扩展子区域中，而这又是一个关于它是否在某个三角形内的问题。
整个多边形随着演变趋近于圆形时，仍允许凸性扩展的区域将变得越来越小。曾经处于凹区域的点将不会再次成为凸性扩展区域的一部分，因此您可以快速减少需要考虑扩展的点的数量。此外，在测试扩展点时，您还可以进一步缩小可能考虑的点列表。如果一个点测试为 false，则它位于另一个点的凹区域内，因此该测试点凹区域内的所有其他点都不需要考虑，因为它们也位于内部点的凹区域内。您应该能够非常快速地缩小可能考虑的点列表。
当然，你还需要为每个空三角形执行此操作。
不幸的是，我不能保证通过始终添加最大新区域来使你的多边形变成可能的最大多边形。
- Andreas
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接