问题描述
我试图找到2d点云的最小边界框，其中只有一部分点云可见.
I am trying to find the minimal bounding box of a 2d point cloud, where only a part of the point cloud is visible.
给出一个具有粗糙矩形形状的点云，将其裁剪以使只有一个角可见:
Given a point cloud with a rough rectangular shape, clipped so that only one corner is visible:
点云被剪裁为绿色边框.我知道边框在图像中的位置，并且我知道在该边框内始终总是有一个矩形形状的正好一个角.我也知道矩形的大小.
The point cloud is clipped at the green border. I know the position of the border in the image, and I know that there will always be exactly one corner of the rectangular shape visible within this border. I also know the size of the rectangular shape.
现在，我想找到包含此形状所有点的最小边界框，即使这些点在屏幕上也不可见.由于我知道盒子的尺寸，因此找到可见的两个侧面就足以确定另外两个侧面.
(实际上有两种可能的解决方案，因为形状的宽度和高度可以交换，但是暂时让我们忽略它)
Now I want to find the minimal bounding box that contains all the points of this shape, even those not visible on-screen. Since I know the dimensions of the box, finding the two sides visible is enough to determine the other two.
(there are actually two possible solutions, since width and height of the shape can be swapped, but let's ignore that for the moment)
我想找到红色框.
我不需要确切的解决方案，也不需要快速的解决方案.我目前的尝试是使用一种简单的蛮力算法，该算法以1°的步长旋转点云，并找到与轴对齐的边界框.
I do not need an exact solution, or a fast one. My current attempt uses a simple brute force algorithm that rotates the point cloud in 1° steps and finds the axis-aligned bounding box.
我只需要一个标准，告诉我哪种旋转是这种情况下最好的旋转.最小面积是最小边界框的常用标准，但是显然只有在所有点都可见的情况下才有效.
I just need a criterion that tells me which rotation is the best one for this case. Minimal-Area is the usual criterion for a minimal bounding box, but that obviously only works if all points are visible.
可能存在一些涉及凸包的最佳算法，但我宁愿使解决方案尽可能简单
There is probably some optimal algorithm involving convex hulls, but I'd rather keep the solution as simple as possible
推荐答案
您真正需要的只是红色和绿色矩形之间的交点的角位置.假设这些点是边界的一个不错的近似值，那么这应该是一种合理可靠的方法:
All you really need is the positions of the corners of the intersection between your red and green rectangle. Assuming the points are a decent approximation of the border, this should be a reasonably reliable method to get those:
- 选择彼此相距最远的两个点A和B.那是相交区域的两个角.
- 找到距AB线最大垂直距离的点C和D(示例)在任一侧.那是该地区交叉路口的另外两个角落.
- Pick the two points A and B most distant from eachother. Those are two corners of the area of intersection.
- Find the points C and D with the greatest perpendicular distance from the line AB (example) on either side. Those are another two corners of the area intersection.
A，B，C和D是红色矩形的角以及绿色和红色矩形之间的交点的某种组合.要计算出哪个，只需检查哪个在绿色矩形边框的较小公差范围内即可.这样，您便获得了足够的信息，可以轻松确定红色矩形的位置.
A, B, C & D are some combination of corners of the red rectangle and intersections between the green and the red rectangles. To work out which are which, just check which are within some small tolerance of the green rectangle's border. And with that, you've got enough information to easily work out the position of the red rectangle.
这篇关于修剪点云的最小边界框的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！