マーカーは良いことです。合理的な量で有用です。それらの数が多すぎると、利点はなくなります。何万ものオブジェクトがある地図で検索結果をマークしたい場合はどうしますか？この記事では、外観とパフォーマンスを犠牲にすることなく、WebGLカードでこの問題を解決する方法を説明します。

背景

2016年、2GISは最初のWebGLプロジェクト-Floors：建物の3Dフロアプランを開始しました。

ノボシビルスクショッピングセンターオーラのフロア

Floorsのリリース直後に、私たちのチームはWebGLで本格的な3次元地図作成エンジンの開発を開始しました。このエンジンは、新しいバージョン2gis.ruとともに開発され、現在はパブリックベータステータスになっています。

WebGLに描かれた赤い正方形。 建物の計画がマップに直接統合されました。

署名一般化タスク

独自のマップエンジンを作成したい人は、遅かれ早かれ、マップに署名を配置する問題に直面します。マップ上には多くのオブジェクトがあり、署名が互いに交差しないように各オブジェクトに署名することは不可能です。

ノボシビルスクですべてのオブジェクトに一度に署名するとどうなりますか

この問題を解決するには、署名の一般化が必要です。一般的な意味での一般化とは、小さな縮尺での表示に適したマップデータの変換です。さまざまな方法で実行できます。署名の場合、通常は選択方法が使用されます。総数から、重複しない最も優先度の高い署名のサブセットが選択されます。

署名の優先度は、そのタイプと現在のマップ縮尺によって決まります。たとえば、小規模では都市と国の署名が必要であり、大規模では道路の署名と家番号がはるかに重要になります。多くの場合、集落の名前の優先順位は、その人口の規模によって決まります。大きいほど、署名が重要になります。

署名だけでなく、マップ上の検索結果をマークするマーカーにも一般化が必要です。たとえば、モスクワで「店舗」を検索すると、15,000件以上の結果があります。それらをすべてマップ上で一度にマークすることは明らかに悪い考えです。

マップ上のすべてのモスクワ店。 一般化せずに行う方法はありません

ユーザーがマップを操作（移動、ズーム、回転、傾斜）すると、画面上のマーカーの位置が変化するため、その場で汎化を再計算できる必要があります。したがって、高速でなければなりません。

この記事では、マーカーの一般化の例を使用して、この問題を解決するさまざまな方法を示します。これらの方法は、プロジェクトでさまざまな時に使用されていました。

一般化への一般的なアプローチ

画面の平面に各マーカーを投影し、境界を計算します。境界は、画面上でマーカーが占める長方形の領域です。
優先度でマーカーを並べ替えます。
各マーカーを順番に調べ、そのマーカーがその前に配置されている他のマーカーと交差しない場合は、画面上に配置します。

ポイント1では、すべてが明確です-それは単なる計算です。パラグラフ2では、ラッキーでした。バックエンドから表示されるマーカーのリストは、検索アルゴリズムによって優先度で既にソートされています。ユーザーが関心を持ちそうな最も関連性の高い結果は、結果の最上部にあります。

主な問題はパラグラフ3にあります。一般化計算時間は、実装方法に大きく依存します。

マーカー間の交差を検索するには、次のようなデータ構造が必要です。

画面に追加されたマーカーの境界を保存します。
画面にマーカーを追加するinsert(marker)

メソッドがあります。
画面に既に追加されているマーカーとの交差のマーカーをチェックするためのcollides(marker)

メソッドがあります。

この構造のいくつかの実装を検討してください。それ以降の例はすべてTypeScriptで記述され、ほとんどのプロジェクトで使用されます。すべての例で、マーカーは次の形式のオブジェクトで表されます。

 interface Marker { minX: number; maxX: number; minY: number; maxY: number; }

考慮されるすべてのアプローチは、次のインターフェイスの実装になります。

 interface CollisionDetector { insert(item: Marker): void; collides(item: Marker): boolean; }

