math & physics
nestor at October 4th, 2005 08:11 — #1
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.
oisyn at October 4th, 2005 12:10 — #2
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.
sigkill at October 5th, 2005 08:42 — #3
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)...
corey at October 7th, 2005 16:25 — #4
You might find some research or articles on Minkowski addition interesting for convex shape sums.