裁剪点云的最小边界框 [英] minimal bounding box of a clipped point cloud

问题描述

我试图找到二维点云的最小边界框，其中只有一部分点云可见.

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(example)两边.这是区域交叉点的另外两个角.

• 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.

这篇关于裁剪点云的最小边界框的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！