Package com.here.platform.location.inmemory.geospatial

Class GeometryTile

java.lang.Object
com.here.platform.location.inmemory.geospatial.GeometryTile
public class GeometryTile extends Object
Contains the road geometry data for a single tile.

In HERE Map Content, a road segment is the unbroken stretch of road between two intersections. The intersections are called nodes.

The geometry of a road segment is a line-string, a sequence of points, starting from the segment's start node and ending with its end node.

A segment geometry consists of a sequence of one or more adjacent segment geometry chunks. Each chunk is a pair of subsequent points of a segment geometry. That means, that the n-th chunk of a segment's geometry consists of points n and n+1 in that geometry.

Road Segment Geometries

Every GeometryTile t1 contains geometries for two kinds of segments.

  • Segments that belong to tile t1 (internal segments).
  • Segments that belong to some other tile t2 but whose geometry is partially inside tile t1 (external segments).

These geometries are stored in segmentGeometryCoordinates in the following order:

  • First, for the internal segments, stored in the same order as the Vertices corresponding to these segments in the GraphTile with the same ID.
  • Then, for the external segments, ordered by the (tileId, localIndex) for each external segment.

To determine which points inside segmentGeometryCoordinates constitute the geometry for a segment we need to consult segmentGeometryFirstCoordinateIndices. For example, the geometry of the segment with index n starts at the point with index segmentGeometryFirstCoordinateIndices(n) and ends at the point with index segmentGeometryFirstCoordinateIndices(n+1) (exclusive). This implies that the first entry of segmentGeometryFirstCoordinateIndices will always be 0 and the last entry will always be segmentGeometryCoordinates.length.

Point Encoding

GeometryTiles contain points to represent segment geometries (in segmentGeometryCoordinates) and to represent bounding boxes (in boundingBoxCoordinates). All these points are stored as 64 bit integers. This representation consumes a lot less memory than, for example a pair of doubles. More importantly, because integers are primitive types, they usually don't need an object to be created for them and, as a consequence, are a lot faster to work with.

A point is usually represented by a GeoCoordinate object containing a longitude and a latitude.

In order to pack these coordinates into an integer, multiply each coordinate by 1000000 and convert it to an integer. The two integer coordinates then become the high (latitude) and low (longitude) bits of a long: 


       packed_representation = (latitude*1E6).toLong << 32) | (longitude*1E6).toLong & 0xFFFFFFFFL)

This packing means that the precision of each coordinate is one millionth of a degree, which is around 10 cm.

To reconstruct the original point, apply the inverse transformation: 


 latitude = (packed_representation >> 32) / 1E6
 longitude = (packed_representation & 0xFFFFFFFFL).toInt / 1E6

External Segments

Every GeometryTile may contain some geometries for segments external to that tile (see above). In order to find out which tile an external segment belongs to and what its index in that tile is, you need to consult externalSegmentPartitions and externalSegmentLocalIndices. These are parallel arrays that contain the tile ID and segment index, respectively, for each external segment.

External segments are always the last segments in a tile. That means, you can decide whether a segment is external, just by looking at its index. The segment with index n is external, if n >= internalSegmentCount.

The ID of the tile that this external segment belongs to is externalSegmentPartitions(n - number_of_internal_segments) and its index there externalSegmentLocalIndices(n - number_of_internal_segments).

The Spatial Index

In order to quickly find segments in a particular area, GeometryTiles contain a spatial index. The spatial index is a tree data structure where every internal node is associated with a bounding box around all its children. Using the bounding boxes while traversing the tree, you can quickly decide whether a sub-tree might contain segment geometries relevant to your search and avoid descending into it, if it does not.

A leaf node in the tree (a node without child nodes) points to a single chunk inside a segment geometry in this tile.

The structure of the tree is stored in indexTree. The tree contains indexTree.length - 1 nodes. For a tree node with index m, the range from indexTree(m) to indexTree(m+1) (exclusive) contains the indices of its child nodes. In particular, if indexTree(m) == indexTree(m+1), the node is a leaf node. The node with index 0 is the tree's root node indexTree. The first entry in indexTree is always 1 and the last entry always indexTree.length.

