ST_MinimumSpanningTree
戻る  7.17. クラスタリング関数  次へ

名前

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

概要

integer ST_MinimumSpanningTree(geometry winset geom);

説明

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

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

Availability: 3.7.0

GEOS >= 3.15.0 が必要です

例

These six edges describe a square with both diagonals. The minimum spanning tree keeps three edges and excludes the rest.

Code
WITH edges(id, geom) AS (
  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)
), marked AS (
  SELECT id,
         geom,
         ST_MinimumSpanningTree(geom) OVER (ORDER BY id) AS tree_id
  FROM edges
)
SELECT string_agg(id::text, ',' ORDER BY id)
         FILTER (WHERE tree_id > 0) AS tree_edge_ids,
       ST_Collect(geom ORDER BY id)
         FILTER (WHERE tree_id > 0) AS tree_edges,
       string_agg(id::text, ',' ORDER BY id)
         FILTER (WHERE tree_id = 0) AS excluded_edge_ids,
       ST_Collect(geom ORDER BY id)
         FILTER (WHERE tree_id = 0) AS excluded_edges
FROM marked;
出力:
-[ RECORD 1 ]-----
tree_edge_ids     | 1,2,3
tree_edges        | MULTILINESTRING((0 0,1 0),(0 0,0 1),(1 1,0 1))
excluded_edge_ids | 4,5,6
excluded_edges    | MULTILINESTRING((1 1,1 0),(0 0,1 1),(1 0,0 1))