5 ms·

"Currently geo indexing is limited to indexing squares with no "wrapping" at the outer boundaries."

by bkudria 17y ago

jrockway 17y ago
This could be added fairly trivially, however, and it is easy to emulate inside your app. You still get the efficiency that spatial indexing provides either way. From reading the documentation, this seems like a standard R-tree implementation, which is just a way to efficiently index two columns at once. If your dataset is two columns, x and y, a normal index could limit the xs efficiently, or limit the ys efficiently, but it couldn't limit both at the same time. This means you'd always have to do a scan over a large number of irrelevant records. The R-tree lets you get at the pair efficiently; you can get 2,2 without having to also look at 2,0; 2,1; 2,3; 2,... This is the performance benefit; if you want to know about all the coffee shops near 2,2, you can just retrieve 2,2 and not have to look at the rest of the dataset. If you need to implement wrapping, you can just retrieve the squares on the other side of the jump when someone requests records near the jump. This probably behaves differently for "things on earth" than on arbitrary two-dimensional datasets, so it is left as an exercise for the reader. I assume. I have never had the occasion to implement (or even use) spatial indexes.
Groxx 17y ago
Out of curiosity, what would "wrapping" mean in this case?
- sqs 17y ago
  A shape on the surface of the globe that includes Japan and Hawaii.
- wlievens 17y ago
  The international dateline; or more precisely the antemeridian. It's a nontrivial problem, that even plagues the more famous gis applications (such as Google Earth, which cannot render a polygon that crosses the antemeridian properly).
  - Groxx 17y ago
    Really? ((loc + 180) % 360) - 180 = loc, wrapped past the antemeridian, for any value. Just detect sign changes, and reverse the range on the reversing side. Seems to me graphics people have been doing this sort of thing for years. A similar, but more complicated problem: painting the texture on a 3D model (literally onto the rendered model), even across seams. That's general-cased, wrapping on a sphere is a rather trivial special case by comparison. Granted, I haven't made any GIS systems, and the underlying structure may make it more difficult than this. But this is definitely a solved problem, are they just reluctant to modify their system?
    - wlievens 17y ago
      The real problem is that you can't tell inside from outside in a polygon that wraps the antemeridian.
      - Groxx 17y ago
        Aaah, yeah, that's harder. Hm. Personally, I'd just find the points that edges intersect the antemeridian, and define two polygons, ORing the results. Know if there's a reason that isn't done?
        wlievens 17y ago
        That's the workaround, but that process is left to the user. Google Earth doesn't do that for you (since it can't know how to split the polygon, because it doesn't know the inside!).

"Currently geo indexing is limited to indexing squares with no "wrapping" at the outer boundaries."

by bkudria 17y ago

"Currently geo indexing is limited to indexing squares with no "wrapping" at the outer boundaries."

This could be added fairly trivially, however, and it is easy to emulate inside your app. You still get the efficiency that spatial indexing provides either way. From reading the documentation, this seems like a standard R-tree implementation, which is just a way to efficiently index two columns at once. If your dataset is two columns, x and y, a normal index could limit the xs efficiently, or limit the ys efficiently, but it couldn't limit both at the same time. This means you'd always have to do a scan over a large number of irrelevant records. The R-tree lets you get at the pair efficiently; you can get 2,2 without having to also look at 2,0; 2,1; 2,3; 2,... This is the performance benefit; if you want to know about all the coffee shops near 2,2, you can just retrieve 2,2 and not have to look at the rest of the dataset. If you need to implement wrapping, you can just retrieve the squares on the other side of the jump when someone requests records near the jump. This probably behaves differently for "things on earth" than on arbitrary two-dimensional datasets, so it is left as an exercise for the reader. I assume. I have never had the occasion to implement (or even use) spatial indexes.

Groxx 17y ago

Out of curiosity, what would "wrapping" mean in this case?

sqs 17y ago
A shape on the surface of the globe that includes Japan and Hawaii.
wlievens 17y ago
The international dateline; or more precisely the antemeridian. It's a nontrivial problem, that even plagues the more famous gis applications (such as Google Earth, which cannot render a polygon that crosses the antemeridian properly).
- Groxx 17y ago
  Really? ((loc + 180) % 360) - 180 = loc, wrapped past the antemeridian, for any value. Just detect sign changes, and reverse the range on the reversing side. Seems to me graphics people have been doing this sort of thing for years. A similar, but more complicated problem: painting the texture on a 3D model (literally onto the rendered model), even across seams. That's general-cased, wrapping on a sphere is a rather trivial special case by comparison. Granted, I haven't made any GIS systems, and the underlying structure may make it more difficult than this. But this is definitely a solved problem, are they just reluctant to modify their system?
  - wlievens 17y ago
    The real problem is that you can't tell inside from outside in a polygon that wraps the antemeridian.
    - Groxx 17y ago
      Aaah, yeah, that's harder. Hm. Personally, I'd just find the points that edges intersect the antemeridian, and define two polygons, ORing the results. Know if there's a reason that isn't done?
      - wlievens 17y ago
        That's the workaround, but that process is left to the user. Google Earth doesn't do that for you (since it can't know how to split the polygon, because it doesn't know the inside!).