Fast Great-Circle Distance Calculation in CUDA C++ | NVIDIA Technical Blog
Technical Blog
Subscribe
Related Resources
Simulation / Modeling / Design
GPU Pro Tip: Fast Great-Circle Distance Calculation in CUDA C++
Jun 29, 2015
By Mark Harris
Like
Discuss (0)
AI-Generated Summary
Like
Dislike
The Haversine formula is used to calculate the great-circle distance between two points on a sphere, such as the Earth, and is implemented in a C function called haversine().<br>The haversine() function takes the latitude and longitude of two points and the Earth's radius as input, and returns the distance between the two points in the same units as the radius.<br>The function utilizes CUDA's sinpi() and cospi() functions, specifically sinpif() and cospif(), to improve the accuracy of the calculation.
AI-generated content may summarize information incompletely. Verify important information. Learn more
This post demonstrates the practical utility of CUDA’s sinpi() and cospi() functions in the context of distance calculations on earth. With the advent of location-aware and geospatial applications and geographical information systems (GIS), these distance computations have become commonplace.
A great circle divides a sphere into two hemispheres. Source: Wikimedia Commons
Wikipedia defines a great circle as
A great circle, also known as an orthodrome or Riemannian circle, of a sphere is the intersection of the sphere and a plane which passes through the center point of the sphere.
For almost any pair of points on the surface of a sphere, the shortest (surface) distance between these points is the path along the great circle between them. If you have ever flown from Europe to the west coast of North America and wondered why you passed over Greenland, your flight most likely followed a great circle path in order to conserve fuel.
Following is the code for a C function, haversine(), which computes the great-circle distance of two points on earth (or another sphere), using the Haversine formula. People differ on their philosophy as to the “correct” radius when assuming a spherical earth (given that earth is not a sphere; Wikipedia provides some guidance on this matter). Therefore, the earth’s radius is an input to the function, which also allows trivial switching between kilometers or miles as units. The accuracy of the formula when computed in single-precision should generally be fully adequate for distance computations within a continent.
/* This function computes the great-circle distance of two points on earth<br>using the Haversine formula, assuming spherical shape of the planet. A<br>well-known numerical issue with the formula is reduced accuracy in the<br>case of near antipodal points.
lat1, lon1: latitude and longitude of first point, in degrees [-90, +90]<br>lat2, lon2: latitude and longitude of second point, in degrees [-180, +180]<br>radius: radius of the earth in user-defined units, e.g. 6378.2 km or<br>3963.2 miles
returns: distance of the two points, in the same units as radius
Reference: http://en.wikipedia.org/wiki/Great-circle_distance<br>*/<br>__device__ float haversine (float lat1, float lon1,<br>float lat2, float lon2, float radius)<br>float dlat, dlon, c1, c2, d1, d2, a, c, t;
c1 = cospif (lat1 / 180.0f);<br>c2 = cospif (lat2 / 180.0f);<br>dlat = lat2 - lat1;<br>dlon = lon2 - lon1;<br>d1 = sinpif (dlat / 360.0f);<br>d2 = sinpif (dlon / 360.0f);<br>t = d2 * d2 * c1 * c2;<br>a = d1 * d1 + t;<br>c = 2.0f * asinf (fminf (1.0f, sqrtf (a)));<br>return radius * c;
Thanks to Norbert Juffa for contributing this code.
Discuss (0)
Like
Tags
Simulation / Modeling / Design | CUDA | CUDA C/C++ | Geospatial | Pro Tip
About the Authors
About Mark Harris
Mark is an NVIDIA Distinguished Engineer working on RAPIDS. Mark has over twenty years of experience developing software for GPUs, ranging from graphics and games, to physically-based simulation, to parallel algorithms and high-performance computing. While a Ph.D. student at The University of North Carolina he recognized a nascent trend and coined a name for it: GPGPU (General-Purpose computing on Graphics Processing Units).
Follow @harrism on Twitter
View all posts by Mark Harris
Comments
Related posts
Interactively Visualizing a DriveTime Radius from Any Point in the US
Interactively Visualizing a DriveTime Radius from Any Point in the US
Share Your Science: Improving the Geolocation Accuracy of Aerial and Orbital Imagery with GPUs
Share Your Science: Improving the Geolocation Accuracy of Aerial and Orbital Imagery with GPUs
GPUs Help Measure Rising Sea Levels in Real-Time
GPUs Help Measure Rising Sea Levels in Real-Time
Researchers Use GPUs to Detect Earthquake Hazards Coming Our Way
Researchers Use GPUs to Detect Earthquake Hazards Coming Our Way
Everything You Ever Wanted to Know About Floating Point but Were Afraid to Ask
Everything You Ever Wanted to Know About Floating Point but Were Afraid to Ask
Related posts
Build On-Device AI Companions with the NVIDIA ACE Game Agent SDK and...