5 ms·

I thought I could maybe do better with a binary search system. Here is some napkin math: Circumference of earth: 40,075,000m Number of choices to get 10m accu

I thought I could maybe do better with a binary search system. Here is some napkin math: Circumference of earth: 40,075,000m Number of choices to get 10m accuracy: log2(40,075,000/10) = 21.9 ~ 22 bits We need two numbers for latitude and longitude = 44 bits We can get 5 bits from each alphanum character = 44/5 ~ 9 alphanum characters Add the checksum character and you're at 10 characters. Anyone have better methods that only use capital letters and digits? This system has the disadvantage of two nearby locations potentially having totally different codes.

TheLoneWolfling 12y ago
One obvious "issue" with that: you have better accuracy at the poles than at the equator.
- gamegoblin 12y ago
  Does latitude and longitude not suffer from the same problem?
  - rtkwe 12y ago
    No because latitude and longitude are infinitely precise only limited by the accuracy of the measuring instrument. With the binary search idea you proposed the dividing lines are more tightly packed longitudinally near the poles.
    - gamegoblin 12y ago
      But near the poles, 1 degree longitude specifies a much smaller span than at the equator. So with say, 4 digits per latitude and longitude, you can specify a much smaller region at the poles than the equator.
      - TheLoneWolfling 12y ago
        And that's the problem. To get 10m accuracy at the equator, you'd need to get much greater than 10m accuracy at the poles. You're effectively wasting information. The surface area of the Earth is 5.10x10^8 km^2. In an ideal world, you could uniquely represent every 10m*10m area of the Earth - there are 5.1x10^12 such areas. log2(5.1x10^12) is about 42.2. So you're wasting about 1.8 bits of information (~4%). Not too bad, now that I calculate it out.
        gamegoblin 12y ago
        Yes, I get that. I was responding to user rtkwe who said that latitude/longitude didn't waste information.
        rtkwe 12y ago
        Lat. long. doesn't have a length limitation of the binary search system, 10:10 so the information isn't wasted because where the grid is sparser near the equator we just extend the decimal places.
        recursive 12y ago
        That "extension" is itself the waste being discussed. Some places require more digits than others.
mturmon 12y ago
Besides the "more accurate at poles" issue, you are also double-counting because you don't need to cover the circumference twice. An alternative is to find the Earth's surface area (5.1e8 km^2), and divide by 10mX10m. This gives the number of cells. Then take log base 30 (26 alpha + 10 digit - {"O", "I", "S", "U", "V", "Z"}). This turns out to be 8.60 characters. To detect all single-character errors, you need a full extra character (9.60). If you allow all alphanumerics (36 possibilities), you end up with 8.16 characters, plus one for errors is 9.16. Conclusion: if you were willing to give up some accuracy over oceans, you could get away with 9 characters, otherwise, 10 is the best you can do.
zackmorris 12y ago
As the others have said, there are too many bits used at the poles. You might be interested in sphere point picking: http://mathworld.wolfram.com/SpherePointPicking.html http://mathworld.wolfram.com/SpherePointPicking.html x = sqrt(1 - u^2) * cos θ y = sqrt(1 - u^2) * sin θ z = u θ ∈ [0,2π) u ∈ [-1,1] The idea is to pick θ and u uniformly instead of latitude and longitude, which ensures equal spacing anywhere on the globe (no squishing at the poles). If you visualize the areas of the side of a cylinder and a sphere: AreaOfSideOfCylinder = 2 * π * * r * h = 2 * π * r * (2 * r) = 4 * π * r^2 AreaOfSphere = 4 * π * r^2 You can see that the areas are equal, but if you think of the triangular sections of a basketball, a uniform distribution uses just over half the bits of lat/long. That’s because the sections bulge out, and also latitude isn’t as susceptible to pinching (perhaps someone who works with distributions can provide the exact ratio). So my guess is that this scheme would use perhaps 6 or 7 digits, depending on whether a checksum is desired. I've used the formulas on that page with great success for things like random stars in OpenGL. This is loosely related to quaternions but I don't have enough math to describe how exactly. Quaternions sweep uniformly, whereas Euler angles pinch and suffer from gimbal lock.
- zackmorris 12y ago
  Too late to edit my own post but mturmon is correct, my guess about the number of digits was incorrect. Even with a uniform distribution, it still takes 8.44 digits in base 32 and 7.04 digits in base 64, not counting checksum: https://www.wolframalpha.com/input/?i=log+base+32+of+%28%285.1e8%29*1000*1000%2F%2810*10%29%29 https://www.wolframalpha.com/input/?i=log+base+32+of+%28%285... https://www.wolframalpha.com/input/?i=log+base+64+of+%28%285.1e8%29*1000*1000%2F%2810*10%29%29 https://www.wolframalpha.com/input/?i=log+base+64+of+%28%285...

