How to determine the 3d shape formed by intersecting planes Question
How can I optimally get the list of vertices for the 3d shape (a convex hull) formed by a set of intersecting planes in 3d space that contains all feasible solutions. Assuming that a 3d shape is formed by the intersection of the planes?
Is there a name for the problem space/algorithm I'm seeking for? My background in this area is not very strong.
Background
I have a list of planes in the form of A, B, C, d that follow the form Ax + By + Cz - d = 0 and I want to determine the list of vertices formed by the intersection of the planes (-d for the sake of implementation details, I don't want the minus sign to be absorbed as part of the constant). Once I have a good solution I want to create a program for it.
Attempt
My intuition tells me that I should determine plane, plane intersection -> line, line intersection -> point, for every plane intersection, but I feel as if this is just the naive/brute force way of doing what I need. Is there perhaps a faster way or a specific algorithm of doing this especially as the number of planes approaches 10, 100, ..., n planes?
reference: How to calculate the intersection of two planes?
My googling so far has led me to think about using Cramer's rule, to help the issue with a more general solution, but it seems rather iterative because I can't just put in all 6 planes in at the same time. At a glance it seems I would have to do some sorting to get the list of planes that intersect with each other. The other thing is that Cramer's rule breaks down a bit and I would have to do a lot of edge case catching to ensure that I can get things working, EX: if I have two planes in 3d space.
reference: https://github.com/guiriosoficial/CramersRule
Plane Data
1, 0, 0, 3.3927
1, 0, 0, -3.5354
0, 1, 0, -1.8034
0, 1, 0, 5.1248
0, 0, 1, 0.8506
0, 0, 1, 2.3506
Visualization of planes
 A: $
\newcommand\R{\mathbb R}
\newcommand\Ext{\mathop\bigwedge}
$I will describe the algebra $\Ext(\R^{3+1})^*$, which works very well for intersecting planes. This is the exterior algebra of the dual space of $\R^{3+1}$; I write $3+1$ because we are projectivizing $\R^3$ by adding a dimension. We will write the standard basis of $(\R^{3+1})^*$ as $e^1, e^2, e^3, \infty$ because the last element will have the interpretation of the plane at infinty. Computationally, there is no difference between using $\R^{3+1}$ and $(\R^{3+1})^*$, but conceptually the latter is preferrable.
Projectivizing
Let $V$ be any finite-dimensional real vector space. Its dual space $V^*$ is also a vector space of the same dimension, and is the set of all linear functions $V \to \R$. To any $\phi \in V^*$ we can naturally associate a plane through the origin
$$
  \ker\phi = \{v \in V \;:\; \phi(v) = 0\}.
$$
We identify $\phi$ as representing this plane. Notice that any point $x \in V$ in a plane parallel to $\phi$ satisfies the $\phi(x) = a$ for some fixed $a$. When $V = \R^3$, the basis $e^1, e^2, e^3 \in (\R^3)^*$ is the dual of the standard basis $e_1, e_2, e_3 \in \R^3$ meaning
$$
  e^i(e_j) = \delta^i_j,\quad i, j = 1, 2, 3.
$$
Now notice the the equation $\phi(x) = a$ can be written
$$
  \phi_1e^1(x) + \phi_2e^2(x) + \phi_3e^3(x) - a = 0
\tag{$*$}
$$
for some $\phi_i \in \R^3$. Formally, we can add a new dimension $\oslash = e_4$ to make $\R^{3+1}$ and form the dual basis of $e_1, e_2, e_3, \oslash$ as $e^1, e^2, e^3, \infty$. We embed $x \in \R^3$ as $x + \oslash \in \R^{3+1}$, where then we can write ($*$) as
$$
  \phi_1e^1(x+\oslash) + \phi_2e^2(x+\oslash) + \phi_3e^3(x+\oslash) - a\infty(x +\oslash) = 0.
$$
Thus we consider the element $\Phi \in (\R^{3+1})^*$
$$
  \Phi = \phi_1e^1 + \phi_2e^2 + \phi_3e^3 - a\infty.
$$
An arbitrary $x + b\oslash \in \R^{3+1}$ can be identified with a point by rescaling to $x/b + \oslash$ when $b\ne0$, in which case $\ker\phi'$ is well-defined:
$$
  \Phi(x + b\oslash) = 0 \iff \Phi(x/b + \oslash) = 0 \iff \phi(x/b) = a.
$$
If $b = 0$ then notice that
$$
  \Phi(x) = 0 \iff \Phi = -a\infty
$$
so we can identify $x$ as a point contained in the plane at infinity.
Thus we have show that elements of $(\R^{3+1})^*$ represent arbitrary planes in $\R^3$, not just those through the origin. In fact, we have shown that a plane defined by the equation
$$
  Ax + By + Cz - d = 0
$$
can be represented by
$$
  Ae^1 + Be^2 + Ce^3 - d\infty \in (\R^{3+1})^*.
$$
The same story repeats in arbitrary $V$, though now we talk about hyperplanes instead of planes.
The Exterior Algebra
The exterior algebra $\Ext V$ is the associative algebra generated by $V$ as a subset subject only to the relations $v\wedge v = 0$ for all $v \in V$; traditionally we use $\wedge$ to write the algebra product. This condition is equivalent to the condition the all vectors anticommute with each other. $\Ext V$ naturally becomes an algebra of subspaces of $V$ due to the following property:
$$
  v_1\wedge\dotsb\wedge v_k = 0 \iff v_1,\dotsc, v_k\text{ are linearly dependent}
$$
where $v_1,\dotsc, v_k \in V$. This makes an element $X = v_1\wedge\dotsb\wedge v_k$, called a $k$-blade, a representation of the following subspace of $V$:
$$
  [X] = \{v \in V \;:\; v\wedge X = 0\}.
$$
Thus we can think of $v_1$ as representing a line through the origin, $v_1\wedge v_2$ the plane through the origin spanned by those vectors, $v_1\wedge v_2\wedge v_3$ a 3D space, etc.
We can just as easily form the exterior algebra $\Ext V^*$ of $V^*$. There is an intimate relation between $\Ext V^*$ and $\Ext V$ given by the existence of the following natural bilinear pairing $\Ext V^*\times\Ext V \to \R$:
$$
  (\phi_1\wedge\dotsb\wedge\phi_k,\; v_1\wedge\dotsb\wedge v_l)
    \mapsto \delta_{kl}\det\Bigl(\phi_i(v_i)\Bigr)_{i,j=1}^k.
$$
Extending this by linearity is enough to define the full pairing. This pairing is zero when $k \ne l$ and otherwise is the determinant of the matrix with entries $\phi_i(v_j)$. Delving into this pairing is too much to get into here, but what we can find is the following: dual to the interpretation of $\Ext V$ as building up subspaces by spanning lines, the algebra $\Ext V^*$ builds subspaces as intersections of (hyper)planes.
Let's return to $V = \R^3$. Elements $\phi_1, \phi_2 \in (\R^3)^*$ are planes through the origin; then $\phi_1\wedge\phi_2$ represents the intersection of those planes, which is a line through the origin. This interpretation does indeed carry over to $\Ext(\R^{3+1})^*$, where elements $\Phi_1, \Phi_2, \Phi_3 \in (\R^{3+1})^*$ are arbitrary planes that need not pass through the origin. $\Phi_1\wedge\Phi_2$ is the line formed by intersecting those planes, and $\Phi_1\wedge\Phi_2\wedge\Phi_3$ is the point of interesection of those three planes.
We should look a little closer at these 3-blades. Since $e^1, e^2, e^3, \infty$ is our basis for $(\R^{3+1})^*$, a basis for the 3-blades is
$$
  \oslash = e^1\wedge e^2\wedge e^3,\quad E^1 =  e^2\wedge e^3\wedge\infty,\quad E^2 = e^3\wedge e^1\wedge\infty,\quad E^3 = e^1\wedge e^2\wedge\infty.
$$
$e^1$ is the $yz$-plane, $e^2$ the $zx$-plane, and $e^3$ the $xy$-plane; it follows easily that $\oslash$ is the origin (and is closely related to the other object we gave this symbol to). We see the remaining basis elements intersect $\infty$; these are ideal points, which we can understood as a representation of pure displacements. You'll find that e.g.
$$
  \oslash + E^1
$$
is exactly the point 1 unit away from $\oslash$ in the $x$-direction, and more generally
$$
  \oslash + xE^1 + yE^2 + zE^3
$$
is exactly the point $(x, y, z) \in \R^3$.
Intersecting Three Planes
We are now able to answer the question in full. Given three planes
$$
  A_1x + B_1y + C_1z - d_1 = 0,\quad
  A_2x + B_2y + C_2z - d_2 = 0,\quad
  A_3x + B_3y + C_3z - d_3 = 0,
$$
We represent these as elements $\Phi_i \in (\R^{3+1})^*$ via
$$
  \Phi_i = A_ie^1 + B_ie^2 + C_ie^3 - d_i\infty.
$$
We then calculate
$$
  P = \Phi_1\wedge\Phi_2\wedge\Phi_3 = a\oslash + XE_1 + YE_2 + ZE_3.
$$
If $P = 0$ then

*

*Two of these planes are identical, or

*All three are parallel, or

*All three intersect in the same line.

If $P \ne 0$ but $a = 0$ then two of these planes intersect in a line which the third is parallel to. In this case $(X, Y, Z)$ is the direction of the line.
If $a\ne0$, then $(X/a, Y/a, Z/a)$ is the point of intersection of the three planes $\Phi_1, \Phi_2, \Phi_3$.
At this point, you can either work out $P$ by hand (which isn't too difficult, but is tedious) or implement the exterior algebra on a computer and make it do the calculation.
