Procedure to check whether two hemispheres intersect

Question

Suppose I have two hemispheres with centers $c_1$ and $c_2$ whose orientations are defined by vectors normal to their bases, $v_1$ and $v_2$. Also suppose these hemispheres have the same radius $r$. I just want to know whether these two hemispheres intersect - I'm not necessarily interested in the intersection volume. I believe I can solve this problem when $v_1$ and $v_2$ are coplanar (so basically, solving whether two semicircles intersect) but the general 3D case is stumping me a bit.

I am not a mathematician, but I am a scientist, and I am trying to implement this computationally.

Answer 1

tl; dr: Suppose the spheres have centers $c_{1}$ and $c_{2}$, radii $R$ (to reserve the letter $r$ for elsewhere), and the hemispheres are defined by unit normals $v_{1}$ and $v_{2}$. I'll assume intersect does not include touching at one point or touching along the boundary; in other words, the open hemispheres intersect. (To permit intersections of the closed hemispheres, a comparable analysis works, but it's necessary to go through step by step and modify accordingly.)

• If $2R \leq 2d = |c_{2} - c_{1}|$, the hemispheres do not intersect. (Separation is too great.)
• Otherwise, let $\theta = \arccos\frac{d}{R}$, $\phi_{1} = \arccos\frac{v_{1} \cdot(c_{2} - c_{1})}{2d}$, and $\phi_{2} = \arccos\frac{v_{2} \cdot(c_{1} - c_{2})}{2d}$. If $\frac{\pi}{2} + \theta \leq \phi_{1}$ or $\frac{\pi}{2} + \theta \leq \phi_{2}$, the hemispheres do not intersect. (At least one hemisphere does not intersect the circle $C$ where the spheres intersect; that is, at least one hemisphere does not even intersect the other sphere.)
• Otherwise, if $\phi_{1} \leq \frac{\pi}{2} - \theta$ or $\phi_{2} \leq \frac{\pi}{2} - \theta$, the hemispheres do intersect. (Both hemispheres intersect $C$, and at least one contains $C$.)
• Otherwise, set $r = \sqrt{R^{2} = d^{2}}$, the radius of $C$. Compute the components $u_{1}$ and $u_{2}$ of the vectors $v_{1}$ and $v_{2}$ orthogonal to the axis $c_{2} - c_{1}$ (by subtracting the component along the $x$-axis), and the angle $0 \leq \psi \leq \pi$ between $u_{1}$ and $u_{2}$. Compute the subtended angles $\psi_{1} = \arccos \frac{-d\cot\phi_{1}}{r}$ and $\psi_{2} = \arccos \frac{-d\cot\phi_{2}}{r}$. The hemispheres intersect if and only if $\psi < \psi_{1} + \psi_{2}$. (The "combined angle" of the two arcs is greater than the angular separation of their centers.)

Notation and justifications follow.

---

As noted in the comments, the first necessary condition is $|c_{2} - c_{1}| < 2R$: the centers are closer than twice the radius. If the centers coincide, the spheres are identical and the hemispheres intersect if and only if $v_{1} \neq -v_{2}$. Setting aside this edge case, the centers are distinct; let $d$ denote half the distance between the centers, so $|c_{2} - c_{1}| = 2d$. The perpendicular bisector of the segment $\overline{c_{1}c_{2}}$ is a plane $P$ at distance $d$ from each center, and the spheres intersect along the circle $C$ lying in $P$ with center $\frac{1}{2}(c_{1} + c_{2})$ and radius $r := \sqrt{R^{2} - d^{2}}$.

It's convenient to work relative to a Cartesian coordinate system whose origin is at the midpoint $O = \frac{1}{2}(c_{1} + c_{2})$ of the centers, and such that the centers are $c_{1} = (-d, 0, 0)$ and $c_{2} = (d, 0, 0)$. The plane $P$ has equation $x = 0$.