パフォーマンスを比較するために、次のコードの実行時間が測定されます。

 for (const marker of markers) { if (!impl.collides(marker)) { impl.insert(marker); } }

markers

配列には、1920x1080サイズの平面にランダムに配置された100,000個の30x50要素が含まれます。

パフォーマンスは、2012 Macbook Airで測定されます。

記事で提供されているテストとコード例もGitHubに投稿されています。

素朴な実装

まず、単純なサイクルでマーカーと他のマーカーとの交差をチェックするときに、最も単純なオプションを検討します。

 class NaiveImpl implements CollisionDetector { private markers: Marker[]; constructor() { this.markers = []; } insert(marker: Marker): void { this.markers.push(marker); } collides(candidate: Marker): boolean { for (marker of this.markers) { if ( candidate.minX <= marker.maxX && candidate.minY <= marker.maxY && candidate.maxX >= marker.minX && candidate.maxY >= marker.minY ) { return true; } } return false; } }

100,000マーカーの一般化計算時間： 420ミリ秒 。多すぎる。一般化の計算がウェブワーカーで実行され、メインスレッドをブロックしない場合でも、特にカードの移動後にこの操作を実行する必要があることを考えると、このような遅延は目で確認できます。さらに、プロセッサが弱いモバイルデバイスでは、遅延がさらに大きくなる可能性があります。

Rツリーの実装

単純な実装では、各マーカーは以前のすべてのマーカーとの交差をチェックするため、最悪の場合、このアルゴリズムの複雑さは2次です。 Rツリーのデータ構造を適用することで改善できます。 Rツリーの実装として、 RBushライブラリを使用します。

 import * as rbush from 'rbush'; export class RTreeImpl implements CollisionDetector { private tree: rbush.RBush<Marker>; constructor() { this.tree = rbush(); } insert(marker: Marker): void { this.tree.insert(marker); } collides(candidate: Marker): boolean { return this.tree.collides(candidate); } }

100,000マーカーの一般化計算時間： 173ミリ秒 。大幅に改善されました。 Floorsでこのアプローチを使用しました（これは以前の記事で言及しました）。

Rツリー内のポイントのストレージの視覚化。 平面を長方形に階層的に分割することにより、すべてのオブジェクトをソートするのではなく、検索エリアをすばやく絞り込むことができます

衝突バッファの実装

地図の描画は、1つの建物の計画を描画するよりもはるかに複雑なタスクです。これは一般化にも現れます。世界最大のショッピングセンターでさえ、1,000の組織が同じ階にいることはめったにありません。同時に、大都市での単純な検索クエリは、何万もの結果を返す可能性があります。

WebGLマップの開発を始めたとき、私たちは考え始めました：一般化をスピードアップすることはまだ可能ですか？私たちのために働いたステラレーターによって興味深いアイデアが提供されました。Rツリーの代わりに、画面の各ピクセルの状態（ビジーまたはビジーでない）を格納するバッファーを使用します。画面にマーカーを挿入するときは、バッファ内の対応する場所を「塗りつぶし」、貼り付けの可能性を確認するときは、必要な領域のピクセル値を確認します。

 class CollisionBufferByteImpl implements CollisionDetector { private buffer: Uint8Array; private height: number; constructor(width: number, height: number) { this.buffer = new Uint8Array(width * height); this.height = height; } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { buffer[i * this.height + j] = 1; } } } collides(candidate: Marker): boolean { const { minX, minY, maxX, maxY } = candidate; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { if (buffer[i * this.height + j]) { return true; } } } return false; } }

100,000マーカーの一般化計算時間： 46ミリ秒 。

なぜそんなに速いの？このアプローチは一見単純に見えますが、両方のメソッドのネストされたループは高速コードとは異なります。ただし、コードを詳しく見ると、両方のメソッドの実行時間がマーカーの総数に依存しないことに気付くでしょう。したがって、固定サイズのWxHマーカーの場合、複雑度O（W * H * n）、つまり線形を取得します！

