Feathered Tiles with Uniform Payload Size
for Progressive Transmission of Vector Data
Andrew Dufilie and Georges Grinstein
Institute for Visualization and Perception Research,
University of Massachusetts Lowell,
Lowell, Massachusetts, USA
{adufilie,grinstein}@cs.uml.edu
Abstract. We introduce Feathered Tiles, a novel vector data tiling
method for web mapping. This method eliminates redundant data
transfer, greatly reduces the amount of excess data transmitted for progressive refinements, and supports smooth zooming operations with onthe-fly generalization. For a given set of geometries, the effective area
of each vertex is computed and stored as a third coordinate, along with
the bounds of the effective area. The results are partitioned in three
dimensions into tiles of a desired byte length. Each tile is stored along
with the 3-dimensional bounds encapsulating the effective area of all vertices contained within. Individual tiles can then be retrieved on demand
with 3-dimensional queries to reproduce a simplified set of geometries
for a given scale and viewport. The key to reducing excess data transfer
lies in associating tiles with the effective bounds of individual vertices
rather than the bounds of the geometries that contain the vertices. This
tiling method is implemented in the open source visualization framework,
Weave.
Keywords: Vector Data, Vector Tiling, Progressive Transmission, Web
Mapping, Generalization, Data Structures, Open Source.
1 Introduction
Our motivation for designing a vector data tiling method came from the requirements of our open source, web-based visualization framework, Weave [12,40]. Our
goals included immediate feedback when the user visits the page and a highly
interactive and customizable visualization interface. We needed the capability of
rendering individual geometries with dynamic line and fill styles as well as polygon intersection testing during brushing operations. We also wanted to be able to
interactively explore large data sets without requiring powerful server machines.
Since available solutions did not meet these requirements, a new solution had to
be developed.
To achieve these goals, it was apparent that progressive transmission of vector
data was necessary. If a fully detailed visualization cannot be transferred or
processed within a timely manner, the user should be allowed to interact with
D. Pfoser and K.-J. Li (Eds.): W2GIS 2014, LNCS 8470, pp. 19–35, 2014.
c Springer-Verlag Berlin Heidelberg 2014
20 A. Dufilie and G. Grinstein
a coarse representation of the data instead. To determine the order in which
vector data should be transmitted to the client, it is necessary to implement a
ranking system.
Our first prototype ranked each vertex in a collection of geometries by a
computed importance value and stored the results in a SQL table. Each time the
map was panned or zoomed to a new location, the client application queried the
server for a 3-dimensional range of data (x, y, and importance) and reassembled
the geometries from the resulting subset. Though this allowed large data sets to
be explored, it was apparent that a tiling system was necessary in order to avoid
redundant data transfer and reduce the computational burden of the server.
Due to the non-uniform distribution of vertices in typical geographic vector
data, a spatially uniform distribution of tiles is not practical as resulting tile
payload sizes can range anywhere from bytes to megabytes. The resulting unpredictability of transfer and processing requirements for any given tile request
would be unacceptable for an interactive web-based system. Having seen the
success of the Slippy Map1 image tiling scheme [33], we desired the same predictability and reliability for vector tiles. Our goal thus became a vector tiling
system in which the tiles have a uniform payload size.
To minimize server requirements, we generate vector tiles once using a preprocessor rather than generating tiles on-the-fly. For each vertex, the preprocessor
computes its effective area which is then treated as a third coordinate. The results are partitioned in three dimensions into tiles with uniform payload size
and overlapping bounds. The server component provides a list of tiles with their
3-dimensional bounds and allows them to be retrieved by their ID numbers. The
client determines which tiles are needed based on the visible extent and scale,
and remembers which tiles have been received to avoid redundant data transfer.
The client reorganizes the tiled vector data into efficient data structures to enable on-the-fly filtering and generalization for smooth zooming operations. The
server and client are implemented in Java and ActionScript, respectively.
This paper contributes several advancements to the field of vector-based webmapping. We present Feathered Tiles, a novel vector tiling method which produces tiles of uniform payload size, eliminates redundant data transfer, and does
not compromise data precision. Novel methods are presented for partitioning
vector data and reducing excess data transfer in an overlapping tile scheme. We
also suggest a non-traditional usage of BLG-tree [26] structures which makes
smooth zooming operations possible without explicitly storing and transmitting
such structures to the client.
The rest of the paper is organized as follows. In Sect. 2 we provide an overview
of related vector mapping solutions, Sects. 3–5 describe our architecture, Sect. 6
discusses the benefits of our solution, and the paper concludes in Sect. 7 with
future work.
1 A Slippy Map is web-based map which uses tiled images and supports zoom and
pan interactions. It uses a fixed set of zoom levels corresponding to magnification
factors of two. Zoom level N uses 4N square images arranged in grid covering the
entire world. Each tile is identified by a set of three integer coordinates (Z, Y, X).
Feathered Tiles 21
2 Related Work
This section provides a diverse sample of existing vector-based web-mapping solutions. There are two main approaches: those that use multiple representations
of vector data for discrete levels of detail, and those supporting progressive refinements. Approaches that use multiple representations suffer from redundant
data transfer when a change in zoom occurs, while those that support progressive refinements seek to eliminate redundancies. Ours is the only method which
partitions vector data with respect to byte length, thus the transfer requirement
for any given server request in the other methods is unpredictable.
2.1 Approaches Using Multiple Representations
Antoniou et al. [1] use an SVG [36] tiling system for vector data. They avoid
redundancy across tiles by splitting polygons at tile boundaries and then merging
them on the client. In order to make sure the polygons render correctly at the
edges of tiles, their system requests an extra set of tiles outside the viewing area.
This does not solve the problem in all situations however, as there could be a
polygon crossing three tiles but not having a vertex in the middle tile, in which
case the polygon could be rendered incorrectly at the edge of the screen.
The approaches of Campin [7] and Langfeld et al. [18] generate SVG tiles by
clipping polygons at tile boundaries.
GIS Cloud [15] provides compact JSON-formatted tiles in a Slippy Map [33]
tiling scheme by snapping all vertices to pixel coordinates, eliminating features
smaller than a pixel, and using clever indexing and lookup techniques. The server
generates the tiles on-the-fly [30]. This solution achieves impressive client-side
performance in exchange for its tradeoffs.
Mapsforge [19] uses a custom binary tile format for vector data. It is not
streamed from a server, but allows for efficient storage of geographical information, fast tile-based access, and filtering of map objects by zoom level.
OpenScienceMap [35] is an open source Android application supporting tiled
vector data using multiple representations for discrete zoom levels.
TileMill2 [37] is an experimental utility that generates vector tiles arranged
in a Slippy Map tiling scheme. They are stored in a binary format and are
never transferred directly to the client. The binary format contains a set of map
features defined by a list of vector graphics instructions such as moveTo and
lineTo. The advantage of defining map features this way is that the tile can be
stored once and re-used to generate any number of raster images with different
styles quickly on the server.
TileStache [38] generates GeoJSON [14] tiles with clipped geometries in a
Slippy Map tiling scheme which can then be rendered in Polymaps [29] as SVG.
For more examples, the OpenStreetMap Wiki provides an extensive list of
vector tiling solutions [28].
22 A. Dufilie and G. Grinstein
2.2 Approaches Supporting Progressive Refinements
The tGAP-tree is a structure suitable for progressive data transfer with the
server component performing dynamic queries on complex SQL tables [27,20].
Our approach uses progressive refinements and supports what Schmalstieg
et al. [34] call smooth levels of detail. Although we eliminate redundant data
transfer, we do have one drawback as pointed out by Han et al. [16]: “progressive
lossless vector transmission takes longer than downloading the entire raw data
set because of added encoding indexes.” Starting with the next section, the
remainder of this paper describes our approach.
3 Preprocessing Method
This section describes our preprocessor which converts a set of geometries into
a set of vector tiles. We first describe how we assign importance values to every
vertex in a set of geometries. Second, we describe the TileSplit algorithm for
partitioning three-dimensional data into tiles. Third, we describe how we apply
the TileSplit algorithm, and fourth we explain the critical details for minimizing
tile overlap and why we named our method Feathered Tiles.
3.1 Vertex Importance Calculations
Throughout our implementation we define importance values using area (in data
coordinates) as the unit. A different implementation could use a different unit
as long as all components are updated accordingly. Our client uses the area of
a single pixel as the minimum threshold for considering an object during spatial queries and on-the-fly generalization. This eliminates the need to preserve
topological consistency during preprocessing, since topological inconsistencies
are difficult to discern when the error is less than a single pixel [6]. If a larger
minimum threshold is desired for further reduction of data transfer and processing requirements, topologically consistent simplification methods [9,21] should
be used to calculate importance values.
Our architecture reproduces valid simplified geometries by skipping all vertices with an importance value less than a given threshold value. Such values
are generated using Visvalingam’s area-based method for ranking vertices [39].
This algorithm iteratively removes vertices with the least effective area, defined
by the triangle formed by a vertex and its two neighboring vertices. Because
the refinement process is exactly the inverse of the simplification process [17]
this algorithm guarantees that our progressive refinements occur in order of descending effective area, meaning that the map stabilizes quickly. In contrast, the
more widely known Douglas-Peucker (DP) algorithm [11] produces less pleasing
results because it tends to produce spikes where there are none [39] and produces
jumpy progressive refinements because the reverse of the simplification process
is not guaranteed to give progressively lower error values [26]. In fact the DP
algorithm is specifically designed to find the biggest jump possible in each of its
iterations, while Visvalingam’s does the opposite.
Feathered Tiles 23
The simplification process stops when a polygon or polyline is reduced to its
minimum number of vertices. The remaining vertices are marked as “required”
and their importance values are set equal to the area of the geometry’s bounding
box. This ensures that all required vertices will be included with a shape once
it becomes visible during a zoom-in operation. For polygons that have multiple
parts (islands or donut holes)2, we add a special placeholder at the index before
a new part begins and treat it as a required vertex of the part that follows.
These placeholders are necessary to avoid incorrectly treating vertices from multiple parts as a single closed loop. Since required vertices of individual parts of
polygons have importance values equal to the area of the part’s bounding box,
islands and donut holes will be excluded when they are smaller than a single
pixel.
3.2 The TileSplit Algorithm
The TileSplit algorithm can be used for partitioning any data with geospatial
aspects into tiles suitable for web mapping. The purpose of this algorithm is to
produce tiles with a uniform payload size by partitioning the data in three dimensions with respect to its length in bytes. Two data structures are introduced
in this algorithm:
– StreamObject is an interface for any object with three coordinates (X, Y,
and importance), a queryBounds and a payload. The queryBounds specifies
the (X, Y) range in which the StreamObject is required at or below its
importance level. The payload can be any length of data to be included in a
tile.
– StreamTile has a queryBounds, an importance range, a list of StreamObjects, and a payload. The queryBounds is the minimum bounding rectangle
containing the queryBounds of every StreamObject in the tile. The importance range covers the minimum and maximum importance values of all the
StreamObjects. The payload contains the concatenated payloads of all the
StreamObjects included in the StreamTile.
The TileSplit algorithm first sorts a list of StreamObjects by their importance
values. Then, it iteratively consumes chunks from the stream in descending order
of importance such that the first chunk is the size of a single tile and each
successive chunk is four times larger than the previous. Each chunk is then
partitioned into tiles with respect to the X and Y dimensions, each partition
with a byte length approximately equal to the target tile payload size. The result
is a layered pyramid of tiles similar to the Slippy Map image tiling scheme [33],
except that the bounding boxes and importance levels are non-uniform. This
non-uniform coverage is required to achieve the goal of uniform tile payload size,
and this is how we mitigate the problem of non-uniform distribution of geometric
detail. Pseudocode for implementing the TileSplit algorithm is shown below, and
Fig. 1 shows an example of resulting tile boundaries.
2 Also known as weakly simple polygons.
24 A. Dufilie and G. Grinstein
Pseudocode for the TileSplit algorithm
Function TileSplit(Array<StreamObject> input, Integer tileSize)
// Divides a stream into StreamTile objects with
// payload size approximately equal to tileSize.
Array<StreamObject> chunk
Array<StreamTile> output
Integer tally, tileCount
SortByImportance(input)
output = new Array<StreamTile>
tileCount = 1
While (input.length > 0)
(chunk, tally) = RemoveChunk(input, tileCount * tileSize)
// Prevent the last level from having under-sized tiles
While (tileCount > 1) And (tileCount * tileSize > tally)
tileCount = tileCount / 4
EndWhile
QuadSplit(chunk, tally, tileCount, output)
tileCount = tileCount * 4
EndWhile
Return output
EndFunction
Function RemoveChunk(Array<StreamObject> input, Integer chunkSize)
// Removes a chunk from a stream
// with respect to StreamObject payload size.
Array<StreamObject> output = new Array<StreamObject>
Integer tally = 0
While (input.length > 0 && tally < chunkSize)
StreamObject so = input.pop()
tally = tally + so.getPayloadSize()
output.push(so)
EndWhile
Return (output, tally)
EndFunction
Function SplitInHalf(Array<StreamObject> input, Integer totalSize)
// Splits a stream in half
// with respect to StreamObject payload size.
Array<StreamObject> half
(half, _) = RemoveChunk(input, totalSize / 2)
Return (input, half)
EndFunction
Function QuadSplit(Array<StreamObject> input, Integer tally,
Feathered Tiles 25
Integer tileCount, Array<StreamTile> output)
// Groups StreamObjects into StreamTile objects,
// partitioning the input in the X and Y dimensions.
Array<StreamObject> west, east, nw, ne, sw, se
If (input.length == 0) Then Return
If (tileCount == 1)
// All objects in a single tile
output.push( new StreamTile(input) )
Return
EndIf
SortByX(input)
(west, east) = SplitInHalf(input, tally)
SortByY(west)
SortByY(east)
(nw, sw) = SplitInHalf(west, tally/2)
(ne, se) = SplitInHalf(east, tally/2)
QuadSplit(nw, tally/4, tileCount/4, output)
QuadSplit(sw, tally/4, tileCount/4, output)
QuadSplit(ne, tally/4, tileCount/4, output)
QuadSplit(se, tally/4, tileCount/4, output)
EndFunction
Fig. 1. Example tile boundaries generated by the TileSplit algorithm overlayed on the
6-megabyte shapefile used to produce them
3.3 Tile Payloads
For a given collection of geometries, we run the TileSplit algorithm twice to
produce a set of metadata tiles and a set of geometry tiles. Keeping these separate
allows the client to request the metadata without requesting the geometry detail,
but a different implementation could combine all the information into one set
26 A. Dufilie and G. Grinstein
of tiles if desired. Each tile payload contains a stream of objects, and since the
byte-level details have no effect on the outcome we will only describe the contents
at an object level.
Metadata Tiles. Each object in a metadata tile corresponds to a geometry
and contains a shapeID (an integer), a shapeKey (a string) and a bounding
box (four coordinates). To simplify our storage model, our implementation also
includes shared metadata (projection and geometry type) in the first tile. It is
safe to do so because the first tile generated by our TileSplit algorithm covers
the entire (X, Y) range and has the highest importance range, and thus is always
requested by the client. If in the future we use a different TileSplit algorithm, we
may have to relocate this shared metadata. For use with the TileSplit algorithm,
each metadata object implements the StreamObject interface as follows:
x, y : Center coordinates of bounding box
importance : Area of bounding box
queryBounds : Equal to the bounding box
Geometry Tiles. The geometry tiles contain CombinedPoint objects which
correspond to (X, Y) locations appearing in the geometry data. A CombinedPoint object contains x, y, importance, and a list of (shapeID, vertexID) pairs.
This information is used for dynamically reconstructing the original geometries,
and is similar to a structure used by Zhang et al. [42] containing x, y, shapeID,
and vertexID. The added importance value allows us to perform on-the-fly generalization of individual geometries. We group vertices by (X, Y) location in
order to reduce the size of the final output for polygon collections that represent
geographic boundaries sharing common borders. For the TileSplit algorithm, the
CombinedPoint implements the StreamObject interface as follows:
x, y : Coordinates shared by all referenced vertices
importance : Highest importance value for any referenced vertex
queryBounds : Envelops the effective area of all referenced vertices
3.4 Minimizing Tile Overlap to Reduce Excess Data Transfer
When vertices from a single geometry are spread across multiple tiles in the X or
Y dimensions, vertices from some of the off-screen tiles may still be required to
correctly render the part of the geometry that is on-screen. Possible approaches
to this missing data problem include duplicating vertices across tiles, introducing new vertices at tile boundaries [22,7,18], and using overlapping tile query
bounds. Duplicating or creating additional vertices increases the size of each
tile unpredictably, which conflicts with our goal of creating tiles with uniform
payload size. Overlapping tile query bounds is the best approach in our case
as it does not add any additional complexity since our tile bounds are already
non-uniform.
The simplest way to ensure a tile is requested when it is required is to extend
the tile’s query bounds to envelop each geometry referenced in the tile. That is
Feathered Tiles 27
the approach used in a winged-edge topology [27,32], where each edge is associated with two polygons and the abox (area box) that envelops them is used
as filtering criteria. Though this approach solves the missing data problem it
creates the additional problem of excess data, since we do not necessarily need
all off-screen vertices in order to render a geometry correctly.
To reduce excess data transfer, we extend our tile’s query bounds to envelop
only the effective area of the included vertices rather than the bounds of the
referenced geometries. As mentioned in Sect. 3.1, the effective area of a vertex is
the area of the triangle it forms with its two adjacent vertices during the simplification process. This distinction is critical because this approach minimizes the
amount of tile overlap, which in turn reduces the amount of data the client will
download at a given scale and viewport, as illustrated in Sect. 6. The similarities
of our method to the winged-edge topology and the importance of this detail led
us to name our method Feathered Tiles.
4 Tile Management
This section describes the roles of the client and server when managing and requesting tiles. Our approach is client-heavy with few requirements of the server beyond
hosting the data, which allows servers to accommodate more simultaneous users.
4.1 Client Tile Requests
Each tile collection contains a list of tile descriptors, each of which includes
an ID number, bounding box coordinates, and an importance range. The client
first examines the tile descriptors to determine which tiles to request based on
the active scale and extent, much like the metadata file described by Zhang et
al. [42]. We index the tiles into a 5-dimensional KD-tree [3] with four dimensions
for the bounding box as done by Rosenberg [31] with a fifth dimension added for
the maximum importance value of the tiles. Other structures could conceivably
be used for this purpose such as range trees [4]. When performing a range query
on the tree, the minimum importance threshold is set to the area covered by a
single pixel in the viewport at the current scale. Thus all tiles with importance
equal to or greater than the current pixel area are caught by the query, ensuring
that the client will receive all the progressive refinements necessary to render
what is visible at the desired scale.
When the client changes its view parameters, it queries the tile tree for a list
of tiles required by the current view. If any tile references are found, they are
removed from the tile tree and requested from the server. Using this approach
tiles are requested only once. To account for interrupted downloads, the removed
tile references may be kept in a separate “pending” list so they can be added
back to the tile tree if their download did not complete.
4.2 Server Tile Management
Given that the client independently determines which tiles it needs, the server
component has very little additional requirements. A minimal server would
28 A. Dufilie and G. Grinstein
require no special services running. The tile descriptors could be stored in a
separate file in the same folder as the individual files for the tiles. In our implementation we store the tiles as rows in a database, indexed by their ID numbers.
The client is allowed to request multiple tiles at once, and the server responds by
concatenating the payload of each tile into a single stream. The advantage of this
approach is a reduced number of client-server round-trip communications. The
drawback is that the dynamic nature of the requests prevents the web browser
from caching the results. We were not particularly concerned with this aspect of
the architecture during development, but if we decide we want a cache-friendly
solution, we have that option. Note that a cache-friendly solution does not require the tiles to be stored as individual files on disk, since URL patterns can
be redirected to servlet calls, which would enable both SQL storage and browser
caching.
5 Client Processing and Rendering
When the client receives tiles from the server, it asynchronously parses the payload stream and dynamically builds data structures that facilitate on-the-fly
generalization with smooth levels of detail. This section explains how these structures are built and how they are used to improve the performance of the client.
5.1 View-Based Filtering
We use the same type of 5-dimensional KD-tree as described in Sect. 4.1 for
filtering geometric features based on the current scale and extent. Geometry
features outside the viewport or smaller than a single pixel are excluded from
the query result. The tree is built using the information included in the metadata
tiles (see Sect. 3.2) and is rebuilt every time we observe that the list of pending
metadata tiles has been completely parsed. Since optimally balanced KD-trees
are computationally expensive to build, we randomize the insertion order of
nodes as a fast alternative to avoid worst-case performance. Since there are much
fewer geometries than there are vertices, metadata tiles are requested nowhere
nearly as often as geometry tiles.
5.2 Implicit BLG-Trees for On-the-Fly Generalization
In order to achieve acceptable performance with highly detailed geometries, the
client must be able to generalize detailed polygons and polylines on the fly. In
Sect. 3.1 we explained that we can use the vertex importance values as filtering
criteria for line generalization. Therefore, we can derive simplified geometries by
skipping vertices with importance values below a given threshold. However, we
want to avoid checking the importance values of all the vertices if possible. For
that purpose, we generate BLG-trees [26] dynamically from the tiled geometry
data as it is received.
Feathered Tiles 29
The BLG-tree is traditionally used to store results from the Douglas-Peucker
(DP) line simplification algorithm [11] to facilitate on-the-fly generalization of
a polyline [26]. Each node of the BLG-tree contains coordinates and an error
threshold value for a single vertex in a polyline, and the tree is constructed
such that a full in-order traversal of the tree will visit every vertex of the original polyline in order. Generalization is achieved by skipping nodes with error
values below a desired threshold during an in-order traversal. Because the DP
algorithm is not guaranteed to produce error values in decreasing order [26],
the parent-child node relationships are a necessary part of the result and these
BLG-trees cannot be reconstructed from the DP algorithm’s error values and
vertex IDs alone. Because of this, BLG-tree structures are traditionally stored
on a server and transmitted to a client, adding undesirable communication and
administrative overhead [21].
In our case, we are able to implicitly derive BLG-trees from our importance
values and vertex IDs since we require that the importance values define the
ranking. No matter the order in which the data is received, a valid BLG-tree can
be dynamically constructed by inserting and rearranging nodes such that the
vertices appear in their original order and deeper nodes have lower importance
values. This is an atypical usage of the BLG-tree structure, since it has no
relation to the DP algorithm.
5.3 Off-screen Vertex Skipping
In early versions of our software we noticed that zooming in to large polygons
with thousands of vertices would slow down the rendering significantly. To prevent this from occurring, we eliminate unnecessary off-screen vertices in our
BLG-tree traversal routine by considering two parameters instead of one: minImportance, and visibleBounds. We use a variation of the Cohen-Sutherland [24]
algorithm to skip vertices that are outside the viewing rectangle. We do not perform clipping on line segments because we have not experienced any significant
performance hit resulting from a large, simplified portion of a polygon being
off-screen in Flash Player. The need for clipping should be re-assessed if the a
client is implemented in a different run-time environment.
During BLG-tree traversal, two flag values are kept for the two previous vertices added to the resulting node list. The flag values are generated by the
GridTest routine, shown below. The code snippet that follows is taken from the
BLG-tree traversal routine and shows how to use the GridTest result for skipping
vertices. To determine if a particular vertex can be skipped, we check the result
of applying the binary AND operator on three consecutive flag values. Section 6
gives sample results of this off-screen simplification process.
Pseudocode for the GridTest routine
Function GridTest(x, y, xMin, yMin, xMax, yMax)
// Returns a value to be ANDed with two previous results.
Return (x < xMin ? 0x0001 : (x > xMax ? 0x0010 : 0))
| (y < yMin ? 0x0100 : (y > yMax ? 0x1000))
30 A. Dufilie and G. Grinstein
EndFunction
Pseudocode for skipping off-screen vertices while traversing a BLG-tree structure
// Begin snippet for NodeVisit (not a stand-alone function)
If (visibleBounds != Null)
gridTest = visibleBounds.getGridTest(node.x, node.y)
If (prevPrevGridTest & prevGridTest & gridTest)
// Drop previous node.
// Keep current prevPrevGridTest value.
result.removeLast();
Else
// Don’t drop previous node.
// Shift prev grid test values.
prevPrevGridTest = prevGridTest;
EndIf
prevGridTest = gridTest;
EndIf
// append this node to the results
result.append(node);
// End snippet
There is one caveat to this vertex skipping process: In order to avoid seeing slivers of simplified off-screen lines, either the drawing routine must omit
off-screen line strokes or the visibleBounds parameter must be padded. The former approach is similar to how Langeld et al. [18] separates the border from
the fill, while the latter approach is used by Campin [7], TileStache [38], and
Polymaps [23].
6 Evaluation and Discussion
The benefits of progressive transmission and on-the-fly generalization for vector
data are well documented in related work [5,8,10,41]. Progressive transmission
reduces the amount of data required to be transferred, and on-the-fly generalization reduces the amount of data processed during rendering. However, the
effectiveness of these solutions depend greatly on the details of their implementation. When a web mapping client zooms far in to a highly detailed portion of
vector data, the client must make sure that it a) does not request more data
than necessary; and b) can efficiently render only the portion of data which is
visible.
Progressive transmission makes it possible to retrieve fully detailed geometry
data when required, but it is important to avoid excess data transfer. Nordan [25]
gives a perfect example of when this matters: “If the user was zoomed in to look
at the border between Russia and Finland, the considerable time and computing power required to download and assemble the entire outline of Russia at
that zoom level would be a complete waste.” In Sect. 3.4 we described how we
Feathered Tiles 31
minimize tile overlap to reduce excess data transfer. Using Nordan’s example,
we can see how much tile overlap matters. Figure 2 shows the borders of Norway, Finland, and Russia, and Table 1 shows the results of applying different
tile overlapping methods. If each tile’s query bounds is extended to include the
bounds of every referenced geometry (the winged method), the entire outlines of
the three countries are downloaded and parsed at the extent shown. Under the
Feathered Tiles method only 15% of the data is transmitted. Results will vary
with the tile payload size and input file, but Feathered Tiles will always produce
less tile overlap and in turn reduce excess data transfer.
Fig. 2. Displaying a 13-megabyte shapefile of countries of the world with 3-meter
accuracy, zoomed in to the borders of Norway, Finland, and Russia. At this extent,
only a small fraction of the data is required for rendering.
In the previous example, reducing the download size is only half the problem. Suppose that the client already had the full detail of the geometry cached
in memory as a result of panning along the borders, or the client has explicitly loaded a large, local shapefile into memory. In a highly detailed shapefile,
individual polygons may have thousands or millions of vertices. It’s clear that
an increased number of vertices will take a longer time to process, so it makes
sense not to waste time with off-screen vertices (OSVs). This problem is solved
by OSV skipping, described in Sect. 5.3. Figure 3 demonstrates two examples
before and after OSV skipping, with related statistics shown in Table 2.
32 A. Dufilie and G. Grinstein
Table 1. The method for determining tile query bounds greatly affects the amount of
excess data transfer in Fig. 2. The winged method extends the query bounds of a tile to
include the bounds of each referenced geometry, while the feathered method includes
only the effective area of the vertices contained within. In both cases, the target tile
payload size was set to 32-kilobytes.
Tile overlap method Overall tile overlap Tiles requested at
extent shown
Vertices received at
extent shown
Winged 405% 117 126,548
Feathered 3% 17 18,775
Fig. 3. Examples before (left) and after (right) off-screen vertex skipping when zoomed
in to Michigan (top) and Louisiana (bottom) shorelines. Off-screen portions are faded
out. The data comes from a 42-megabyte United States boundary shapefile. Only a
small fraction of the data is required to render the visible portion of the polygons.
Table 2. Skipping certain off-screen vertices in Fig. 3 allows correct rendering of
polygons using only a fraction of the data
Shoreline Total vertices at
scale shown
On-screen vertices
at extent shown
Percentage of vertices
required for rendering
Michigan 14,000 3,500 25%
Louisiana 10,000 1,500 15%
Feathered Tiles 33
7 Conclusion and Future Work
This paper presents Feathered Tiles, a novel approach for vector-based web
mapping which eliminates redundant data transfer and supports smooth zooming
operations with on-the-fly generalization. Tiles are partitioned to uniform byte
length which enables planned, predictable progressive transmission techniques.
One critical aspect of Feathered Tiles is the definition of the effective area of a
tile, which includes only the effective area of the vertices contained within the tile
rather than the bounds of the geometries it references. It has been demonstrated
that this decision can greatly reduce the amount of data requested by the client.
Finally, important client-side performance enhancements were outlined which
enable selective processing on large amounts of vector data for highly interactive
vector-based web-mapping.
There are several directions our future work can take. Firstly, different importance calculation methods can be used to improve preprocessing speed and
output quality. For example, the algorithm proposed by Buzer has a time complexity of O(n log n) and produces minimal representations of polylines targeted
for given pixel scales without introducing visible topological inconsistencies [6].
Another possibility is to eliminate the need for tile descriptors. The client request would then consist of a data range, a scale, and a bitmask for filtering out
the tiles it has or is currently receiving. With some polishing, our tiling method
could be encapsulated in a new standalone file format to facilitate on-the-fly exploration and generalization of large geometry sets. To tackle the issue of large
geometry sets exceeding the memory capacity of lower-end machines, a method
for freeing unused parts of the cache could be developed. We could also consider
using a more adaptive tiling method [2,13] to further reduce excess data transfer.
Finally, different encoding methods for data compression could be explored. For
example, grouping vertices by geometry ID or importance value rather than x,y
pairs may improve the storage efficiency.
References
1. Antoniou, V., Morley, J., Haklay, M(M.): Tiled vectors: A method for vector transmission over the web. In: Carswell, J.D., Fotheringham, A.S., McArdle, G. (eds.)
W2GIS 2009. LNCS, vol. 5886, pp. 56–71. Springer, Heidelberg (2009)
2. The Astrophysical Research Consortium: Tiling and Adaptive Tiling. The Sloan
Digital Sky Survey Project Book. Princeton University (1993), http://www.
astro.princeton.edu/PBOOK/tiling/tiling.htm
3. Bentley, J.L.: Multidimensional binary search trees used for associative searching.
Communications of the ACM 18(9), 509–517 (1975)
4. Bentley, J.L., Friedman, J.H.: Data Structures for Range Searching. ACM Comput.
Surv. 11(4), 397–409 (1979)
5. Bertolotto, M., Egenhofer, M.J.: Progressive transmission of vector map data over
the world wide web. GeoInformatica 5(4), 345–373 (2001)
6. Buzer, L.: Optimal simplification of polygonal chains for subpixel-accurate rendering. Computational Geometry 42(1), 45–59 (2009), http://dx.doi.org/10.1016/
j.comgeo.2008.03.002
34 A. Dufilie and G. Grinstein
7. Campin, B.: Use of vector and raster tiles for middle-size Scalable Vector Graphics mapping applications. In: SVGOpen 2005 (2005), http://www.svgopen.org/
2005/papers/VectorAndRasterTilesForMappingApplications/
8. Corcoran, P., Mooney, P., Bertolotto, M., Winstanley, A.: View- and scale-based
progressive transmission of vector data. In: Murgante, B., Gervasi, O., Iglesias,
A., Taniar, D., Apduhan, B.O. (eds.) ICCSA 2011, Part II. LNCS, vol. 6783, pp.
51–62. Springer, Heidelberg (2011)
9. Corcoran, P., Mooney, P., Bertolotto, M.: Line simplification in the presence of nonplanar topological relationships. In: Bridging the Geographic Information Sciences,
pp. 25–42. Springer, Heidelberg (2012), doi: http://dx.doi.org/10.1007/978
-3-642-29063-3 2
10. Costa, D.C., Teixeira, M.M., De Paiva, A.C., de Souza Baptista, C.: A serviceoriented architecture for progressive transmission of maps. In: Proceedings of IX
Brazilian Symposium on GeoInformatics, INPE 2007. GeoInfo, Campos do Jord˜ao,
Brazil, November 25-28, pp. 97–108 (2007)
11. Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points
required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization 10(2), 112–122
(1973)
12. Dufilie, A., Fallon, J., Stickney, P., Grinstein, G.: Weave: A Web-based Architecture
Supporting Asynchronous and Real-time Collaboration. In: Proceedings of the AVI
Workshop on Supporting Asynchronous Collaboration in Visual Analytics Systems
(2012)
13. Environmental Systems Research Institute, Inc.: Tiled processing of large datasets.
ArcGIS Desktop 8.3 Help (2009), http://webhelp.esri.com/arcgisdesktop/9.3
/index.cfm?TopicName=Tiled+processing+of+large+datasets
14. GeoJSON – JSON Geometry and Feature Description, http://geojson.org/
15. GIS Cloud, http://www.giscloud.com/
16. Han, H., Tao, V., Wu, H.: Progressive vector data transmission. In: Proceedings of
the 6th AGILE, Lyon, France, pp. 103–113 (2003)
17. Haunert, J.H., Dilo, A., van Oosterom, P.: Constrained set-up of the tGAP structure for progressive vector data transfer. Computers and Geosciences 35(11), 2191–
2203 (2009)
18. Langfeld, D., Kunze, R., Vornberger, O.: SVG Web Mapping. Four-dimensional
visualization of time- and geobased data. In: SVGOpen 2008 (2008),
http://www.svgopen.org/2008/papers/92-SVG_Web_Mapping/
19. Mapsforge, http://code.google.com/p/mapsforge/wiki/
SpecificationBinaryMapFile
20. Meijers, M.: Cache-friendly progressive data streaming with variable-scale data
structures. In: Proceedings of the ICA/ISPRS Workshop on Generalisation and
Multiple Representation, Paris, France, June 30-July 1 (2011)
21. Meijers, M.: Simultaneous & topologically-safe line simplification for a variablescale planar partition. In: Advancing Geoinformation Science for a Changing
World, pp. 337–358. Springer, Heidelberg (2011)
22. Migurski, M.: TileStache Mailing List (July 19, 2011),
https://groups.google.com/d/msg/tilestache/p7OotBbz5tE/clvzx0YAtUYJ
23. Migurski, M.: StackExchange answer (November 22, 2010), http://gis.
stackexchange.com/questions/3712/create-vector-tiles-for-polymaps
24. Newman, W.M., Sproull, R.F.: Principles of interactive computer graphics, 124,
252. McGraw-Hill, Inc. (1979)
Feathered Tiles 35
25. Nordan, R.P.V.: An Investigation of Potential Methods for Topology Preservation
in Interactive Vector Tile Map Applications. Master Thesis. Norwegian University
of Science and Technology (2012)
26. van Oosterom, P., Van Den Bos, J.: An object-oriented approach to the design of
geographic information systems. Computers and Graphics 13(4), 409–418 (1989)
27. van Oosterom, P.: Variable-scale topological data structures suitable for progressive data transfer: The GAP-face tree and GAP-edge forest. Cartography and
Geographic Information Science 32(4), 331–346 (2005)
28. Vector Tiles - OpenStreetMap Wiki, http://wiki.openstreetmap.org/wiki/
Vector tiles
29. Polymaps, http://www.polymaps.org
30. Ravnic, D.: Re: GisCloud showing tons of vectors features on Web Browser.
OpenLayers-Users mailing list (September 23, 2011), http://lists.osgeo.org/
pipermail/openlayers-users/2011-September/022351.html
31. Rosenberg, J.B.: Geographical data structures compared: A study of data structures supporting region queries. IEEE Transactions on Computer-Aided Design of
Integrated Circuits and Systems 4(1), 53–67 (1985)
32. Samet, H.: Foundations of Multidimensional and Metric Data Structures, pp. 317–
329 (2006)
33. Slippy Map Tilenames, http://wiki.openstreetmap.org/wiki/Slippy map
tilenames
34. Schmalstieg, D., Schaufler, G.: Smooth levels of detail. In: Virtual Reality Annual
International Symposium, pp. 12–19. IEEE (March 1997)
35. Schmid, F., Janetzek, H., Wladysiak, M., Hu, B.: OpenScienceMap: open and free
vector maps for low bandwidth applications. In: Proceedings of the 3rd ACM Symposium on Computing for Development. ACM, New York (January 2013)
36. Scalable Vector Graphics. Wikipedia entry, http://en.wikipedia.org/wiki/
Scalable Vector Graphics
37. TileMill2, https://github.com/mapbox/tm2
38. TileStache documentation. TileStache.Vector, http://tilestache.org/doc/
TileStache.Vector.html (accessed June 2013)
39. Visvalingam, M., Whyatt, J.D.: Line generalisation by repeated elimination of
points. The Cartographic Journal 30(1), 46–51 (1993)
40. Weave: Web-based Analysis and Visualization Environment,
http://www.oicweave.org
41. Yang, B.S., Purves, R.S., Weibel, R.: Implementation of progressive transmission algorithms for vector map data in web-based visualization. The International
Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences
34. Part XXX (2004)
42. Zhang, L., Zhang, L., Ren, Y., Guo, Z.: Transmission and visualization of large
geographical maps. ISPRS Journal of Photogrammetry and Remote Sensing 66(1),
73–80 (2011)