# Using minkowski difference to check for containment

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

## 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 on other sites
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.

##### Share on other sites

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.

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 on other sites
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 all points in B from all 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 on other sites

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.

Minkowski difference A - B means you subratct all points in B from all 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 on other sites

[quote name='DonDickieD' timestamp='1298036669' post='4775852']
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.

Minkowski difference A - B means you subratct all points in B from all 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.

1. 1
2. 2
3. 3
Rutin
18
4. 4
JoeJ
12
5. 5

• 14
• 9
• 22
• 9
• 31
• ### Forum Statistics

• Total Topics
632618
• Total Posts
3007485
• ### Who's Online (See full list)

There are no registered users currently online

×