インメモリタイル

このinmemoryモジュールには 、コア インターフェイスを実装する効率的なインメモリデータ構造が含まれています。

libraryDependencies ++= Seq(
  "com.here.platform.location" %% "location-inmemory" % "0.21.788"
)

<dependencies>
    <dependency>
        <groupId>com.here.platform.location</groupId>
        <artifactId>location-inmemory_${scala.compat.version}</artifactId>
        <version>0.21.788</version>
    </dependency>
</dependencies>

dependencies {
    compile group: 'com.here.platform.location', name: 'location-inmemory_2.12', version:'0.21.788'
}

グラフと TiledGraph

パーティション分割方式を使用すると、非常に大きいルーティンググラフをパーティションできます。 分割スキームは、グラフのどの部分がどのパーティションに移動するかを指定します。 ルーティンググラフは 、グラフのプリミティブに関連付けられた地理的な場所と、各パーティションのバウンディング ボックスに基づいて、遺伝的パーティション分割方式に従って分割されます。 特に、ジオコード化された座標の 2D スペースは四角形のタイルに分割され、同じタイルの境界内にあるグラフプリミティブは同じパーティションに移動します。

TiledGraph は 、圧縮されたスパース行形式のデータのロケーション ライブラリ DirectedGraph 抽象化を実装します。

特に 、 TiledGraph は分割されたインシデントグラフを表します。

発生率グラフは、頂点で 1 つの操作のみをサポートするグラフです。つまり、頂点から出るエッジを取得します。 これを効率的に実装するには、開始頂点のある送信エッジを同じパーティションに保存します。 送信エッジは、同じパーティションにない頂点で終了することがあります。

TiledGraph は、パーティション間の遷移を透過的に処理します。 たとえば、シームレスなグラフトラバーサルの場合 、次のように 2 つの GraphTile から TiledGraph を作成できます。

import com.here.platform.location.inmemory.geospatial.TileId
import com.here.platform.location.inmemory.graph._

// Create the graph p3(1) <-- p1(0) --> p2(0).
val graph1 = new GraphTile(TileId(1),
                           firstEdgeIndices = Array(0, 2),
                           edges = Array(1, 2),
                           externalVertexTileIds = Array(2, 3),
                           externalVertexIndices = Array(0, 1))
val graph2 = new GraphTile(TileId(2),
                           firstEdgeIndices = Array(0, 0),
                           edges = Array.empty,
                           externalVertexTileIds = Array.empty,
                           externalVertexIndices = Array.empty)
// Only partition 1 and 2 are present.
val graphTiles =
  Map(graph1.tileId -> graph1, graph2.tileId -> graph2)

val graph = new TiledGraph(graphTiles.get)

val p1v0 = Vertex(TileId(1), VertexIndex(0))
val edges: Iterable[Edge] = graph.outEdgeIterator(p1v0).toIterable

println(s"$p1v0 has ${edges.size} outgoing edges: ...")

val p2v0 = graph.target(edges.head)
println(s"... one to $p2v0")

val p2v0edges = graph.outEdgeIterator(p2v0)
println("which can be expanded")

完全なグラフが含まれていない TiledGraph を探索しても、不足しているパーティションが見つかることがあります。 たとえば、特定の領域のルーティンググラフを探索しているときに、その領域の外側にある頂点に達することがあります。 通常 の TiledGraph では例外がスローされます。

val p3v1 = graph.target(edges.last)
println(s"... and one to $p3v1")
try {
  graph.outEdgeIterator(p3v1)
} catch {
  case _: NoSuchElementException =>
    println("which cannot be expanded")
    println("because its partition is not present")
}

これらの頂点をフィルターで除外する場合は 、 TiledGraphwithTiledGraph.CutBorders を作成できます

val cutGraph = new TiledGraph(graphTiles.get) with TiledGraph.CutBorders

