you're reading...
gvsig mobile, tiling, wonthurt

Large shapefiles on small screens using a drawable spatial index

Sometimes a large vector layer needs to be rendered on a relatively small area on the screen. This happens especially with mobile devices, where screen size ranges between 240 x 320 and 480 x 850 pixels. If the vector layer affects a small number of pixels, it makes no sense to go through all the shapes and dedicate some (possibly optimized) computation and graphic instructions to each one. We should prepare an alternative for these cases, which will be used when the scale denominator surpasses a certain value.

Using the quadtree approach, we can create before-hand a drawable spatial index that will quickly tell us which pixels must be painted, and hopefully which color should be used. A non-optimized, initial attempt to do this is explained here.

How it will work

We’ll use a shapefile of polygons to illustrate this. Starting from a square that contains the shapefile’s bounding box, we will recursively analyze the relationship of each sub-square with the shapes contained in the shapefile. For example, if we create 9 levels in the spatial index, we’ll end up with a matrix of 512×512 pixels (2^9 = 512), which we will be able to draw very quickly as long as the shapefile does not need more pixels than that. The quadtree algorithm automatically dedicates more computation to borders, while large homogeneous areas (inside one shape or outside all shapes) are discarded quickly. Click to enlarge:

At the lowest level of the spatial index, we’ll have lists of integers telling us which features are intersected by each sub-square.

Creating the spatial index

We’ll have a matrix of integer values with 4 columns and as many rows as we need. Each row will represent a square in our quadtree scheme. Row 0 will be the minimum square than contains the layer’s bounding box:

Row 0: { 0, 3, 4, 0 }
Row 1: { 5, 6, 0, 0 }
...
Row n: { -23, 233, 1, 7000654 }

Each of the four columns will hold information about each of the four sub-squares:

0 1
3 2

The meaning of the integer values v will be:

  • If (v < 0): This value indicates that the feature with index -(v+1) in the shapefile completely contains this sub-square. Therefore, this sub-square must be painted with the fill color that corresponds to feature with index -(v+1).
  • If (v = 0): This value indicates that this sub-square in completely outside any feature in the shapefile. Therefore, this sub-square must not be painted.
  • If (v > 0 and v < 1,000,000): This value indicates this sub-square intersects with at least one feature but is not contained by any feature, and its four sub-squares are described in the row with index (v-1). Therefore, in case we have to paint this sub-square, we’ll use the layer’s border color. This will happen with views where the scale denominator is very large, and the spatial index itself is enough to draw the layer because the width of each screen pixel in map units is larger than the width in map units of the deepest sub-squares in the spatial index quadtree scheme.
  • If (v >= 1,000,000): This value will only be found in the lowest level of the quadtree scheme, and indicates that this sub-square is not contained by any feature in the shapefile, but intersects a number of features, and the indices of those intersected features are listed in the array, starting in position (v mod 1,000,000) and the number of features intersected is (v div 1,000,000).

Using the spatial index

Given the current viewport’s bounding box, we’ll start by comparing it with the well-known bounding box of each of the four sub-squares of the square that is being processed:

  • If the value is 0, the sub-square is ignored.
  • If the value is negative (sub-square is contained by a feature), we’ll find out the fill color that corresponds to that feature and paint it. This may result in a single pixel or a square on the map (see image).
  • If the value is positive, there are three cases:
    • If we need to go deeper because the screen pixel width is smaller than the sub-square’s width, then we’ll recursively visit the row indicated by that value.
    • If we need to go deeper but the spatial index does not have more levels, we’ll find a number bigger than 1,000,000, and we’ll have to access the SHP file to get those features, and paint them in the traditional way.
    • If the sub-square’s width is by now smaller than the screen pixel width and the value is indicating a row where the sub-square is described, then we are in the case where the spatial index is enough to paint the layer, and we’ll use the border color to paint this sub-square (which will result in a single pixel). In this case, we cannot use a different color for the border of each feature.

Conclusion

By indicating in a quadtree scheme the index of the feature that contains a certain sub-square or the place where that sub-square is expanded, we can draw the layer very quickly when all the shapes need to be painted in a small portion of the screen. At the bottom of our quadtree spatial index, we can list the indices of the features intersected by each leaf sub-square.

You can see here a video showing how a shapefile (black) and it’s quadtree spatial index (red) are drawn. All the shapes are contained by the viewport, so a traditional spatial index telling which features intersect the viewport would not help:

Advertisements

Discussion

Trackbacks/Pingbacks

  1. Pingback: GIS-Lab Blog» Архив блога » Новости вокруг 40 - 02/03/2010

  2. Pingback: Why Your Business MUST Have a Mobile Website - 14/08/2012

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: