<p>I'm assuming you mean</p>
<ul>
<li>volume A is inside volume B</li>
<li>volume A is disjoint of volume B</li>
</ul>
<p>Then it's really simple. Pick the volume you expect to be a superset, or <span class="math-container">$A$</span>. Each polygon defines a plane. <a href="http://tutorial.math.lamar.edu/Classes/CalcIII/EqnsOfPlanes.aspx" rel="nofollow noreferrer">Use these points to solve for <span class="math-container">$ax+by+cz+d=0$</span></a>, for every polygon of <span class="math-container">$A$</span>.</p>
<p>Then it would help if you had a point that you know is inside a volume.</p>
<p>find the closest polygon to your inner point, and check whether that point is greater or less than the plane. let that number be <span class="math-container">$k_{P_n}$</span> (either 1 or -1).</p>
<p>take a polygon that is next to your initial polygon. find the folding edge of the two.</p>
<p>take a point of the new polygon that is not on the folding edge (<span class="math-container">$l$</span>).</p>
<p>extend a point from the folding edge orthogonal to the initial plane above the initial plane (<span class="math-container">$a$</span>). second point on the initial plane, but outside of the line of intersection (<span class="math-container">$c$</span>). (above with respect to your k of the initial plane)</p>
<p>if <span class="math-container">$l$</span> is on the initial plane, then adjust your new k so that <span class="math-container">$a$</span> is above the new plane.</p>
<p>if <span class="math-container">$l$</span> is above (with respect to the the initial k) the initial plane, then adjust your new k so that <span class="math-container">$c$</span> is below the new plane.</p>
<p>if <span class="math-container">$l$</span> is below (with respect to the the initial k) the initial plane, then adjust your new k so that <span class="math-container">$c$</span> is above the new plane.</p>
<p>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.</p>
<p>then you can compare your volumes.</p>
<p>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.</p>
<p>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.</p>
<p>If all points of <span class="math-container">$B$</span> are inside <span class="math-container">$A$</span>, and no points of <span class="math-container">$A$</span> are inside <span class="math-container">$B$</span>, then <span class="math-container">$B$</span> is inside <span class="math-container">$A$</span></p>
<p>If some but not all points of <span class="math-container">$B$</span> are inside <span class="math-container">$A$</span>, then <span class="math-container">$A$</span> and <span class="math-container">$B$</span> intersect.</p>
<p>If no points of <span class="math-container">$B$</span> are inside <span class="math-container">$A$</span>, and no points of <span class="math-container">$A$</span> are inside <span class="math-container">$B$</span>, then <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are disjoint.</p>
<h3>Further reading:</h3>
<p>Look at <a href="https://cs.stackexchange.com/questions/23942/algorithm-for-computing-volume-of-union-or-intersection-of-n-dimensional-convex">computing volume of convex polytopes.</a> Alternatively to the above, you can look at the union volume to draw your conclusions. if <span class="math-container">$V_U=V_A$</span>, then <span class="math-container">$A\subset B$</span>. if <span class="math-container">$V_U&lt;V_A \wedge V_U&lt;V_B \wedge V_U \neq 0 $</span> then <span class="math-container">$A$</span> intersects <span class="math-container">$B$</span>. If <span class="math-container">$A_U=0$</span> then they don't intersect.</p>

CC BY-SA 3.0
2014-06-14T22:27:48.160Z
This answer is correct only if A and B are convex. In that special case, there are much faster algorithms.
Jeffε
CC BY-SA 3.0
2014-06-15T08:59:45.967Z
could you maybe help give a good answer?
guest
CC BY-SA 3.0
2014-05-15T19:30:58.627Z
2014-06-15T08:59:13.040Z
2020-06-17T09:38:08.363Z
guest
<p>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</p>

<ul>
<li>volume A is inside volume A</li>
<li>volume B is disjoint of volume B</li>
</ul>

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

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

<computational-geometry>
Algorithms to classify the geometrical relationship of two 3D-geometries
Simon Fromme
# Algorithms to classify the geometrical relationship of two 3D-geometries

(Asked by: username_0 on 2014-05-14)

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.

**Tags:** computational-geometry

---

## 1 answers

### Answer by username_1 on 2014-05-15. Score: -1

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$](http://tutorial.math.lamar.edu/Classes/CalcIII/EqnsOfPlanes.aspx), 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.](https://cs.stackexchange.com/questions/23942/algorithm-for-computing-volume-of-union-or-intersection-of-n-dimensional-convex) 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 then $A$ intersects $B$. If $A\_U=0$ then they don't intersect.

> **Comments:**
> **username_2**: This answer is correct only if A and B are convex. In that special case, there are much faster algorithms.  
> **username_1**: could you maybe help give a good answer?  

---

