Member Avatar for thompsonSensibl

Hi there,

I am stuck with a problem, and don't know where to start.

I am given a series of cities, and their locations in longitude and latitude. The goal is to find the two cities with the shortest distance.

I have an algorithm which, given the geographical locations (longitude and latitude) of two cities, calculates the distance between them in kilometres.

I also have an algorithm that can calculate the answer in nlogn time, but only with inputs of x,y coordinates, and NOT longitude / latutude :( ...


How could I change longitude,latitude to x,y, in order to use the algorithm and find the closest pairs?

Thank you!

  • 3 Contributors
  • 4 Replies
  • 327 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by NormR1

Dani AI

Generated

Short answer: two practical options.

For datasets that cover a relatively small area (a single city, state or country) convert latitude/longitude to planar x,y with a simple equirectangular projection using the mean latitude as a scale factor, then run the existing O(n log n) 2‑D closest‑pair routine. This keeps distortion small and preserves nearest‑pair order for typical city separations; normalize longitude differences to ±180° to avoid dateline problems.

rad = PI/180
lat0 = mean(all_lats) * rad
x = R * (lon * rad) * cos(lat0)
y = R * (lat * rad)

For truly global data, convert each (lat,lon) to a 3‑D unit vector on the sphere and do the nearest‑pair search in Euclidean 3‑D. For points on the unit sphere the straight‑line (chord) distance is a monotonic function of the central (great‑circle) angle, so the same pair is closest in either metric. Example conversion:

latr = lat * PI/180
lonr = lon * PI/180
x = cos(latr) * cos(lonr)
y = cos(latr) * sin(lonr)
z = sin(latr)

Implementation notes and cautions: was right to flag curvature; planar projection is only safe when distortion is negligible. ’s concern about replacing Pythagoras with great‑circle math is valid — swapping the distance function inside a plane D&C routine can break its geometric assumptions. Either (a) project to a plane and reuse the 2‑D algorithm, or (b) use the 3‑D vectors and a KD‑tree / 3‑D closest‑pair routine (both can be O(n log n) for fixed dimension). In any case, compute the final reported distance with an exact great‑circle (haversine) formula so the output is in kilometres.

Recommended Answers

All 4 Replies

Member Avatar for JamesCherrill

Long/lat map points on a sphere. x,y map points on plane. You can't meaningfully convert between the two except over areas small enough that you can ignore the curvature of the earth.

Member Avatar for thompsonSensibl

Long/lat map points on a sphere. x,y map points on plane. You can't meaningfully convert between the two except over areas small enough that you can ignore the curvature of the earth.

Um... here is something that might say otherwise:
http://stackoverflow.com/questions/7129482/closest-pair-of-points-problem
"...translate them to three dimensional coordinates and then use the divide and conquer approach using a plane rather than a line. This will definitely work correctly."

but i don't understand the explanation :X any help to understand it would be grateful, thanks!

Edited by thompsonSensibl because: n/a
Member Avatar for JamesCherrill

No, there's no contradiction. That link proposes converting to 3-dimensional coords (x,y,z) which is OK. I was answering the question about 2-D coordinates (x,y).
I looked at the divide & conquer link, and I didn't understand it either. :-(

Member Avatar for NormR1

Mercator had this problem with his maps.
When you convert lat/long to x,y,z the distance between the points would be though the surface of the earth vs on the surface via a great circle route. No idea if you would get the same results.

I also have an algorithm that can calculate the answer in nlogn time, but only with inputs of x,y coordinates,

how does that algorithm work? Does it use the Pythagorean theorem to compute distances between two x,y points? Can you replace the distance calc with the great circle calc

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.