5

I am developing an app where I need to divide the entire world map into fixed sized square blocks. For simplicity, think of it as a problem of dividing the google maps into a fixed sized block. I can choose any arbitrary point in the map and my app needs to create a block of fixed size around that point.

The primary concern here is when i choose a point and define a block around it, there should never be an overlap between this block and any other blocks that were defined previously. In other words, any point can belong to one and only one block.

What is the best algorithm I can use to do this? I am guessing this is a problem that has been solved before and doesn't require me to reinvent the wheel.

Right now, all I am doing is when the user selects a point, I get the latitude and longitude of the point and define a square block around it. While doing so, I am making a check to see whether the new block would overlap with other blocks around it or not.

Any help would be greatly appreciated.

CuriousCoder
  • 153
  • 1
  • 5
  • Climate models use a similar [approach](https://en.wikipedia.org/wiki/General_Circulation_Model) – Robbie Dee Jan 22 '16 at 16:35
  • Are you asking how to determine the largest possible square centered at (x,y) that does not intersect with any of the squares you've already drawn or exceed some maximum size? Or some other problem? – Ixrec Jan 22 '16 at 16:36
  • @lxrec No, not the largest possible square. I want to determine a fixed sized square (say 1mile x 1mile) centered at that point such that it doesn't intersect with any other squares that I have already drawn. – CuriousCoder Jan 22 '16 at 16:38
  • Well, if there's only one valid size, and the center is already known, then there's only one possible square. Either it does intersect another square or it doesn't. Are you asking how to test for intersections efficiently? – Ixrec Jan 22 '16 at 17:05
  • Is this question about mapping the surface of a sphere to a rectangle? – MetaFight Jan 22 '16 at 17:15
  • 2
    Yes, this problem as already been solved. Take a look at [OpenStreetMap tiles](http://wiki.openstreetmap.org/wiki/Tiles). – Gilbert Le Blanc Jan 22 '16 at 17:45
  • I formulated an answer making use of the "Quad Tree" concept in game development, but one problem is I'm not sure if you want a click to always create a dot right on the point picked, or if it's okay for that dot to simply appear at the nearest suitable predefined square. (In the former case, you'd have a way of "rejecting" clicks because they're too close to another dot) Additionally, I'm curious if you want squares because you feel they're easier, or if circles would be suitable, as a way of restricting minimum distance. – Katana314 Jan 22 '16 at 17:45

1 Answers1

2

You can't map the surface of a sphere onto a plane square grid, whilst at the same time preserving distance, area and angles - there has to be some sort of compromise. See here for more details.

If you really want "equal sized elements", a better solution might be to use a spherical co-ordinate system - latitude and longitude with elements of equal arc length. That way, any point on the surface can be assigned to a single element. However this means that the elements are not perfectly square so there will be a little distortion if you treat them as such. Also, all of the elements will have the same height, but they will become progressively narrower as you move away from the equator.

Assuming the earth is a perfect sphere of radius 6371 Km, and using a 1 degree granularity, each element will be 111.19 km from north to south. Those along the equator will be 111.19 Km along the southern edge but 111.17 Km along the northern edge. You'd be hard pressed to notice this 0.02% difference though if you just treated it as a square.

As you move further north, the difference between the length northern and southern edges becomes more pronounced.

for example :-

Guatemala City (15 deg north) 107.89 - 107.41 Km (0.45%)

San Antonio (30 deg north) 97.25 - 96.26 Km (0.98%)

Lyon (45 deg north) 78.62 - 77.24 Km (1.76%)

Oslo (60 deg north) 57.27 - 55.60 Km (2.92%)

So you could draw a 5 element high grid centred on any of these cities with limited distortion, just with the elements becoming more rectangular as you move north, so you need more elements for the same horizontal distance. It's only as you get towards the poles that you start to get big problems, with the final element effectively being a triangle, coming to a point at the pole.

If you were to zoom in by using a smaller granularity, say 0.1 degree of arc, then the "squareness" of the elements improves. You'd have to go to 80.2 deg north before you get even a 1% difference between the lengths of the northern and southern edges, although these elements will have an aspect ratio of 5.8:1 - 11.1 x 1.89 km. This is almost enough to cover the northernmost permanently inhabited place in the world - Albert, Canada is 82.5 deg north.

Peregrine
  • 1,236
  • 1
  • 7
  • 9