コリジョンバッファアプローチの最適化

1つのピクセルがメモリ内で1バイトではなく1ビットで表現されるようにすれば、速度と占有メモリの両方で以前のアプローチを改善できます。ただし、この最適化後のコードは著しく複雑で、ビット単位の魔法で大きくなりすぎています。

ソースコード

 export class CollisionBufferBitImpl implements CollisionDetector { private width: number; private height: number; private buffer: Uint8Array; constructor(width: number, height: number) { this.width = Math.ceil(width / 8) * 8; this.height = height; this.buffer = new Uint8Array(this.width * this.height / 8); } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; if (start === end) { buffer[start] = buffer[start] | (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { buffer[start] = buffer[start] | (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { buffer[i] = 255; } buffer[end] = buffer[end] | (255 << (8 - (maxX & 7))); } } } collides(marker: Marker): boolean { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; let sum = 0; if (start === end) { sum = buffer[start] & (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { sum = buffer[start] & (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { sum = buffer[i] | sum; } sum = buffer[end] & (255 << (8 - (maxX & 7))) | sum; } if (sum !== 0) { return true; } } return false; } }

100,000マーカーの一般化計算時間： 16ミリ秒 。ご覧のとおり、ロジックの複雑さはそれ自体を正当化し、一般化の計算をほぼ3倍高速化することができます。

衝突バッファの制限

コリジョンバッファはRツリーの完全な代替物ではないことを理解することが重要です。機能がはるかに少なく、制限が多くなっています。

マーカーが正確に交差するものを理解することはできません。バッファには、どのピクセルがビジーで、どのピクセルがビジーでないかに関するデータのみが格納されます。したがって、特定のトークンと交差するトークンのリストを返す操作を実装することはできません。
以前に追加したマーカーは削除できません。バッファーには、指定されたピクセルにあるマーカーの数に関するデータは保存されません。したがって、バッファからマーカーを削除する操作を正しく実装することは不可能です。
要素のサイズに対する高い感度。画面全体を占めるマーカーを衝突バッファーに追加しようとすると、パフォーマンスが劇的に低下します。
限られた地域で機能します。バッファのサイズは作成時に設定され、このサイズを超えるマーカーをバッファに配置することはできません。したがって、このアプローチを使用する場合は、画面に表示されないマーカーを手動でフィルタリングする必要があります。

これらの制限はすべて、マーカーの一般化の問題の解決を妨げませんでした。現在、このメソッドは、2gis.ruのベータ版のマーカーに使用されています。

ただし、マップ上の主な署名を一般化するには、要件がより複雑です。たとえば、彼らにとっては、POIアイコンが自身の署名を「殺す」ことができないようにする必要があります。コリジョンバッファは、交差点の正確な原因を区別しないため、このようなロジックを実装することはできません。そのため、RBushに決定を委ねなければなりませんでした。

おわりに

この記事は、最も単純なソリューションから現在使用されているソリューションへの道を示しています。

Rツリーの使用は、単純な実装を何度も高速化するための最初の重要なステップでした。 Floorsではうまく機能しますが、実際には、このデータ構造の機能のごく一部しか使用していません。

Rツリーを放棄し、それを単純な2次元配列に置き換えました。これは、必要なことだけを行い、それ以外は何もしませんでしたが、生産性がさらに向上しました。

この例は、いくつかのオプションから問題の解決策を選択し、それぞれの制限を理解して実現することの重要性を示しています。制限は重要かつ有用であり、あなたはそれらを恐れてはいけません：些細なことに自分を巧みに制限すれば、本当に必要なところで見返りに大きな利益を得ることができます。たとえば、問題の解決を単純化するため、またはクラス全体の問題から身を守るため、または、この場合のように、生産性を数回改善するためです。

WebGLマップでの高速マーカーの一般化

背景