5 ms·

Spatial Data Structures for Better Map Interactions

113 points by efkv 13y ago

adam-a 13y ago
The other way to do this, which is common in (older?) 3d video games, is to render your scene twice, once normally and once with each object shaded in a unique flat colour. Then sample your second bitmap at the mouse position and map the pixel value back to your list of objects. This is very fast and only falls over when you start to have transparent objects, in which case ray-casting and r-trees become appropriate.
- munificent 13y ago
  This is basically a grid[1] where the resolution is down to 1 pixel. Not a bad solution! [1]: http://en.wikipedia.org/wiki/Grid_(spatial_index) http://en.wikipedia.org/wiki/Grid_(spatial_index)
ryandrake 13y ago
Spatial data structures are great, and heavily used in all kinds of mapping applications. Most of the systems I've worked with used the more constrained quadtree structure, where the map is divided into uniformly-sized tiles, and a level-of-detail hierarchy is built. This is good for raster data, where each tile is a picture and the whole world is covered by tiles. The R-tree has great advantages when the complexity is not uniformly distributed across the map, for example, vector road data, where vast areas on earth have no data, and most of the data is concentrated in small urban areas. I believe PostGIS, which adds spatial operations to Postgres, uses an R-tree as its spatial index. An improvement on the R-tree, the R(star)-tree, uses a different node splitting algorithm and includes re-insertions (similar to balancing a B-tree), reducing both coverage and overlap. The insertion complexity is greater, but in general, R(star)-tree query performance tends to be a bit better for mapping applications. Generally, maps don't change that often, so building the tree tends to happen far less often than querying it. There are many more specialized spatial data structures available, for example, Kd-trees, which can be perfectly balanced and are useful for storing point data. If you're really interested in this stuff, the holy bibles for spacial data structures (which I keep in a special place on my bookshelf) are a pair of books written by H. Samet: The Design and Analysis of Spatial Data Structures, and Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. EDIT: Formatting, and apparently you can't write the asterisk character on HN R-Tree paper (1984): http://postgis.org/support/rtree.pdf http://postgis.org/support/rtree.pdf R(star)-Tree (1990): http://epub.ub.uni-muenchen.de/4256/1/31.pdf http://epub.ub.uni-muenchen.de/4256/1/31.pdf PostGIS: http://postgis.net http://postgis.net H.Samet textbooks: http://www.cs.umd.edu/~hjs/design.html http://www.cs.umd.edu/~hjs/design.html
- saosebastiao 13y ago
  PostGIS uses an R Tree implemented on a GiST index by default, with a pure R tree partially implemented. http://postgis.net/docs/manual-2.1/using_postgis_dbmanagement.html#idp7232880 http://postgis.net/docs/manual-2.1/using_postgis_dbmanagemen...
  - ryandrake 13y ago
    Ahh, I stand corrected. Thanks!
- dhconnelly 13y ago
  Shameless plug of my Go R-tree implementation, which cites the Guttman R-tree paper and the Roussopoulos/Kelley/Vincent nearest-neighbor search paper in its implementation, and is therefore perhaps a useful resource: https://github.com/dhconnelly/rtreego https://github.com/dhconnelly/rtreego
- jandrewrogers 13y ago
  The spatial data structure literature is quite incomplete, and there is a lot of confusion about what to use when. Many of the issues with spatial indexing performance at companies I go into is that they are doing it wrong, not that they necessarily have a fundamental problem. It should be pointed out that R-family data structures should only be used for data sets that are (1) small and (2) relatively static. They scale very poorly in a number of ways. The primary reason they are used in databases is that they can handle interval (i.e. non-point) spatial data types without the possibility of pathological space complexity (bad when talking about databases) and fit B-tree indexing models adequately, which that software understands. Quad-tree variants can scale well for point data types but are often terrible for indexing non-point data types due to pathological space complexity. Grid-file variants are the canonical structure for large-scale spatial data sets if the data is static. However, the number of companies implementing these correctly at scale is approximately zero in my experience. For general, scalable, online/dynamic spatial indexing structures, there is another family of algorithms and data structures (adaptive spatial sieves) that are basically ignored in the literature even though they were first described in 1990, albeit in a not very useful form at the time. If you are doing petabyte-scale real-time indexing of polygons at extremely high rates, this is what you would use but little is published about them because most modern variants did not come out of academia. And the most advanced algorithm family for indexing point-like data is not in the literature at all. (Background: my day job involves extreme-scale, high-performance spatial indexing software and I invented a few spatial indexing algorithms back in the day that are still the state-of-the-art in their respective algorithm families.)
