0
$\begingroup$

I want to calculate the intersection volume of a rectangular prism and a cuboid. There are not any constraint on cuboid and the rectangular prism. I thought of solving it with some sort of numerical integration or break it to many triple integration over different regions which have analytical solution. but none of these would be computationally efficient, and i need an efficient way because it must be repeated many many times for different cuboids and prisms.

So I was wondering is there any analytical solution to this problem. Finite Element Modelling software do this kind of calculations all the time (finding the intersection and calculating its volume). I would be happy if anyone could suggest a reference or textbook on the subject.

For 2D case (intersection area between a rectangle and 2 arbitrary line) I found the intersection points, then calculate the area of convex polygon (using shoelace algorithm which simply breaks the polygon to many triangles and sum the area of triangles). In the picture the red dots define the intersection polygon.

2D analog

$\endgroup$
7
  • $\begingroup$ Explain what you call "rectangular prism" : what is its base, are its side orthogonal to the base, and also, how you define a "cuboid" : is it a "rectangular parallelepiped" ? The 2D analogy is not understandable : how are your lines connected to any polygon ? $\endgroup$ Commented Apr 26, 2023 at 16:17
  • $\begingroup$ The rectangular prism has a rectangular base but it could be oblique. The cuboid is a rectangular cuboid. In 2D analogy, The rectangular prism, would become 2 arbitrary line (parallel or not) and the cuboid would be a rectangle. If the lines cut the rectangle and there was an intersection it would be a polygon and I want the area of that polygon. There are not any other constraint, in other words the prism and the cuboid are parametric. I don't need a parametric solution, but i need a computationally fast solution or algorithm to find the intersection volume when the parameters were fixed. $\endgroup$ Commented Apr 26, 2023 at 17:27
  • $\begingroup$ What data do you know best about the prism? Do you know the vertices and hence the edge vectors, or the inequalities that carve out the faces? (There are two different computational strategies that can be customized to the two cases.) $\endgroup$ Commented Apr 27, 2023 at 0:10
  • $\begingroup$ I have the vertices coordinates at hand, but I could calculate equation of the planes. $\endgroup$ Commented Apr 27, 2023 at 9:19
  • $\begingroup$ Finite Element Modelling software do this kind of calculations all the time (finding the intersection and calculating its volume). I would be happy if anyone could suggest a reference or textbook on the subject. $\endgroup$ Commented Apr 27, 2023 at 9:25

1 Answer 1

Reset to default
1
$\begingroup$

The method I would advise is to convert each polyhedron into a set of inequalities :

  • 6 inequalities for the parallelepiped $C$, for example, if the length, width and height are resp $\ell,w,h$ :

$$x \ge 0,x \le \ell, y \ge 0,y \le w, z\ge 0,z \le h \tag{1}$$

  • 6 others for the prism $P$.

Then generat $10^n$ (uniform) random points in the parallelepiped (which is easy under the form (1)) and increment a counter $k$ (initialized to $0$ of course) each time the 6 "other" inequalities are verified.

Finaly, the proportion $k/10^n$ is roughly equal to the ratio of volumes $\text{Vol}(C \cap P)/\text{Vol(C)}$ and you know $\text{Vol(C)}$...

$\endgroup$
2
  • $\begingroup$ Thank you, rather than this Monte Carlo method, is there any way? like 2D analog. $\endgroup$ Commented Apr 26, 2023 at 19:34
  • 1
    $\begingroup$ Yes, as it is polyhedra, their intersection is a polyhedron that you can "tetraedrize" (2D equivalent : triangularization of a polygon), and the volume of a tetrahedra $ABCD$ is $\frac16 \det(\vec{AB},\vec{AC},\vec{AD})$. But the difficulty is to find the vertices... $\endgroup$ Commented Apr 26, 2023 at 20:54

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.