val cutEdges = cutGraph.outEdgeIterator(p3v1)
println(s"... unless we cut the graph's borders")
assert(cutEdges.isEmpty)
println("in which case the missing vertex will have no outgoing edges")

頂点

グラフの頂点に関連付けられている情報を取得するに は、頂点を PropertyMap のキーとして使用します。

頂点は、その パーティション内のグラフパーティション（ TileId で表されます）とそのインデックス（ vertexIndex で表されます）によって一意に識別されます。

TileResolver

タイリングされたマップにアクセスするには、必要なパーティションのタイル ID を計算する方法が必要です。 使用しようとしているマップ データのパーティション分割方式またはタイルレベルを事前に把握できないため、この機能を一般的に実装する方法はありません。 そのため 、さまざまなエリアクエリのタイル ID を計算できる TileResolver を使用する必要があります。

import com.here.platform.location.inmemory.geospatial.TileResolver
import com.here.platform.location.integration.herecommons.geospatial.{
  HereTileLevel,
  HereTileResolver
}

// Construct a resolver for the HEREtile scheme on level 14
val outputLevel = HereTileLevel(14)
val resolver: TileResolver = new HereTileResolver(outputLevel)

import com.here.platform.location.integration.herecommons.geospatial.HereTileLevel;
import com.here.platform.location.integration.herecommons.geospatial.javadsl.HereTileResolver;
// Construct a resolver for the HEREtile scheme on level 14
HereTileLevel outputLevel = new HereTileLevel(14);
HereTileResolver resolver = new HereTileResolver(outputLevel);

次のスニペットは、クエリの例を示しています。

• ポイントで検索 :

  Scala

  Java

  import com.here.platform.location.core.geospatial.GeoCoordinate
  
  val point = new GeoCoordinate(latitude = 0.0, longitude = 53.0)
  val pointTile = resolver.fromCoordinate(point)
  
  println(s"The $point is inside the level ${outputLevel.value} tile with id ${pointTile.value}")
    

  import com.here.platform.location.core.geospatial.GeoCoordinate;
  GeoCoordinate point = new GeoCoordinate(0.0, 53.0);
  long pointTile = resolver.fromCoordinate(point);
  
  System.out.printf(
      "The %s is inside the level %s tile with id %s%n", point, outputLevel.value(), pointTile);

• 半径で検索 :

  Scala

  Java

  val radiusInMeters = 1000.0
  val radiusTiles = resolver.fromCenterAndRadius(point, radiusInMeters)
  
  println(s"The following tiles are within $radiusInMeters meters of $point:")
  radiusTiles.foreach(println)
    

  double radiusInMeters = 1000.0;
  Set<Long> radiusTiles = resolver.fromCenterAndRadius(point, radiusInMeters);
  
  System.out.printf(
      "The following tiles are within %s meters of %s: %s%n", radiusInMeters, point, radiusTiles);

• バウンディングボックスで検索 :

  Scala

  Java

  import com.here.platform.location.core.geospatial.BoundingBox
  
  val bb = BoundingBox(northLatitude = 52.53047,
                       southLatitude = 52.51708,
                       westLongitude = 13.39632,
                       eastLongitude = 13.42293)
  
  val bbTiles = resolver.fromBoundingBox(bb)
  
  println(s"The following tiles are intersecting $bb:")
  bbTiles.foreach(println)
    

  import com.here.platform.location.core.geospatial.BoundingBox;
  BoundingBox bb = new BoundingBox(52.53047, 52.51708, 13.42293, 13.39632);
  Set<Long> bbTiles = resolver.fromBoundingBox(bb);
  
  System.out.printf("The following tiles are intersecting %s: %s%n", bb, bbTiles);

HereTileResolver では、次のクエリを使用して、指定したタイルでカバーされているバウンディング ボックスを取得できます。

val boundingBox = HereTileResolver.boundingBoxOf(pointTile)

println(s"The following bbox are covered by tile ${pointTile.value}: $boundingBox")