sigil 13y ago
If you find yourself doing big-time spatial queries, consider using the PostGIS extension for Postgres, which uses R-Trees-on-top-of-GiST indices: http://postgis.net/ http://postgis.net/ In addition to ray-casting and R-Trees, there's another alternative for the "point in polygon test" not mentioned by the article: compute the Winding Number. Appropriate for a very low number of polygons where a full spatial index might be overkill. http://en.wikipedia.org/wiki/Point_in_polygon#Winding_number_algorithm http://en.wikipedia.org/wiki/Point_in_polygon#Winding_number... I think seatgeek made the right choice in this case though with a client-side R-Tree. Aside: does anyone know what browsers use for hit-testing polygons defined by the <map/> tag?
cwmma 13y ago
the rtree implementation they found [1] isn't connected to leaflet except that the org that it lives in also manages some leaflet plugins, Vladimir, the author of leaflet, does have his own rtree implementation [2]. For the record I manage the one in the article. 1: https://github.com/leaflet-extras/RTree https://github.com/leaflet-extras/RTree 2. https://github.com/mourner/rbush https://github.com/mourner/rbush
- efkv 13y ago
  Ah, you are right. I must have looked at Vladimir's implementation and then just associated him in my mind with the leaflet-extras implementation.
kstop 13y ago
tl;dr: we re-implemented imagemaps.

113 points by efkv 13y ago

The other way to do this, which is common in (older?) 3d video games, is to render your scene twice, once normally and once with each object shaded in a unique flat colour. Then sample your second bitmap at the mouse position and map the pixel value back to your list of objects. This is very fast and only falls over when you start to have transparent objects, in which case ray-casting and r-trees become appropriate.

munificent 13y ago
This is basically a grid[1] where the resolution is down to 1 pixel. Not a bad solution! [1]: http://en.wikipedia.org/wiki/Grid_(spatial_index) http://en.wikipedia.org/wiki/Grid_(spatial_index)

ryandrake 13y ago

Spatial data structures are great, and heavily used in all kinds of mapping applications. Most of the systems I've worked with used the more constrained quadtree structure, where the map is divided into uniformly-sized tiles, and a level-of-detail hierarchy is built. This is good for raster data, where each tile is a picture and the whole world is covered by tiles. The R-tree has great advantages when the complexity is not uniformly distributed across the map, for example, vector road data, where vast areas on earth have no data, and most of the data is concentrated in small urban areas. I believe PostGIS, which adds spatial operations to Postgres, uses an R-tree as its spatial index. An improvement on the R-tree, the R(star)-tree, uses a different node splitting algorithm and includes re-insertions (similar to balancing a B-tree), reducing both coverage and overlap. The insertion complexity is greater, but in general, R(star)-tree query performance tends to be a bit better for mapping applications. Generally, maps don't change that often, so building the tree tends to happen far less often than querying it. There are many more specialized spatial data structures available, for example, Kd-trees, which can be perfectly balanced and are useful for storing point data. If you're really interested in this stuff, the holy bibles for spacial data structures (which I keep in a special place on my bookshelf) are a pair of books written by H. Samet: The Design and Analysis of Spatial Data Structures, and Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. EDIT: Formatting, and apparently you can't write the asterisk character on HN R-Tree paper (1984): http://postgis.org/support/rtree.pdf http://postgis.org/support/rtree.pdf R(star)-Tree (1990): http://epub.ub.uni-muenchen.de/4256/1/31.pdf http://epub.ub.uni-muenchen.de/4256/1/31.pdf PostGIS: http://postgis.net http://postgis.net H.Samet textbooks: http://www.cs.umd.edu/~hjs/design.html http://www.cs.umd.edu/~hjs/design.html

