The objective is to compute the minimum enclosing circle on Earth (considered as a sphere), given any number of GPS coordinates. It determines the center, the radius in meters, and checks if all input points are contained. The solution is based on a 3D spherical adaptation of the Shamos-Hoey algorithm.
To project a GPS point \( (\phi, \lambda) \) (latitude, longitude in degrees) on the unit sphere:
\[ x = \cos(\phi) \cdot \cos(\lambda), \quad y = \cos(\phi) \cdot \sin(\lambda), \quad z = \sin(\phi) \]
For 3 unit vectors \( \vec{A}, \vec{B}, \vec{C} \), compute the normal to the plane defined by them: \[ \vec{n} = \frac{(\vec{B} - \vec{A}) \times (\vec{C} - \vec{A})}{\|\cdot\|} \] Then normalize \( \vec{n} \). The center of the spherical circle is: \[ \vec{O} = \pm \vec{n} \quad (\text{sign chosen to face the input points}) \]
The angle between the center \( \vec{O} \) and a boundary point (e.g., \( \vec{A} \)) gives the radius (in radians): \[ r = \cos^{-1}(\vec{O} \cdot \vec{A}) \]
Then converted to meters using haversine distance:
\[ d = 2R \cdot \arcsin\left(\sqrt{\sin^2\left(\frac{\Delta \phi}{2}\right) + \cos(\phi_1) \cos(\phi_2) \sin^2\left(\frac{\Delta \lambda}{2}\right)}\right) \]
with \( R = 6371 \) km (mean Earth radius).
Only points from the 2D-projected convex hull are tested (the fewest points tested the fastest). We use a tangent plane projection followed by a monotone chain algorithm:
\[ \text{cross2D}(O, A, B) = (A_x - O_x)(B_y - O_y) - (A_y - O_y)(B_x - O_x) \]
In the original 2D algorithm:
In our 3D adaptation:
For each candidate center \( \vec{O} \) and radius \( r \), we check: \[ \forall \vec{P},\ \angle(\vec{O}, \vec{P}) \leq r + \varepsilon \]