Vector-based map cutting: In the context of cloud-based navigation systems

Abstract

Vector maps are used when describing real world geographical objects, such as lakes or roads, with the convenience of vectors and vector objects. Each vector, or coordinate, describes a geographical point. Two or more vectors describe a line, or polyline, and three or more cordinates can describe a polygon. A lake can thus be described by a polygon with coordinates mapping its boundary, while a road can be described by a polyline with coordinates mappings its stretch. When dealing with vector map objects you often bound the geographical area of interest by a bounding polygon. In its simplest form this is a bounding box, but arbitrarily shaped polygons can be used as well. This thesis report examines how vector map objects in form of polylines and polygons can be cut out from arbitrarily formed polygons. It also describes how the arbitrarily formed polygons in turn can be created by splitting up a corridor surrounding a polyline, the corridor created by offsetting the polyline to each of its sides. It goes into details on algorithms used for polygon clipping and polyline offsetting. The report also covers implementation of selected approaches into a vector map based mobile navigation system, as well as benchmarking and testing of it.