This week's book giveaways are in the Java EE and JavaScript forums.
We're giving away four copies each of The Java EE 7 Tutorial Volume 1 or Volume 2(winners choice) and jQuery UI in Action and have the authors on-line!
See this thread and this one for details.
The moose likes Beginning Java and the fly likes algorithm to compute the common space of two cuboid? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "algorithm to compute the common space of two cuboid?" Watch "algorithm to compute the common space of two cuboid?" New topic
Author

algorithm to compute the common space of two cuboid?

liu hao
Greenhorn

Joined: Oct 02, 2009
Posts: 9
the cuboid is specified by two vertex which are Point3D objects meaning that they are parallel to the axises. My approach is to first determine if the two cuboids have common space by compare the distance between two mid-point of the two cuboids with half of their length on the X,Y and Z axis respectively. If they do have common space, then I sort four coordinates on each axis and and calculate it.
But the automate marker(a software) always said my algorithm is no good. my algorithm is indeed tedious. I'm eager to know if anybody has a better one.
any suggestion is appreciated.thanks.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
I don't have an answer off the top of my head, but I find the question interesting, so perhaps I can help to work something out.

I am a little puzzled by one part of your post, perhaps you can clarify. As I understand it, a cuboid is a six sided figure in 3D space. So it is not clear to me how a three dimensional figure can be defined by two points in 3D space. Last time I checked. two points determine a line. I guess I am missing your point somehow.
cd wei
Greenhorn

Joined: Oct 07, 2009
Posts: 1
cs1101 right??
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38449
    
  23
Welcome to the Ranch cd wei

No, I don't think it is a "101" subject; it involves some complex maths working out the orientation and sizes of the two cubes.
liu hao
Greenhorn

Joined: Oct 02, 2009
Posts: 9
Fred Hamilton wrote:I don't have an answer off the top of my head, but I find the question interesting, so perhaps I can help to work something out.

I am a little puzzled by one part of your post, perhaps you can clarify. As I understand it, a cuboid is a six sided figure in 3D space. So it is not clear to me how a three dimensional figure can be defined by two points in 3D space. Last time I checked. two points determine a line. I guess I am missing your point somehow.

the cuboids are parallel to the X-Y plane, so the two points are actually two diagonal vertices.
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
if it is then, you find the overlap along x and Y axis, that will give you the 2D overlap, now find which one is shorter along Z axis. That will give the 3rd dimension of the overlapped cuboid.
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
Rahul.p Kumar wrote:if it is then, you find the overlap along x and Y axis, that will give you the 2D overlap, now find which one is shorter along Z axis. That will give the 3rd dimension of the overlapped cuboid.

There is one correction above. cuboids may be not even touching along z axis, ok so you need to find the depth of overlap along z axis, that will give you the 3rd dimension of overlapped cuboid
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
liu hao wrote:
Fred Hamilton wrote:I don't have an answer off the top of my head, but I find the question interesting, so perhaps I can help to work something out.

I am a little puzzled by one part of your post, perhaps you can clarify. As I understand it, a cuboid is a six sided figure in 3D space. So it is not clear to me how a three dimensional figure can be defined by two points in 3D space. Last time I checked. two points determine a line. I guess I am missing your point somehow.

the cuboids are parallel to the X-Y plane, so the two points are actually two diagonal vertices.


ok yeah, you did allude to that in your first post.

Still... to me two diagonal vertices for each shape is sufficient information only if we are dealing with cubes, which as I see it is a narrower definition of a shape than cuboid. Do we agree?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3012
    
  10
If Liu Hao means that all sides of the "cuboid" are parallel to either the XY, XZ, or YZ planes, then two diagonal points have exactly enough information - and the problem is much easier than most here have been envisioning.

If a cuboid is defined by points (1,2,3) and (3,7,10) then its surfaces are:

x = 1, x= 3
y = 2, y = 7
z = 3, z = 10

And when comparing two different cuboids, you just need to check that [the x coordinates of both cuboids overlap] AND [the y coordinates of both cuboids overlap] AND [the z coordinates of both cuboids overlap].
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
OK Mike, that makes sense, to a point. But if we restrict the definition of a cuboid to that where the meetings of the faces are all right angles, then I would suggest that your definition is too restrictive, no? it should be that at least one pair of opposing faces is parallel to one of the xy, xz, or yz planes. agreed?

regards
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3012
    
  10
Well, if we take your interpretation, then I agree that we don't have enough information to solve the problem. But if we take my interpretation, we do.

liu hao wrote:the cuboid is specified by two vertex which are Point3D objects meaning that they are parallel to the axises.

This isn't really clear - but apparently something is parallel to the axes. A vertex is just a point; it can't be parallel to anything. But the edges can certainly be parallel to the axes. The original post says nothing special about the X axis as opposed to the Y or Z axis, so I assume they're all equally involved. It's not until later that the XY plane is mentioned , still in an unclear manner. I suspect it's just an oversight that the other planes weren't mentioned at the same time.

But really, there's no way for us to know unless the original poster posts again, to clarify.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
Mike Simmons wrote:Well, if we take your interpretation, then I agree that we don't have enough information to solve the problem.

...


OK, well there is no agreement then, one of us is wrong. As I see it the only way to prove the point is a counter example to my claim, i.e. two different cuboids that satisfy my criteria, at which point I will have no choice but to stand corrected.


edit: and I think I have the example. I do believe that without your restrictions, we can simpley rotate the cuboid around the line connecting the two vertices.

.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3012
    
  10
I don't even know where to begin with that. We seem to be posting in two unrelated threads accidentally occupying the same time and space.

Anyway, if the original poster wants to post something to tell us what the heck he/she really meant, that would be great.
liu hao
Greenhorn

Joined: Oct 02, 2009
Posts: 9
sorry for that I cannot reply in time as I have lectures and still lots of assignments.

Mike Simmons's interpretation is exactly what I mean. sorry for this vagueness, but the it's the description of original problem.
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
Mike Simmons wrote:I don't even know where to begin with that. We seem to be posting in two unrelated threads accidentally occupying the same time and space.

Anyway, if the original poster wants to post something to tell us what the heck he/she really meant, that would be great.


Oh really. Well I guess you're just too clever for the likes of me then.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: algorithm to compute the common space of two cuboid?