Lemma 1: Write $\theta = \arccos\frac{d}{R}$. Suppose $v_{1}$ makes angle $\phi_{1}$ with $c_{2} - c_{1}$, i.e., $\phi_{1} = \arccos(\frac{v_{1} \cdot (c_{2} - c_{1})}{2d}$. The half-space $H_{1}$ intersects $C$ if and only if $\phi_{1} < \frac{\pi}{2} + \theta$.

Proof: Fix a plane containing the $x$-axis and parallel to $v_{1}$. The dashed green rays through $c_{1}$ making angle $\theta$ with the $x$-axis hit the circle of intersection $C$. The "extreme" normal vectors of hemispheres intersecting $C$ are shown. We deduce $H_{1} \cap C$ is non-empty if and only if $\phi_{1} < \frac{\pi}{2} + \theta$.

Lemma 2: With the preceding notation, if $\phi_{1} \leq \frac{\pi}{2} - \theta$, then $C \subset H_{1}$, i.e., the hemisphere contains the entire circle of intersection. If instead $\frac{\pi}{2} - \theta < \phi_{1} < \frac{\pi}{2} + \theta$, then $H_{1} \cap C$ is an arc of $C$ with midpoint parallel to the the orthogonal projection of $v_{1}$ on $P$, and whose subtended angle measured from the center of $C$ is $\psi_{1} = \arccos \frac{-d\cot\phi_{1}}{r}$.

Proof: In the coordinates above, we have $v_{1} = (\cos\phi_{1}, \sin\phi_{1}, 0)$ with $0 \leq \phi_{1} \leq \pi$. The open half-space $H_{1}$ is the set of triples $(x, y, z)$ satisfying $$ 0 < (x + d)\cos\phi_{1} + y\sin\phi_{1}, $$ and the boundary plane satisfies $0 = (x + d)\cos\phi_{1} + y\sin\phi_{1}$. Points $(x, y, z)$ on the circle $C$ satisfy $x = 0$ and $y^{2} + z^{2} = r^{2}$. If $\phi_{1} \leq \pi/2 - \theta$, the hemisphere completely contains $C$. If instead $\pi/2 - \theta < \phi_{1} < \pi/2 + \theta$, the boundary plane cuts $C$ in the $(y, z)$-plane at the two solutions of the system $$ 0 = d\cos\phi_{1} + y\sin\phi_{1},\qquad y^{2} + z^{2} = r^{2}. $$ The first gives $y = -d\cot\phi_{1}$, from which the second gives $$ z = \pm\sqrt{r^{2} - d^{2}\cot^{2}\phi_{1}} = \pm\sqrt{R^{2} - d^{2}\csc^{2}\phi_{1}}. $$ The intersection is the arc of circle centered on $(0, r, 0)$ and having endpoints $(0, y, z$); the half-angle subtended by this arc is $$ \psi_{1} = \frac{ry}{r^{2}} = \arccos \frac{-d\cot\phi_{1}}{r}. $$

---

To reiterate, we are now set up to determine whether the hemispheres intersect.

• If $2R \leq 2d = |c_{2} - c_{1}|$, the hemispheres do not intersect. (Separation is too great.)
• Otherwise, let $\theta = \arccos\frac{d}{R}$, $\phi_{1} = \arccos\frac{v_{1} \cdot(c_{2} - c_{1})}{2d}$, and $\phi_{2} = \arccos\frac{v_{2} \cdot(c_{1} - c_{2})}{2d}$. If $\frac{\pi}{2} + \theta \leq \phi_{1}$ or $\frac{\pi}{2} + \theta \leq \phi_{2}$, the hemispheres do not intersect. (At least one hemisphere does not even intersect the other sphere.)
• Otherwise, if $\phi_{1} \leq \frac{\pi}{2} - \theta$ or $\phi_{2} \leq \frac{\pi}{2} - \theta$, the hemispheres do intersect. (Both hemispheres intersect $C$, and at least one contains $C$.)
• Otherwise, compute the components $u_{1}$ and $u_{2}$ of the vectors $v_{1}$ and $v_{2}$ orthogonal to the axis $c_{2} - c_{1}$, and the angle $0 \leq \psi \leq \pi$ between $u_{1}$ and $u_{2}$. Compute the subtended angles $\psi_{1} = \arccos \frac{-d\cot\phi_{1}}{r}$ and $\psi_{2} = \arccos \frac{-d\cot\phi_{2}}{r}$. The hemispheres intersect if and only if $\psi < \psi_{1} + \psi_{2}$. (The "combined angle" of the two arcs is greater than the angular separation of their centers.)

Answer 2

I have an idea. I have used something similar recently to find out where two cylinders intersect.

Find the point on the surface of the hemisphere that is closest to the center of the other hemisphere. There are two possible solutions for this.

Either a point on the sphere where the two centers connect. Or a point on the diameter circle defined by where the circle intersects the plane connecting the two centers and has the direction vector lying on it.

Once the closest point is found within a radius from the other hemisphere's center, the two objects might intersect. Swap the two objects and repeat the above to find out if an intersection exists as both points have to be within range.

Here is an example where the objects do not intersect. I color-coded them blue and red for convenience.

• Point $\vec{p}_1$ lies on the sphere is a located a radius $r$ from the center of the first sphere towards the second sphere

  $$ \vec{p}_1 = \vec{c}_1 + r\; {\rm unit}( \vec{c}_2 - \vec{c}_1 ) $$

  where ${\rm unit}(\vec{a}) = \vec{a} / \| \vec{a} \|$ produces a unit vector.

• Point $\vec{p}_2$ lies on the diameter circle of the second hemisphere and it is the closest point of the circle to the first hemisphere center.

  This point lies on a plane with normal vector $$\vec{n} = {\rm unit}( \vec{v}_2 \times (\vec{c}_1 - \vec{c}_2))$$ that goes through the center of the second object

  The point is found by

  $$ \vec{p}_2 = \vec{c}_2 + r \; (\vec{n} \times \vec{v}_2)$$

• The final check for interference when both conditions below are satisfied

  $$ \| \vec{p}_1 - \vec{c}_2 \| \le r $$ $$ \| \vec{p}_2 - \vec{c}_1 \| \le r $$

---

Here is my un-tested C# code

public readonly struct Hemisphere
{
    public Hemisphere(float radius, Vector3 center, Vector3 direction) : this()
    {
        Radius = radius;
        Center = center;
        Direction = Vector3.Normalize(direction);
    }

    public float Radius { get; }
    public Vector3 Center { get; }
    public Vector3 Direction { get; }

    public Vector3 GetPointClosestTo(Vector3 target)
    {
        if (Vector3.Dot(Direction, target - Center) < 0)
        {
            Vector3 n = Vector3.Cross(Direction, target - Center);
            // only one point on the dia. circle is closest to the target
            n = Vector3.Normalize(n);
            return Center + Radius * Vector3.Cross(n, Direction);
        }
        else
        {
            // hemisphere directed towards target, so closest point
            // is on the sphere surface.
            return Center + Radius * Vector3.Normalize(target - Center);
        }
    }


    public static bool Intersect(Hemisphere h_1, Hemisphere h_2)
    {
        Vector3 p_1 = h_1.GetPointClosestTo(h_2.Center);
        Vector3 p_2 = h_2.GetPointClosestTo(h_1.Center);

        float d_12 = Vector3.Distance(p_1, h_2.Center);
        float d_21 = Vector3.Distance(p_2, h_1.Center);
        return d_12 <= h_2.Radius && d_21 <= h_1.Radius;
    }
}

---

I am doing some testing with CAD and so far the numbers match

and the test code that corresponds to this scenario

    [TestMethod()]
    public void GetPointClosestToTest4()
    {
        // Separate two unit hemispheres by 0.8 units distance. 
        // First one is just pointing along the y-axis.
        // The first one is going to point away by 40 degrees
        // The second one is pointing along the z-axis
        var rot = Matrix4x4.CreateFromAxisAngle(Vector3.UnitZ, 40 * deg);
        var h_1 = new Hemisphere(1f, -0.8f * Vector3.UnitX, Vector3.Transform(Vector3.UnitY, rot));
        Debug.WriteLine(h_1);


        var h_2 = new Hemisphere(1f, 0.8f * Vector3.UnitX, Vector3.UnitZ);
        Debug.WriteLine(h_2);

        var p_1 = h_1.GetPointClosestTo(h_2.Center);
        var p_2 = h_2.GetPointClosestTo(h_1.Center);

        Debug.WriteLine($"Point1: {p_1}");
        Debug.WriteLine($"Point2: {p_2}");

        Assert.IsTrue(Vector3.Distance(new Vector3(-0.03395557f, 0.6427876f,0), p_1) <= tol);
        Assert.IsTrue(Vector3.Distance(-0.2f * Vector3.UnitX, p_2) < tol);
        // Values verified with CAD

        Assert.IsFalse(Hemisphere.Intersect(h_1, h_2));
    }

As you can see the coordinates of p_1 correspond to the CAD image. The program is in meters, and the CAD is millimeters for more decimal points displayed.

Coord	C# [m]	CAD [mm]	Delta [m]
X	0.03395557	33.955557	1.3e-8
Y	0.6427876	642.78761	1.0e-8