How to determine if a solid fits inside a given box in O(N^2)?
I'm looking for an algorithm that will let me determine if a solid object can fit inside of a box (rectangular prism) with given dimensions. The solid may be rotated and translated to fit inside the box.
I already have a solution to this problem:
(EDIT: this is not a valid solution)
This works, but I am looking for a more efficient solution. The minimum bounding box algorithm runs in O(n^3) time where n is the number of vertices. I am hoping for an O(n^2) algorithm.
Note that instead of a "solid object" I may just as well be asking if the set of points which form the convex hull of the solid can fit inside the box.
You might want to take a look at this paper. It gives an algorithm than compute an 1+epsilon approximation of a 3D minimum bounding box in O(n log n + 1/epsilon^3) time.
Quickly ruling some objects out
If you expect the answer to usually be "No", you may be able to rule out many instances (fairly) quickly as follows: if there is a pair of points separated by more than the longest diagonal of your box, then the shape cannot possibly fit in it. This is O(n^2), but you can stop as soon as you find a more distant pair, and you could also first sort points along the longest dimension and take points from opposite ends as your pairs to increase the chances of finding
Combined with Eric J.'s suggestion of using a bounding sphere to rule an object in, this might quickly solve many cases.
Quickly ruling some objects in
Another option you have is to just randomly project the points a bunch of times, and calculate the AABB; if it fits inside your box, you're done. This requires generating random unit-length vectors.
If this isn't outdated there is currently no faster exact algorithm:
The current fastest 3D bounding cuboid algorithm is by [O'Rourke, 1985], which runs in O(n3) time, has several special cases, and is considerably more difficult to implement. O'Rourke's algoruthm is based on his observation that “A box of minimal volume circumscribing a convex polyhedron must have at least two adjacent faces that contain edges of the polyhedron.” No faster exact algorithm has been found.
Regardless, since O(n3) algorithms can be very slow in practice for large point sets, there is considerable interest in fast approximations for the minimum cuboid in 3D and higher dimensions. Several methods have been suggested, such as: (1) only consider cuboids that have a face coinciding with a polyhedron face (which is O(n2) as discussed in [O'Rourke, 1985], and can be 2 times too large), (2) principal component analysis on the point set (which is fast, but often results in a poor solution), (3) brute-force methods that sample many possible orientations for a cuboid, (4) reduce a large point set to a smaller approximate set (eg, by selecting the cells in a discrete grid that contain set points) [Barequet & Har-Peled, 1999], and others. All these methods have trade-offs between the solution accuracy versus the efficiency of execution.
So you will have to decide if you need exact results, or if you can live with an approximation and use on of the referenced articles.
链接地址: http://www.djcxy.com/p/82088.html上一篇: .NET中的依赖注入与例子？