Sign in to follow this  

Using minkowski difference to check for containment

This topic is 2486 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on an implementation of a GJK algorithm and as a preliminary I'm looking for a test that will determine if one shape completely contains another. I know that it will contain the origin for sure, but I don't know if there is a general test that will tell me whether one shape completely contains another or not.

From what I can tell, for two objects A and B, if B contains A, then the difference B-A will intersect with B if B contains A completely. But sometimes the difference will intersect B even when A is not completely contained, as when they are intersecting and B also happens to contain the origin.

Any insights? Thanks.

Share this post


Link to post
Share on other sites
[quote name='DonDickieD' timestamp='1297999859' post='4775684']
There is a nice discussion on the MollyRocket forum about a boolean GJK with a video You can also look at Gino v.d. Bergens book.
[/quote]

Thanks this is what I was looking at initially. I think the answer is that if you check every point in the object as an isolated case and they all are contained, then by induction the whole thing is contained. I was just wondering if there was another property of the minkowski difference or sum that allowed you avoid the brute force approach.

Share this post


Link to post
Share on other sites
[quote]From what I can tell, for two objects A and B, if B contains A, then the difference B-A will intersect with B if B contains A completely. But sometimes the difference will intersect B even when A is not completely contained, as when they are intersecting and B also happens to contain the origin.[/quote]

Minkowski difference A - B means you subratct [b]all [/b]points in B from [b]all [/b]points in A. If A and B overlap they must share equal points. Therefore A - B must contain the origin. This is actual trivial and no rocket science.

Share this post


Link to post
Share on other sites
[quote name='DonDickieD' timestamp='1298036669' post='4775852']
[quote]From what I can tell, for two objects A and B, if B contains A, then the difference B-A will intersect with B if B contains A completely. But sometimes the difference will intersect B even when A is not completely contained, as when they are intersecting and B also happens to contain the origin.[/quote]

Minkowski difference A - B means you subratct [b]all [/b]points in B from [b]all [/b]points in A. If A and B overlap they must share equal points. Therefore A - B must contain the origin. This is actual trivial and no rocket science.
[/quote]

I think the OP is asking about containment, not overlap/penetration -- does the minksum have any properties which would make it easy to detect/infer containment using only a few tests rather than testing all vertices of each object against the other.

Share this post


Link to post
Share on other sites
[quote name='raigan' timestamp='1298135835' post='4776351']
[quote name='DonDickieD' timestamp='1298036669' post='4775852']
[quote]From what I can tell, for two objects A and B, if B contains A, then the difference B-A will intersect with B if B contains A completely. But sometimes the difference will intersect B even when A is not completely contained, as when they are intersecting and B also happens to contain the origin.[/quote]

Minkowski difference A - B means you subratct [b]all [/b]points in B from [b]all [/b]points in A. If A and B overlap they must share equal points. Therefore A - B must contain the origin. This is actual trivial and no rocket science.
[/quote]

I think the OP is asking about containment, not overlap/penetration -- does the minksum have any properties which would make it easy to detect/infer containment using only a few tests rather than testing all vertices of each object against the other.
[/quote]

Yes, this is what I am asking: not overlap, but rather containment. Thanks.

Share this post


Link to post
Share on other sites

This topic is 2486 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this