saosebastiao 13y ago
PostGIS uses an R Tree implemented on a GiST index by default, with a pure R tree partially implemented. http://postgis.net/docs/manual-2.1/using_postgis_dbmanagement.html#idp7232880 http://postgis.net/docs/manual-2.1/using_postgis_dbmanagemen...
- ryandrake 13y ago
  Ahh, I stand corrected. Thanks!
dhconnelly 13y ago
Shameless plug of my Go R-tree implementation, which cites the Guttman R-tree paper and the Roussopoulos/Kelley/Vincent nearest-neighbor search paper in its implementation, and is therefore perhaps a useful resource: https://github.com/dhconnelly/rtreego https://github.com/dhconnelly/rtreego
jandrewrogers 13y ago
The spatial data structure literature is quite incomplete, and there is a lot of confusion about what to use when. Many of the issues with spatial indexing performance at companies I go into is that they are doing it wrong, not that they necessarily have a fundamental problem. It should be pointed out that R-family data structures should only be used for data sets that are (1) small and (2) relatively static. They scale very poorly in a number of ways. The primary reason they are used in databases is that they can handle interval (i.e. non-point) spatial data types without the possibility of pathological space complexity (bad when talking about databases) and fit B-tree indexing models adequately, which that software understands. Quad-tree variants can scale well for point data types but are often terrible for indexing non-point data types due to pathological space complexity. Grid-file variants are the canonical structure for large-scale spatial data sets if the data is static. However, the number of companies implementing these correctly at scale is approximately zero in my experience. For general, scalable, online/dynamic spatial indexing structures, there is another family of algorithms and data structures (adaptive spatial sieves) that are basically ignored in the literature even though they were first described in 1990, albeit in a not very useful form at the time. If you are doing petabyte-scale real-time indexing of polygons at extremely high rates, this is what you would use but little is published about them because most modern variants did not come out of academia. And the most advanced algorithm family for indexing point-like data is not in the literature at all. (Background: my day job involves extreme-scale, high-performance spatial indexing software and I invented a few spatial indexing algorithms back in the day that are still the state-of-the-art in their respective algorithm families.)

sigil 13y ago

If you find yourself doing big-time spatial queries, consider using the PostGIS extension for Postgres, which uses R-Trees-on-top-of-GiST indices: http://postgis.net/ http://postgis.net/ In addition to ray-casting and R-Trees, there's another alternative for the "point in polygon test" not mentioned by the article: compute the Winding Number. Appropriate for a very low number of polygons where a full spatial index might be overkill. http://en.wikipedia.org/wiki/Point_in_polygon#Winding_number_algorithm http://en.wikipedia.org/wiki/Point_in_polygon#Winding_number... I think seatgeek made the right choice in this case though with a client-side R-Tree. Aside: does anyone know what browsers use for hit-testing polygons defined by the <map/> tag?

cwmma 13y ago

the rtree implementation they found [1] isn't connected to leaflet except that the org that it lives in also manages some leaflet plugins, Vladimir, the author of leaflet, does have his own rtree implementation [2]. For the record I manage the one in the article. 1: https://github.com/leaflet-extras/RTree https://github.com/leaflet-extras/RTree 2. https://github.com/mourner/rbush https://github.com/mourner/rbush

efkv 13y ago
Ah, you are right. I must have looked at Vladimir's implementation and then just associated him in my mind with the leaflet-extras implementation.

kstop 13y ago

tl;dr: we re-implemented imagemaps.