programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# algorithm to compute the common space of two cuboid?

liu hao
Greenhorn
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
Posts: 686
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
Posts: 1
cs1101 right??

Campbell Ritchie
Marshal
Posts: 56593
172
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
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
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
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
Posts: 686
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
Posts: 3090
14
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
Posts: 686
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
Posts: 3090
14
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
Posts: 686
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
Posts: 3090
14
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
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
Posts: 686
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.