c# - 在 X、Y 平面上的某个区域中最大化矩形，其中包含表示该区域的点列表

Question

好的，我需要帮助最大化长条对象中可以是许多不同形状的矩形的面积。我已经完成了大部分工作。

我正在使用 kinect 和深度像素在 C# 中工作。

这张图片只是我能找到的最能代表我所说的内容。

我需要在 x，y 平面上的该区域中生成一个矩形，以最大化该区域，同时使每个边缘都是实心的。

我已经将实心形状表示为 x、y 平面上的点列表。所以我有二维平面上的形状。有点像这样：

为了简化问题，我将生成一个边平行于 x 和 y 线的矩形。我不是在寻找代码。我只需要一些可以阅读并尝试实施的方向或算法。

如果需要任何澄清，请告诉我。

Answer 1

如果您只需要边界矩形，您可以遍历点列表。存储 X 和 Y 的最小值和最大值（如 minX、minY、maxX、maxY）。浏览整个列表，如果检查每个点，请执行 4，例如：

if(point.X < minX) minX = point.X
if(point.Y < minY) minY = point.Y
if(point.X > maxX) maxX = point.X
if(point.Y > maxY) maxY = point.Y

这将为您提供边界矩形。Min 和 Max 是两个点，根据您的坐标系，代表左上点和右下点，您可以轻松地使用它们来绘制矩形。

Answer 2

看看最大的空矩形问题。这是一篇关于计算其解决方案的算法的文章。

更准确地说，这是一个问题，包括在给定一组点的情况下搜索不包含任何点的最大区域。在您的情况下，您可以将其应用于描述 2D 形状边缘的一些点，以及外部的一些点。然后本文的程序将计算黄色区域中的最大矩形。我确实应用了这样的程序来找到不包含透明像素的图像的最大部分。它运作良好，但有点慢。

该解决方案适用于一组点（即没有段），但您可以轻松地计算出近似您的形状的近似解决方案。