Intersecting hull

71c453205fbe34dec433416522300c3f
0
nestor 101 Oct 04, 2005 at 12:11

I need to calculate the common hull which is shared by two intersecting convex hulls.
Is there any open-source libraries that would do this?
Or a paper explaining how to do this?

I have googled the net but nothing came up.

3 Replies

Please log in or register to post a reply.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 04, 2005 at 16:10

What exactly do you mean with “common hull”. Do you mean just the intersection (e.g. boolean ‘and’) of the two convex hulls?

That should be fairly easy using some good old CSG algorithms :). Just take the set of planes that define the convex hull for object A, and use them to cut away pieces from object B. You end up with the intersection of both objects.

4e70f904a74bd2aa8773733b25b77d41
0
SigKILL 101 Oct 05, 2005 at 12:42

The simplest method to explain is simply to create a new convex hull generated by the all the planes in the to original hulls (Like if C is the intersection of B and A, C can be generated by the union of planes that generate A and B). Some of the planes might be redundant and should be removed (if you’re triangulating the convex hull you will detect them automatically there)…

-si

F6ad85487ec271d99a0ef7a4e1b426d6
0
corey 101 Oct 07, 2005 at 20:25

You might find some research or articles on Minkowski addition interesting for convex shape sums.

corey