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

Name

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

Synopsis

integer ST_MinimumSpanningTree(geometry winset geom);

説明

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

The Minimum Spanning Tree connects all geometries in the window partition such that the total length of the connecting lines is minimized. If the graph is not fully connected (e.g. infinite distance between some geometries), it produces a Minimum Spanning Forest, and each connected component is assigned a unique tree ID.

Availability: 3.7.0

Requires 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