(back to main)

Random points on a spherical cap

A note by Ahmed Fasih 2016/11/19

How do you sample random points in a spherical cap? How do you randomly pick a direction inside a 3D cone, whose tip is at the origin? How do you get randomly latitude–longitude pairs that are within some distance of a given latitude and longitude? These are all one and the same question!

Sampling points on a unit sphere (in three dimensions, centered at the origin with radius 1) is a little tricky: anyone who tried to do this by drawing uniformly random latitudes between ±90° and longitudes between ±180° can be forgiven for it, but this is the wrong way to do it. A glance at the visualizations by MathWorld, D3.js–guru Jason Davies, or Chris Wellons shows that this bunches points near the poles:

The wrong way to sample points on a sphere, via Chris Wellons
You don’t want to see this. Courtesy of Chris Wellons.

Luckily there are many right ways to sample points from the unit sphere (MathWorld has your back). However, Pedro77 needed something a little different when asking their question on StackOverflow: they needed random points on a unit sphere that lay inside a cone, with tip at the origin and oriented in a particular direction, towards some (latitude, longitude) pair on the sphere. They were generating random points on the entire sphere and discarding points that failed to meet this criterion, and wanted to know if there was a better way. Rejection sampling is perfectly correct, but can be inefficient for small angles, when it has to throw away most samples.

I tried intuiting a mathematical solution for a few minutes in vain, then sought to find the name of this cone–sphere intersection—maybe knowing what it’s called would aid searching. Google quickly sent me to Mathworld’s “Spherical Cap” entry. A picture is worth a thousand words:

Spherical cap, via Mathworld
A spherical cap, ladies and gentlemen.

Knowing what to search for, in this case, meant all the world. Between Jim Belk and joriki’s fine answers on—where else—Math.StackExchange (StackOverflow’s sister site for mathematicians), the problem reduced to converting mathematical pseudocode to Matlab code. My answer as well as my personal Matlab toolkit (GitHub), contains that public-domain Matlab code.

I wanted you, kind reader, to visualize spherical caps just as you are, since you are likely reading these words on a programmable device in a programmable browser, so I wound up making the sphere-cap-random project, an ES2015 JavaScript module to sample from arbitrary spherical caps:

Three spherical caps. Without WebGL, you will see nothing above—click here for an animated GIF.

The interactive 3D scatter plot above, courtesy of plotly.js, shows random samples from three spherical caps:

I have the same demo in a bl.ock (bl.ocks.org is Mike Bostock’s beautiful HTML/JavaScript playground).

It was very pleasant to use bl.ocks for the first time. It was unpleasant but educational to write an ES2015 module with Rollup and Babel—ClojureScript and the Google Closure Compiler shielded me from all that, so I felt like a real 2016 Web Developer:

Exasperated cat
A ClojureScript developer does an ES2015 module with Rollup.

But the most fun part of the little exercise was scijs written by Mikola Lysenko and Ricky Reusser and friends. It’s a high-performance ecosystem for JavaScript numerics with some very powerful abstractions but also very little syntactic sugar. This last sentence included a number of clauses that one usually doesn’t find together. Working with scijs was fun but challenging. For a taste of coding in it, see the source code for sphere-cap-random.

Links