Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
add comment

1 Answer

I think you're asking the wrong question, and I'll explain why.

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.

share|improve this answer
    
Indeed, I can see why an answer to my question would not solve my original problem completely. However, are there any better alternatives? I need to computationally quickly find all points that are within an approximal distance to a point. Preferably I thus need to just check that the longitude/latitude are within a span. I guess it would be acceptable that the result would be distorted close to the poles, if there are no better solution. –  pgsandstrom Jun 27 '12 at 10:21
    
To be clear: I cant just compare the distance between the given point to all other points, since there will be millions of points. However, getting all points within a span will be log(n) if they are already ordered. –  pgsandstrom Jun 27 '12 at 10:22
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.