algorithm - 裁剪点云的最小边界框

Question

我试图找到 2d 点云的最小边界框，其中只有一部分点云可见。

给定一个粗略矩形的点云，经过裁剪后只有一个角可见:

点云在绿色边框处被剪裁。我知道边框在图像中的位置，而且我知道在该边框内总会恰好有矩形的一个角可见。我也知道矩形的大小。

现在我想找到包含此形状所有点的最小边界框，即使是那些在屏幕上不可见的点。因为我知道盒子的尺寸，找到可见的两个边就足以确定另外两个。
(实际上有两种可能的解决方案，因为形状的宽度和高度可以交换，但我们暂时忽略它)

我要找到红色的盒子。

我不需要精确解，也不需要快速解。我目前的尝试使用一种简单的蛮力算法，以 1° 的步长旋转点云并找到轴对齐的边界框。

我只需要一个标准来告诉我哪种轮换最适合这种情况。 Minimal-Area 是最小边界框的常用标准，但显然只有在所有点都可见时才有效。

可能有一些涉及凸包的最优算法，但我宁愿让解决方案尽可能简单

Answer 1

您真正需要的只是红色和绿色矩形交点角的位置。假设这些点是边界的近似值，这应该是获得这些点的一种相当可靠的方法:

• 选择彼此距离最远的两个点 A 和 B。那是相交区域的两个角。
• 找到与直线 AB ( example ) 两边垂直距离最大的点 C 和 D。那是区域交叉点的另外两个角。

A、B、C 和 D 是红色矩形的角以及绿色和红色矩形之间的交点的某种组合。要确定哪些是哪些，只需检查哪些在绿色矩形边框的小公差范围内。这样，您就有了足够的信息来轻松计算出红色矩形的位置。