ST_MinimumSpanningTree
Prev  7.17. クラスタリング関数  Next

Name

ST_MinimumSpanningTree — 最小全域木アルゴリズムを使って入力ジオメトリーを接続された木にクラスタリングを行い、入力ジオメトリーごとに木IDを返すウィンドウ関数です。

Synopsis

integer ST_MinimumSpanningTree(geometry winset geom);

説明

入力ジオメトリの最小接続木 (Minimum Spanning Tree, MST)に基づいてラインストリングの接続グラフを構築するウィンドウ関数です。返り値は、引数のジオメトリーが参加しているクラスターの番号で、最小木を構成していない場合には0となります。

Minimum Spanning Tree (最小全域木）はウィンドウ区画にある全てのジオメトリーと接続していて、線長が最小となる木です。グラフが完全には接続されていない (例: ジオメトリ間が無限距離になっている)場合には、最小全域フォレストを生成します。これはそれぞれの接続要素に一意の木IDが付きます。

Availability: 3.7.0

GEOS >= 3.15.0 が必要です

例

SELECT id, ST_AsText(geom), ST_MinimumSpanningTree(geom) OVER () AS msp
  FROM (VALUES
    (1, 'LINESTRING(0 0,1 0)'::geometry),
    (2, 'LINESTRING(0 0,0 1)'::geometry),
    (3, 'LINESTRING(1 1,0 1)'::geometry),
    (4, 'LINESTRING(1 1,1 0)'::geometry),
    (5, 'LINESTRING(0 0,1 1)'::geometry),
    (6, 'LINESTRING(1 0,0 1)'::geometry)
) AS t(id, geom);
id |      st_astext      | msp
----+---------------------+-----
  1 | LINESTRING(0 0,1 0) |   1
  2 | LINESTRING(0 0,0 1) |   1
  3 | LINESTRING(1 1,0 1) |   1
  4 | LINESTRING(1 1,1 0) |   0
  5 | LINESTRING(0 0,1 1) |   0
  6 | LINESTRING(1 0,0 1) |   0