0
$\begingroup$

I have multiple 3D volumes which are represented by their boundaries (set of polygons each represented as a list of 3D-coordinates). I am now looking for algorithms to decide if

  • volume A is inside volume A
  • volume B is disjoint of volume B

Also I am interested in the dimension of the intersection of A and B if they aren't disjoint.

Specific ideas for algorithms would be just as helpful as references to useful books or papers.

$\endgroup$
-1
$\begingroup$

I'm assuming you mean

  • volume A is inside volume B
  • volume A is disjoint of volume B

Then it's really simple. Pick the volume you expect to be a superset, or $A$. Each polygon defines a plane. Use these points to solve for $ax+by+cz+d=0$, for every polygon of $A$.

Then it would help if you had a point that you know is inside a volume.

find the closest polygon to your inner point, and check whether that point is greater or less than the plane. let that number be $k_{P_n}$ (either 1 or -1).

take a polygon that is next to your initial polygon. find the folding edge of the two.

take a point of the new polygon that is not on the folding edge ($l$).

extend a point from the folding edge orthogonal to the initial plane above the initial plane ($a$). second point on the initial plane, but outside of the line of intersection ($c$). (above with respect to your k of the initial plane)

if $l$ is on the initial plane, then adjust your new k so that $a$ is above the new plane.

if $l$ is above (with respect to the the initial k) the initial plane, then adjust your new k so that $c$ is below the new plane.

if $l$ is below (with respect to the the initial k) the initial plane, then adjust your new k so that $c$ is above the new plane.

keep doing that until you have your complete shell mapped for k. if you have more than one shell (like a hollow object) you need to track all unmapped polygons and do the same thing for them.

then you can compare your volumes.

take any point from B, and find the closest polygon from A, and check whether your B point is above the plane of the A polygon. do this for every point in B.

you also need to check whether any A point is in B, for the special case in which a sharp spike from one volume penetrates the other.

If all points of $B$ are inside $A$, and no points of $A$ are inside $B$, then $B$ is inside $A$

If some but not all points of $B$ are inside $A$, then $A$ and $B$ intersect.

If no points of $B$ are inside $A$, and no points of $A$ are inside $B$, then $A$ and $B$ are disjoint.

Further reading:

Look at computing volume of convex polytopes. Alternatively to the above, you can look at the union volume to draw your conclusions. if $V_U=V_A$, then $A\subset B$. if $V_U<V_A \wedge V_U<V_B \wedge V_U \neq 0 $ then $A$ intersects $B$. If $A_U=0$ then they don't intersect.

$\endgroup$
2
  • 1
    $\begingroup$ This answer is correct only if A and B are convex. In that special case, there are much faster algorithms. $\endgroup$ – Jeffε Jun 14 '14 at 22:27
  • $\begingroup$ could you maybe help give a good answer? $\endgroup$ – guest Jun 15 '14 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.