   OBB from points?
  I'm looking for source code to create a 2D oriented bounding box (OBB) from a list of 2D points.It doesn't matter if it's optimized or not, or best implemented, it just has to work.   
  I don't have any code or a link, but I am pretty certain of the algorithm. I did a 3D OBB box creator a long time ago. The steps should be nearly the same.I believe what you do first is find the linear curve of best fit. This tells you the orientation of the box. To find the extents of the box you must first find the center of the box. There are a few methods to do this. The centroid ( I think that is the right term here) should do the trick. This can be found by finding the center of the AABB of the points.One of the extents will be the distance from the line perpendicular to the line of best fit that goes through the centroid, to the farthest point in the direction of the line of best fit. The other extent is the distance from the line of best fit to the farthest point in the direction perpendicular to the line of best fit. That isn't extremely clear, I know. I can clear that up later when I have more time.That should be the basics.   ;  Thanks, I have some basic details on it too, however, what I would like most is to see it working.Most of the source code I've found so far is highly "compartmentized".  What I'm looking for is something that can be easily plugged for use.   ;  The 3d version of this problem (minimum oriented bounding box) is more difficult than the 2d version, and this is why a statistical approximation is often used. An optimal 2d box can be found using the rotating calipurs method, and there are a few websites with good demos and possibly sourcecode for such algorithms. The rotating calipurs method provides a way to scan through all minimal bounding boxes such that at least one side is coincident to the convex hull of the point set. You should also be finding the bounding box for the convex hull instead of the point set itself.If you don't care about any sort of optimality, you can just find the AABB for the points and then use that as the OBB. It usually won't be the tightest fit, but it's still a perfectly valid OBB.   ;  Finding a convex hull first seems like more work?I don't think I have to know anything about convex hulls to find a OBB?   ;Quote:Original post by JakeMFinding a convex hull first seems like more work?I don't think I have to know anything about convex hulls to find a OBB?The convex hull is a preliminary computation that could be useful for other purposes.A OBB of the convex hull is acceptable for the interior points, which therefore don't need to be considered further. The rotating calipers algorithms, which provides an exact solution, processes the convex hull directly: the smallest OBB is guaranteed to have one of its sides collinear with one side of the convex hull.   ;  the problem with not taking the convex hull, iirc, is that if your point density is uneven, the calculation of eigen vectors can be innacurate. Also, in 2D, you can use the hull, which is a convex polygon, directly to compute a tight fitting OBB. Basically, given the convex polygon, calculate the bounding box around the polygon using each edge as one of the axis (and its perpendicular as the other axis), see which one gives the smallest OBB with respect to area coverage, and this is your bounding box.It may not be the tightest (example, a diamond), nor the fastest, but you can also add the direction from the centre of the polygon to each vertices as well and see if they give you a better OBB. Else, you would have to go with eigen vectors, and all that malarkey.   ;  The code I'm looking at extracts eigenvectors from 3x3 covariance matrix, but it fails miserablyabout half the time.  So, I would to get my hands on some other method.And these points are not ordered in any way, so I don't have any method to grab an edge inthe first place?   ;  If you're dealing with 2d points, then the covariance matrix would be 2x2 and everything would need to be adjusted accordingly. I think this simplifies to what Lexdysic was saying, except that finding the center of the OBB is done by finding the extreme points in the directions of the extents to find the size of the box and then just using that to find the center.Finding the convex hull is not difficult, and it computes the minimal convex polygon that bounds your point set. The giftwrapping and Graham's scan algorithms are not difficult to implement.   ;Quote:Original post by oliiiBasically, given the convex polygon, calculate the bounding box around the polygon using each edge as one of the axis (and its perpendicular as the other axis), see which one gives the smallest OBB with respect to area coverage, and this is your bounding box.Ok, assuming I'm able to create a convex hull from a list of points, is there diagram somewhere showing this method (obb from convex hull) ?I understand the hull edge lies along the bounding box, but how to get the 4 corners of the box from it?[Edited by - JakeM on September 12, 2007 11:12:48 PM]