Need a way of computing the vertices of intersection of two simplices

288 Views Asked by At

I have two simplices $\Delta_1, \Delta_2$ defined as:

The first simplex, $\Delta_1$, is the set of points defined as follows:

$$\Delta_1 = \left\{\sum\theta_iu_i, \theta_i >= 0, \sum\theta_i=1, i = 0,1,2,3\right\}$$

$$u_0=\left(0,0,0\right)\hspace{10pt} u_1=\left(a,b,c\right)\hspace{10pt} u_2=\left(2\cfrac{a-c}{2-c},2\cfrac{b-c}{2-c},0\right)\hspace{10pt} u_3=\left(2\cfrac{a-b}{2-b},0,0\right)$$

The $u_i$'s are the vertices of the simplex which is a tetrahedron (3D geometry). I have written the simplex as the convex hull of the given vertices.

The second simplex, $\Delta_2$, is defined as follows:

$$\Delta_2 = \left\{\sum\theta_iv_i, \theta_i >= 0, \sum\theta_i=1, i = 0,1,2,3\right\}$$

$$v_0=\left(2,2,2\right)\hspace{10pt} v_1=\left(x,y,z\right)\hspace{10pt} v_2=\left(2, 2\cfrac{y}{x},2\cfrac{z}{x}\right)\hspace{10pt} v_3=\left(2,2,2\cfrac{z}{y}\right)$$

All the vertices are non-negative and less than 2.

The two simplices defined above are a subset of the simplex with vertices $$\left\{(0,0,0), (2,0,0), (2,2,0), (2,2,2)\right\}.$$

I am interested in determining the $V$-presentation of the convex polytope$\Delta_1 \cap \Delta_2$. If you can point me two any reference it would be extremely appreciated. Let me know if any kind of plots are required to further clarify the problem.

The two simplices which are the subset of another simplex look as follows enter image description here

and their intersection enter image description here

2

There are 2 best solutions below

1
On

Unless your tetrahedra are positioned very specially (which I cannot determine without doing some computation on your coordinates myself), it might be best to just intersect each triangle face of one tetrahedron with each face of the other. For this you need triangle-triangle intersection code. This is not difficult, but nor is it straightforward. You could look at CGAL for the high-end (Triangle_3 vs. Triangle_3), or this earlier MSE discussion ("Find whether two triangles intersect or not in 3D") for the idea behind the computation. I believe this is TriTriIntersect in David Eberly's Magic Software.

0
On

You're looking at the problem of vertex enumeration. I would recommend taking a look at LRS

http://cgm.cs.mcgill.ca/~avis/C/lrs.html

as well as the related software listed on that page.