問題描述
如何計算一個長方體與其相鄰長方體的接觸面積 (How to calculate area of contact of one rectangular cuboid to its adjacent cuboids)
I'm trying to position different-sized rectangular cuboids next to each other such that the area of contact between those is maximized.
In a brute-force kind of way I'm searching for a possible position for each to be positioned cuboid in space which doesn't intersect with any other cuboids. I realized this using Java 3D's BoundingBox class where it's possible to check whether a given box intersects with a given collection of other boxes. Now I got many possible locations from which I need to choose the one with the highest area of contact to other boxes.
My problem is that I don't know how to calculate this area efficiently. A little example...
Box 1: lower left point x=0,y=0,z=0; upper right point x=10,y=10,z=10
Box 2: lower left point x=10,y=0,z=0; upper right point x=15,y=5,z=5
Box 3 has the same dimensions as Box 1 and should be positioned with maximum area of contact
In this example all positions where one side of Box 3 matches any except the right side of Box 1 (where Box 2 is) are optimal solutions.
I would be very glad if someone has an idea or even a solution. I'm also happy with free libraries if they are not too huge.
Thanks!
參考解法
方法 1:
Consider each potential pair of touching faces in turn.
Place box 2 anywhere in contact with box 1. You then recursively search. For each location you identify all the intersecting cuboids and then find minimum movement up, down, left and right that would prevent an intersection with one of those intersecting cuboids. This establishes four new places to search from. You then work out from these as well.
To clarify, if you are moving left, you find the rightmost left face of an intersecting cuboid and move so that face no longer intersects. Other cuboids will probably still intersect but we will recursively move away from them.
If there are no intersections, you have a stop location and you note the area and carry on searching.
If a move make it impossible to touch the original box, you don't explore further along that route.
For each face you can find that either no locations are possible, or there is at least one with a maximal are of contact for that face.
You then repeat the process for the other 5 faces.