そして、データベースに100万個のマーカーを入力することにしたとき、特定の半径でのみマーカーをリクエストしても、すべてが非常に遅くなり、クライアントでのクラスタリングもオプションではないことに気付きました:)
そしてこの森の下のどこかにマンハッタンがあります
クラスタリングは非常に興味深いタスクであり、クライアント、サーバー、およびすべての主要なマップサービスがサポートしています。 多くのタイプのクラスタリングが知られていますが、私の検索ではグリッドクラスタリングを選択しました。 Yandexの従業員は、カンファレンスでのいくつかのレポートで彼女について話をしました。 Yandexマップでクラスターマーカーに使用されます。
Yandexクラスタリング 
理論のビット
グリッドクラスタリングはメルカトル図法に基づいています。要するに、それは長方形の平面上の球体の球面の投影です。 これらは、すべてのアトラス、マップなどです。 このクラスタリングで名前が示すように、マップをグリッドでカバーし、このグリッドの各セルのマーカーの数を計算します。
条件：
タイルは基本的に、特定のズームのためにマップを正方形に分割するだけです。 最初のレベルでは、マップはレベル0の1正方形（タイル）、4正方形（タイル）のレベル1、16の2番目のレベル、64の3番目のレベルなどで構成されます。 実際、学位レベルは4です。
Quadkeyは、あらゆるレベルで一意のタイル識別子です。 最初のレベルでは、タイル0、1、2、3に右から左、上から下に番号を付けます。 次に、次のレベルで、最上位からの各タイルに対して、同じ番号を実行しますが、既に親のクワッドキーを追加します。 00.01,02,03,10,11,12,13など 写真からより明確になります。
したがって、4桁の計算システムで数値を取得しました。 各タイルには、任意のズームレベルで固有の識別子があります。 ズーム、緯度、経度から、すでにクワッドキータイル自体を取得できます。 任意のポイントを、対応するズームレベルのクワッドキーに変換できます。 そして、これはquadkeyが特定の座標を探す方法です：
経度-79.377807617187500
緯度43.653785705566406
quadkey 13940830302567（base4：03022313122033033011213）
マイクロソフトの英語によるこのアプローチの説明：
Bing Mapsタイルシステム
この記事では、これらすべての変換の実装はC＃で記述されているため、PHPで簡単に書き直しました。
TileSystem.php
class TileSystem { const EarthRadius = 6378137; const MinLatitude = -90; const MaxLatitude = 90; const MinLongitude = -180; const MaxLongitude = 180; const MaxZoom = 23; private static function clip( $n, $minValue, $maxValue) { return min( max( $n, $minValue), $maxValue); } public static function mapSize( $levelOfDetail) { return 256 << $levelOfDetail; } public static function GroundResolution( $latitude, $levelOfDetail) { $latitude = self::clip( $latitude, self::MinLatitude, self::MaxLatitude); return cos( $latitude * pi() / 180) * 2 * pi() * self::EarthRadius / self::mapSize( $levelOfDetail); } public static function mapScale( $latitude, $levelOfDetail, $screenDpi) { return self::groundResolution( $latitude, $levelOfDetail) * $screenDpi / 0.0254; } public static function latToPixelY( $latitude, $levelOfDetail) { $latitude = self::clip( $latitude, self::MinLatitude, self::MaxLatitude); $sinLatitude = sin( $latitude * pi() / 180); $y = 0.5 - log((1 + $sinLatitude) / (1 - $sinLatitude)) / (4 * pi()); $mapSize = self::mapSize( $levelOfDetail); $pixelY = (int) self::clip( $y * $mapSize + 0.5, 0, $mapSize - 1); return $pixelY; } public static function longToPixelX( $longitude, $levelOfDetail) { $longitude = self::clip( $longitude, self::MinLongitude, self::MaxLongitude); $x = ($longitude + 180) / 360; $mapSize = self::mapSize( $levelOfDetail); $pixelX = (int) self::clip( $x * $mapSize + 0.5, 0, $mapSize - 1); return $pixelX; } public static function pixelXToLong( $pixelX, $levelOfDetail) { $mapSize = self::mapSize( $levelOfDetail); $x = ( self::clip( $pixelX, 0, $mapSize - 1) / $mapSize) - 0.5; $longitude = 360 * $x; return $longitude; } public static function pixelYToLat( $pixelY, $levelOfDetail) { $mapSize = self::mapSize( $levelOfDetail); $y = 0.5 - (self::clip( $pixelY, 0, $mapSize - 1) / $mapSize); $latitude = 90 - 360 * atan( exp(-$y * 2 * pi())) / pi(); return $latitude; } public static function pixelYToTileY( $pixelY) { return $pixelY / 256; } public static function pixelXToTileX( $pixelX) { return $pixelX / 256; } public static function tileXYToPixelXY( $tileX, $tileY, &$pixelX, &$pixelY) { $pixelX = $tileX * 256; $pixelY = $tileY * 256; } public static function tileXYToQuadKey( $tileX, $tileY, $levelOfDetail) { if ($levelOfDetail == 0) return "0"; $quadKey = ""; for ($i = $levelOfDetail; $i > 0; $i--) { $digit = 0; $mask = 1 << ($i - 1); if (($tileX & $mask) != 0) { $digit++; } if (($tileY & $mask) != 0) { $digit++; $digit++; } $quadKey .= $digit; } return $quadKey; } public static function latLongToQuadKeyDec( $lat, $long, $zoom) { return self::quadKey4ToDec( self::latLongToQuadKey( $lat, $long, $zoom)); } public static function latLongToQuadKey( $lat, $long, $zoom) { $pixelX = \foci\utils\TileSystem::longToPixelX( $long, $zoom); $pixelY = \foci\utils\TileSystem::latToPixelY( $lat, $zoom); $tileX = \foci\utils\TileSystem::pixelXToTileX( $pixelX); $tileY = \foci\utils\TileSystem::pixelYToTileY( $pixelY); return \foci\utils\TileSystem::tileXYToQuadKey( $tileX, $tileY, $zoom); } public static function pixelXYToQuadKey( $pixelX, $pixelY, $zoom) { $tileX = \foci\utils\TileSystem::pixelXToTileX( $pixelX); $tileY = \foci\utils\TileSystem::pixelYToTileY( $pixelY); return \foci\utils\TileSystem::tileXYToQuadKey( $tileX, $tileY, $zoom); } public static function pixelXYToQuadKeyDec( $pixelX, $pixelY, $zoom) { return base_convert( self::pixelXYToQuadKey( $pixelX, $pixelY, $zoom), 4, 10); } public static function quadKeyToTileXY( $quadKey, &$tileX, &$tileY, &$levelOfDetail) { $tileX = $tileY = 0; $levelOfDetail = strlen( $quadKey); for( $i = $levelOfDetail; $i > 0; $i--) { $mask = 1 << ($i - 1); switch( $quadKey[$levelOfDetail - $i]) { case '0': break; case '1': $tileX |= $mask; break; case '2': $tileY |= $mask; break; case '3': $tileX |= $mask; $tileY |= $mask; break; default:; } } } public static function tileXYToQuadKeyDec( $tileX, $tileY, $levelOfDetail) { return base_convert( self::tileXYToQuadKey( $tileX, $tileY, $levelOfDetail), 4, 10); } public static function quadKey4ToDec( $quadkey) { return base_convert( $quadkey, 4, 10); } }
練習に移りましょう
範囲
ここで重要な点を考慮する必要があります。特定のズームでマップ上のすべてのクラスターを要求する必要はありませんが、クライアントのスコープ内にあるクラスターのみを取得する必要があります（この場合は、AndroidとWebです）。
有効範囲内のクラスターを取得するためのオプション：
- スマートクライアント。 クライアント自体が、必要なズームとスコープに入るスコープを決定し、たとえば、ビューを初期化するとき、またはマップ内を移動するときにスコープに入るもののみを一度に要求します
- 怠zyな顧客。 クライアントは単にそのスコープをサーバーに送信し、サーバーが送信する内容を表示します。
怠zyな顧客を選択しました。 なんで？
- クライアントのロジックは非常に単純です。 実際、クライアントはビューとして機能し、ビューを受け取って表示します。
- 異なるプラットフォームに複数のクライアントがあるため、この単純さは便利です。 スコープ内でフォーカスを定義するトリッキーなロジックを複製する必要はありません。 すべてのロジックは、サーバー上の1つの場所に集中しています。
- 実践が示しているように、実装には少し時間がかかります。
サーバーのロジックはどうなりますか？
- 長方形のスコープの角の座標（左上角、右下角など）はサーバーに送られます。
- サーバーは、この長方形の領域の寸法を知って、完全に入力するサイズのタイルを決定します（幅と高さの両方で）
- さらに、タイルのサイズを知っているサーバーはズームを決定できるため、座標とともにタイルを送信する必要はありません。
- 次に、表示をより便利にするために、このズームを大きくする必要があることを考慮する必要があります。
- そして、サーバーは最後のクワッドキーを決定し、スコープに分類し、クラスターを選択してクライアントに提供します。
保管
クワッドキーを保存するには、ズームレベルを選択する必要があります。23で十分です。 データベースはMySQLを使用します。 トークンストレージテーブルの構造は次のとおりです。
CREATE TABLE `marker` ( `id` int(11) NOT NULL AUTO_INCREMENT, `latitude` FLOAT(19,15) NOT NULL, `longitude` FLOAT(19,15) NOT NULL, `quadkey` bigint(20) NOT NULL DEFAULT 0, PRIMARY KEY (`id`), INDEX `quadkey ` (`quadkey `) ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
クワッドキーインデックスを使用すると、タイル（クラスター）内のマーカーの数を簡単に選択できます。
MySQLにクワッドキーを保存するには、bigint（20）を使用します。4桁のシステムから10進数に変換し、データベースとアプリケーションでは10桁のクワッドキーを使用します。
クラスター検索コード
クラスター検索コードは次のようになります。
public function getClusters( $quad_key, $zoom) { $q1 = $quad_key . str_repeat("0", TileSystem::MaxZoom - $zoom); $q2 = $quad_key . str_repeat("3", TileSystem::MaxZoom - $zoom); $mask = $q1; $mask_plus = 1; $mask = $quad_key . str_repeat("3", $mask_plus); $mask = $mask . str_repeat("0", TileSystem::MaxZoom - $zoom - $mask_plus); $q1 = TileSystem::quadKey4ToDec( $q1); $q2 = TileSystem::quadKey4ToDec( $q2); $mask = TileSystem::quadKey4ToDec( $mask); return $this-> findBetweenQuadKeys( $q1, $q2, $mask); } public function findBetweenQuadKeys( $quad_key_l, $quad_key_r, $mask) { $entities = []; $sql = "SELECT `quadkey`, MIN(id) AS id, COUNT(id) AS count, AVG(longitude) AS longitude, AVG(latitude) AS latitude "; $sql .= "FROM `marker ` "; $sql .= "WHERE `quadkey` BETWEEN $quad_key_l AND $quad_key_r "; $sql .= "AND `is_deleted`= '0' "; $sql .= "GROUP BY (`quadkey` & $mask) "; if( $stmt = $this->_connection->query( $sql)) { foreach( $stmt as $row) $entities[] = $this->_createEntityFromRow( $row); } return $entities; }
$ mask変数を使用すると、特定のズームでクワッドキーをグループ化できます。 変数$ quad_key_lおよび$ quad_key_rを使用すると、この親のすべてのマーカーのクワッドキーを考慮することができます。つまり、$ quad_key_l = 03022313122033033000000および$ quad_key_r = 03022313122033033033333の場合、データベース内の030223131220330330330のすべてのマーカーが見つかります。
これは、結果のSQLクエリのようになります。
SELECT `quadkey`, MIN(id) AS id, COUNT(id) AS count, AVG(longitude) AS longitude, AVG(latitude) AS latitude FROM marker WHERE quadkey between 15499682906112 and 15499683168255 GROUP BY (quadkey & 15499683151872); -- 4- -- WHERE quadkey between "03201203031012000000000" and "03201203031012333333333" -- GROUP BY (quadkey & "03201203031012330000000")
どうした
残念ながら、100万個のマーカーに基づいたクラスターのスクリーンショットは保存されませんでした（ただし、それは何かでしたが）、現在の小さなベースがあり、次のようになります。
ウェブ
Android
クラスターの座標は、マーカーがタイルの中心ではなく最も集中している場所にあります。これは、SQLクエリの座標の単純な平均化のおかげです。
結果
このクラスタリングを使用するサーバーが稼働しています。 アプローチ自体は、さらなるスケーリングに非常に便利です。
クラスター内のマーカーの数が絶えず再カウントされないように、クラスターのキャッシングが追加されます。
このトピックをさらに検討すると、マップサービスはマップをレンダリングするためにタイルを積極的に使用します。 同様の何かがゲーム開発などにも使用されています。
ソース
www.mapbox.com/guides/how-web-maps-work
msdn.microsoft.com/en-us/library/bb259689.aspx