Each node in indexTree is associated with two values in indexValues. For an internal (non-leaf) tree node with index n, indexValues(2*n) contains the index of a bounding box in boundingBoxCoordinates. Because two points are required for storing each bounding box, the index of a bounding box will always be even. For a leaf node with index n, indexValues(2*n) contains a segment index in this tile and indexValues(2*n+1) a chunk index inside the geometry for that segment.

Cumulative Chunk Lengths

For every chunk in every segment geometry, cumulativeChunkLengths contains the sum of the length of that chunk and the lengths of all previous chunks in the segment (inclusive prefix sum). The cumulative chunk lengths can be used to calculate the distance fraction for a point on a segment's geometry. The distance fraction (or simply fraction) for a point on a segment is the ratio between the distance you need to travel along a segment from the beginning of the segment to reach that point and the length of the segment.

A segment whose geometry consists of p points, always has p-1 chunks. To retrieve the cumulative chunk length for the chunk with index c in the segment with index n, you therefore need to use the following index into cumulativeChunkLengths: 


   length_index = segmentGeometryFirstCoordinateIndices(n) - n + c
   cumulative_chunk_length = cumulativeChunkLengths(length_index)

The cumulative chunk length of a segment's last chunk is also the total length of the segment. 


   segment_length = cumulativeChunkLengths(segmentGeometryFirstCoordinateIndices(n + 1) - n - 2)

param: segmentGeometryCoordinates The geometries (line-strings) for road segments in this tile. Each entry represents a point param: segmentGeometryFirstCoordinatesIndices The start index for each segment's geometry in segmentGeometryCoordinates param: externalSegmentPartitions For each external segment, the ID of the tile it belongs to. An external segment is a segment that does not belong to this tile, but whose geometry is partially inside this tile param: externalSegmentLocalIndices For each external segment, its index in the tile it belongs to. An external segment is a segment that does not belong to this tile, but whose geometry is partially inside this tile param: boundingBoxCoordinates The bounding boxes used in this tile's index tree. Each bounding box is stored as a pair of points, one for the south-west corner and one for the north-east corner, in that order param: indexTree The tree structure used as this tile's spatial index param: indexValues The values associated with each node in this tile's spatial index param: cumulativeChunkLengths The sum of the length of each segment geometry chunk and the lengths of all previous chunks in a segment's geometry, in millimeters

Note:
Although this object contains Arrays, you should treat it as immutable.

  • Constructor Details

    • GeometryTile

      public GeometryTile(TileId tileId, int[] segmentGeometryFirstCoordinatesIndices, int[] externalSegmentPartitions, int[] externalSegmentLocalIndices, long[] boundingBoxCoordinates, long[] segmentGeometryCoordinates, int[] indexTree, int[] indexValues, int[] cumulativeChunkLengths)

  • Method Details

    • chunkLengthToMeters

      public static double chunkLengthToMeters(int chunkLength)
      Converts a length value from GeometryTile.cumulativeChunkLengths to a value in meters.

    • metersToChunkLength

      public static int metersToChunkLength(double meters)
      Converts a length value in meters to a value suitable for GeometryTile.cumulativeChunkLengths.

    • ChunkLengthCalculatorSinusoidalProjectionCenteredOnChunkFirstPoint

      public static ProjectionDistanceCalculator ChunkLengthCalculatorSinusoidalProjectionCenteredOnChunkFirstPoint()
      The chunk length calculator used by the Optimized Map Compiler, and TiledGeometryPropertyMap

    • tileId

      public TileId tileId()

    • segmentGeometryFirstCoordinatesIndices

      public int[] segmentGeometryFirstCoordinatesIndices()

    • externalSegmentPartitions

      public int[] externalSegmentPartitions()

    • externalSegmentLocalIndices

      public int[] externalSegmentLocalIndices()

    • boundingBoxCoordinates

      public long[] boundingBoxCoordinates()

    • segmentGeometryCoordinates

      public long[] segmentGeometryCoordinates()

    • indexTree

      public int[] indexTree()

    • indexValues

      public int[] indexValues()

    • cumulativeChunkLengths

      public int[] cumulativeChunkLengths()

    • internalSegmentCount

      public int internalSegmentCount()
      The number of segments in this tile.

      The number of internal segments is calculated as segmentGeometryFirstCoordinatesIndices.length - externalSegmentPartitions.length - 1.