import com.here.platform.location.core.geospatial.BoundingBox;
BoundingBox boundingBox = HereTileResolver.boundingBoxOf(pointTile);

System.out.printf("The following bbox are covered by tile %s: %s%n", pointTile, boundingBox);

圧縮されたスパース行グラフ形式

Compressed Sparse Row （ CSR ）形式 は、マトリックスおよびグラフの効率的なストレージ形式です。 この形式のロケーション ライブラリバリアントでは、各パーティションは 4 つの整数配列で構成されています。

• firstEdgeIndices： 各内部頂点の最初のエッジのインデックス
• エッジ : 各エッジの移動先の頂点インデックス
• パーティション ID: このパーティションから参照されているすべての外部頂点のパーティション ID
• 頂点インデックス: すべての外部頂点の各パーティションの頂点インデックス

頂点のインデックス 0 ～ firstEdgeIndices.length - 2 は内部の頂点 ( このパーティションの頂点 ) を参照しています。

の最後のエントリ firstEdgeIndices は常にです edges.length。

そのため、の各エントリ firstEdgeIndices は、前の頂点の最後のエッジの後にあるエッジのインデックスになります。

その結果、インデックスのある特定の内部頂点から開始するエッジ idx は firstEdgeIndices(idx) 、インデックスの範囲（両端を含む）から firstEdgeIndices(idx + 1) （排他的）までによって決定されます。

firstEdgeIndices.length - 1 を経由する頂点のインデックス firstEdgeIndices.length + partitionIds.length - 2 は、外部の頂点（このパーティションの外側にある、このパーティションの内側から参照される頂点）を参照します。 したがって、外部頂点の数はです partitionIds.length。

v インデックスのある頂点の idx場合、次の条件が有効です。

• idx < firstEdgeIndices.length - 1vが 現在のグラフパーティションにある場合。

• それ以外の場合は v 、 ID を持つパーティションに属します partitionIds(idx - firstEdgeIndices.length + 1)

そのパーティションのインデックスがです vertexIndices(idx - firstEdgeIndices.length + 1)。

例

次の図は、特定のグラフのパーティション 1 を示しています。

CSRG 形式は、このパーティションを次のように表します。

グラフパーティションを復元するには、その CSRG の表現を確認します。

v(i) インデックスiのある頂点にしましょ う。v(0)インデックス 0 の頂点、v(1)インデックス 1 の頂点などです。

1. このパーティションで定義されている内部頂点の数と、参照している外部頂点を確認します。

   firstEdgeIndices.length - 1 は 3 であるため、頂点 v(0)v(1)および v(2) は現在のパーティションに属しています。

   頂点 v(3) は partitionIds(0) 、インデックス位置のパーティションの外部頂点（ vertexIndices(0)パーティション 24 およびインデックス 13 ）に対応しています。

   同様 に、頂点v(4)はインデックスの頂点（パーティションpartitionIds(1) at index vertexIndices(1)）の外部頂点であり、パーティション 42 およびインデックス 9 です。

2. グラフのエッジを再構築します。 すべての内部頂点について、その外向きのエッジをデコードします。

   v(0)の発信エッジ には、 [0,1] の範囲のインデックスがあり ます ( 両端を含むfirstEdgeIndices(0)からfirstEdgeIndices(1)排他的 ) 。 したがって、頂点にはインデックス 0 の単一の外向きエッジがあり 、エッジのターゲットは vertexv(edges(0))==v(2). になります。

   v(1)の発信エッジ には、 ( 空の ) 範囲 [1,1] のインデックスがあり ます ( 両端を含むfirstEdgeIndices(1)からfirstEdgeIndices(2)排他的 ) 。 したがって、頂点には外向きのエッジがありません。

   同様 に、v(2)の出力エッジには、ターゲットの頂点v(edges(1))およびv(edges(2)) -- v(4)頂点およびv(3) -- に対応する範囲のインデックスが [1,3] にあります。