# Getting the max/min longitude/latitude within a distance from a point

I have a location in longitude/latitude (x,y) and a distance d. Now I want to find the maximum and minimum longitude and latitude that are within the the distance d from my location. The goal is to create a box with exact width and height, with the location (x,y) in the middle.

I have found code for getting the distance from two points, and through this I could search for the correct longitude/latitude by getting the distance between points that only differs in longitude or latitude until I find the correct distance. But this is obviously not the best solution, and the goal of this is to get a solution that is very fast when implemented in code. However, if it helps, here is the implementation that gives the distance between two locations (in java):

public static double getDistanceMeter(double currentLongitude, double currentLatitude, double goalLongitude,
double goalLatitude) {
double meterConversion = 1609;
double R = 3958.7558657440545D; // Radius of the earth in km
double dLat = Math.toRadians(goalLatitude - currentLatitude);
double dLon = Math.toRadians(goalLongitude - currentLongitude);
double a = Math.sin(dLat / 2D) * Math.sin(dLat / 2D) + Math.cos(Math.toRadians(currentLatitude))
* Math.cos(Math.toRadians(goalLatitude)) * Math.sin(dLon / 2D) * Math.sin(dLon / 2D);
double c = 2D * Math.atan2(Math.sqrt(a), Math.sqrt(1D - a));
double d = R * c * meterConversion; // Distance in m
return d;
}


(if someone would help me find better tags for this question, I would really appreciate it, I feel lost in the math-lingo)

-

Let's approximate the globe by a sphere, because that's a lot simpler than an ellipsoid. Call its radius $R$ (approximately 6370km). The maximum latitude within distance $d$ of your point at latitude $y$ (degrees) is $\min\left(90, y + \frac{180d}{\pi R}\right)$ (where the minimum becomes relevant near the North Pole), and the minimum latitude is correspondingly $\max\left(-90, y - \frac{180d}{\pi R}\right)$.
The curve of constant latitude $\theta$ (radians) is a circle of circumference $2\pi R \cos\theta$, so to a first approximation the point due east of $(x, y)$ at distance $d$ is at longitude $x + \frac{180d}{\pi R \cos\theta}$, where $\theta = \frac{\pi y}{180}$. (Actually that's going to be an underestimate when $\theta \ne 0$ because the straightest line between two points is a great circle. But it suffices to illustrate the point).
So when you say "a box", what do you mean? You can't just compute max and min longitude by going east and west $d$, and max and min latitude by going north and south $d$; generate four points by pairing them up; and draw lines between those points. This breaks down spectacularly near the poles, where there will be a range of latitudes in which every longitude is within $d$ of your point, but that range may not include the latitude of the point itself.
@sandis, the best approach probably depends on your restrictions on d and plausible latitudes, but it's really a data structures question rather than a mathematical one. A relatively simple approach would be to use oct-trees; for more sophisticated approaches look at papers from the GIS community or search for terms like k-nearest. –  Peter Taylor Jun 27 '12 at 11:58