TheLoneWolfling 12y ago

One obvious "issue" with that: you have better accuracy at the poles than at the equator.

gamegoblin 12y ago
Does latitude and longitude not suffer from the same problem?
- rtkwe 12y ago
  No because latitude and longitude are infinitely precise only limited by the accuracy of the measuring instrument. With the binary search idea you proposed the dividing lines are more tightly packed longitudinally near the poles.
  - gamegoblin 12y ago
    But near the poles, 1 degree longitude specifies a much smaller span than at the equator. So with say, 4 digits per latitude and longitude, you can specify a much smaller region at the poles than the equator.
    - TheLoneWolfling 12y ago
      And that's the problem. To get 10m accuracy at the equator, you'd need to get much greater than 10m accuracy at the poles. You're effectively wasting information. The surface area of the Earth is 5.10x10^8 km^2. In an ideal world, you could uniquely represent every 10m*10m area of the Earth - there are 5.1x10^12 such areas. log2(5.1x10^12) is about 42.2. So you're wasting about 1.8 bits of information (~4%). Not too bad, now that I calculate it out.
      - gamegoblin 12y ago
        Yes, I get that. I was responding to user rtkwe who said that latitude/longitude didn't waste information.
        rtkwe 12y ago
        Lat. long. doesn't have a length limitation of the binary search system, 10:10 so the information isn't wasted because where the grid is sparser near the equator we just extend the decimal places.
        recursive 12y ago
        That "extension" is itself the waste being discussed. Some places require more digits than others.

mturmon 12y ago

Besides the "more accurate at poles" issue, you are also double-counting because you don't need to cover the circumference twice. An alternative is to find the Earth's surface area (5.1e8 km^2), and divide by 10mX10m. This gives the number of cells. Then take log base 30 (26 alpha + 10 digit - {"O", "I", "S", "U", "V", "Z"}). This turns out to be 8.60 characters. To detect all single-character errors, you need a full extra character (9.60). If you allow all alphanumerics (36 possibilities), you end up with 8.16 characters, plus one for errors is 9.16. Conclusion: if you were willing to give up some accuracy over oceans, you could get away with 9 characters, otherwise, 10 is the best you can do.

zackmorris 12y ago

As the others have said, there are too many bits used at the poles. You might be interested in sphere point picking: http://mathworld.wolfram.com/SpherePointPicking.html http://mathworld.wolfram.com/SpherePointPicking.html x = sqrt(1 - u^2) * cos θ y = sqrt(1 - u^2) * sin θ z = u θ ∈ [0,2π) u ∈ [-1,1] The idea is to pick θ and u uniformly instead of latitude and longitude, which ensures equal spacing anywhere on the globe (no squishing at the poles). If you visualize the areas of the side of a cylinder and a sphere: AreaOfSideOfCylinder = 2 * π * * r * h = 2 * π * r * (2 * r) = 4 * π * r^2 AreaOfSphere = 4 * π * r^2 You can see that the areas are equal, but if you think of the triangular sections of a basketball, a uniform distribution uses just over half the bits of lat/long. That’s because the sections bulge out, and also latitude isn’t as susceptible to pinching (perhaps someone who works with distributions can provide the exact ratio). So my guess is that this scheme would use perhaps 6 or 7 digits, depending on whether a checksum is desired. I've used the formulas on that page with great success for things like random stars in OpenGL. This is loosely related to quaternions but I don't have enough math to describe how exactly. Quaternions sweep uniformly, whereas Euler angles pinch and suffer from gimbal lock.

zackmorris 12y ago
Too late to edit my own post but mturmon is correct, my guess about the number of digits was incorrect. Even with a uniform distribution, it still takes 8.44 digits in base 32 and 7.04 digits in base 64, not counting checksum: https://www.wolframalpha.com/input/?i=log+base+32+of+%28%285.1e8%29*1000*1000%2F%2810*10%29%29 https://www.wolframalpha.com/input/?i=log+base+32+of+%28%285... https://www.wolframalpha.com/input/?i=log+base+64+of+%28%285.1e8%29*1000*1000%2F%2810*10%29%29 https://www.wolframalpha.com/input/?i=log+base+64+of+%28%285...