find图像中最大的凸面黑色区域
我有一个这是一个小切口的图像：
正如你所看到的，它是黑色背景上的白色像素。 我们可以在这些像素（或更好的点）之间绘制虚线。 用这些线我们可以把区域。
我怎样才能find这个图像中不包含白色像素的最大的凸面黑色区域？
这里是一个小手绘的例子，我的意思是最大的凸面黑色区域：
PS：图像不是噪音，它表示水平排列的低于10000000的素数。
我将绘制一个正确的多时间algorithm。 毫无疑问，要进行数据结构方面的改进，但我相信要更好地理解这个问题尤其需要search非常大的数据集（或者可能是包含多边形）。
主循环包括猜测最大凸多边形中的最低点p（断开连接以支持最左边的点），然后计算可以使用p和点q使得（qy> py）||的最大凸多边形。 （qy == py && qx> px）。
dynamic程序依赖于与Graham扫描相同的几何事实。 假定不失一般性，p =（0,0），并按照它们与x轴（通过考虑它们的点积的符号来比较两个点）的逆时针angular度的顺序排列点q。 让sorting的点为q 1 ，…，q n 。 令q 0 = p。 对于每一个0≤i <j≤n，我们将计算点q 0上的最大凸多边形，它是q 1 ，…，q i – 1 ，q i和q j的一个子集。
因为只有“多边形”是零区域段q 0 q j ，所以i = 0的基本情况很容易。 归纳地说，为了计算（i，j）条目，我们将尝试使用（i，j）扩展（k，i）多边形。 我们什么时候可以这样做？ 首先，三angular形q 0 q i q j不能包含其他点。 另一个条件是angular度q k q q q j最好不是右转（再次检查相应点积的符号）。
最后，返回find的最大的多边形。 为什么这个工作？ 要certificate凸多边形具有dynamic程序所需的最佳子结构并不难，并且程序恰好考虑那些满足Graham的凸性表征的多边形。
试图find最大的凸面区域是一项艰巨的任务。 你会不会很好find最大面积的矩形 ？ 这个问题要容易得多，并且可以用O（n） – 像素数的线性时间来解决。 algorithm如下。
说你想find最大的免费（白色）像素矩形（对不起，我有不同颜色的图像 – 白色相当于你的黑色，灰色相当于你的白色）。
你可以通过两遍线性O(n)时间algorithm（n是像素数O(n)非常有效地做到这一点：
1）在第一遍中 ，按列从下到上，并且对于每个像素，表示直到此为止可用的连续像素的数量：
重复，直到：
2）第二遍 ，按行，读current_number 。 对于每个数字k >= k的连续数字（即高度为k潜在矩形）的总和。 closuresk > current_number的总和（可能的矩形），并查看总和（〜矩形区域）是否大于当前最大值 – 如果是，则更新最大值。 在每行的末尾，closures所有打开的潜在矩形（对于所有k ）。
这样你将获得所有最大的矩形。 它当然不是最大的凸面面积，但可能会给你一些提示（一些启发式）在哪里寻找最大凸面积。
您可以尝试将像素视为顶点并执行点集的Delaunay三angular剖分 。 然后，您将需要find最大的一组连接三angular形，它不会创build凹面形状，也不会有任何内部顶点。
如果我正确理解你的问题，这是一个连接组件标签的实例。 你可以从例如http://en.wikipedia.org/wiki/Connected-component_labeling开始;
我想到了解决这个问题的方法：
所有点中的所有点都会生成所有可能的3点子集。 这是你的空间中所有三angular形的集合。 从这个集合中删除所有包含另一个点的三angular形，并获得所有空三angular形的集合。
对于每个空的三angular形，你会把它扩大到最大尺寸。 也就是说，对于矩形外的每一个点，您都可以将其插入到多边形的两个最近点之间，并检查这个新三angular形内是否有点。 如果不是的话，你会记得那个点和它添加的区域。 对于每一个新点你想添加一个最大化增加面积。 当没有更多的点可以添加最大的凸多边形已经构build。 logging每个多边形的面积并记住面积最大的面。
这个algorithm的性能至关重要的是你能否确定a）一个点是否位于一个三angular形之内，以及b）在添加一个特定点之后该多边形是否保持凸出。
我认为你可以减lessb）成为a）的问题，然后你只需要find最有效的方法来确定一个点是否在三angular形内。 search空间的减less可以通过以下步骤实现：取一个三angular形，并在两个方向上将所有的边增加到无限长。 这将三angular形以外的区域分成6个子区域。 对我们有利的是，这些次区域中只有3个可以包含符合凸面约束的点。 因此，对于你testing的每一点，你需要确定它是否在一个凸扩展子区域，这又是它是否在某个三angular形的问题。
整个多边形随着它的演变而接近圆的形状将会有越来越小的区域，仍然允许凸面扩展。 凹点区域中的点将不会再次成为凸扩展区域的一部分，因此您可以快速减less需要考虑进行扩展的点数。 此外，在testing扩展点时，您可以进一步减less可能点的列表。 如果一个点被检验为假，那么它就在另一个点的凹形子区域，因此在被测点的凹形子区域中的所有其他点不需要考虑，因为它们也在内点的凹形子区域。 你应该能够很快地减less到可能点的列表。
当然，你仍然需要为每个空三angular形做这个。
不幸的是，我不能保证通过添加总是最大的新的地区你的多边形成为最大的多边形可能。
