minimal bounding box of a clipped point cloud

3
votes

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:

enter image description here

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)

enter image description here

I want to find the red box.

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

1
algorithmlanguage-agnosticgeometry2dbounding-box
The criteria should probably be that the area not included in the rectangle is maximum. – Abhishek Bansal
You are right, that's probably it. Or conversely, minimize the intersection of the bounding box and the clipping rectangle. Darn, this means I have to write code to intersect arbitrarily rotated rectangles, not an easy task. – HugoRune
writing code for intersection should not be difficult. You just need to calculate thier points of intersection and then just appy yhe formula for area of two right angled trianhles. – Abhishek Bansal
Computing convex hull is relatively easy. I think this is worth trying, since it reduces the problem to a polygon with fairly simple geometry. If your data set behaves in a nice way, the convex hull will have only a few edges which will be very close to the edges of the rectangular that you're looking for. This should increase the efficiency of your algorithm dramatically. – Tomasz Lenarcik

1 Answers

1
votes

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:

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