PostGISによるポリゴン単純化を詳しく調べてみた #PostgreSQL

はじめに

Web系の開発では、送受信するファイルサイズをより小さくすることが望まれるかと思います。弊社のTerraMap APIでは、高精度の行政区画ポリゴンをGeoJSON形式で提供していますが、用途によっては精度よりもファイルサイズを小さくすることを優先したいこともあるかと思います。

ポリゴン情報のファイルサイズを小さくする選択肢の一つに、「ポリゴンの単純化（簡略化）」が考えられます。PostGIS 3.5にはジオメトリの単純化関数が5つもありますが、具体的なデータで比較検証を行った例は少ないかと思います。

そこで今回は、TerraMap APIと同じ町丁目ポリゴンを使用して、それぞれの単純化関数の結果を比較し精査してみました。

単純化関数

PostGIS 3.5のリファレンスからジオメトリの単純化関数をリリース順にリストアップすると、以下のようになります。

関数名	ﾘﾘｰｽ	概要
ST_Simplify	1.2.2	Douglas-Peukerアルゴリズムでジオメトリを単純化。
ST_SimplifyPreserveTopology	1.3.3	Douglas-Peuckerアルゴリズムでジオメトリを単純化。トポロジを保全し、妥当なジオメトリを返す。
ST_SimplifyVW	2.2.0	Visvalingam-Whyattアルゴリズムでジオメトリを単純化。
ST_SimplifyPolygonHull	3.3.0	頂点数が目標に達するまで、最も少ない面積を持つ凹の角を徐々に削除していく。トポロジを保全し、妥当なジオメトリを返す。
ST_CoverageSimplify	3.4.0	Visvalingam-Whyattアルゴリズムでポリゴンカバレッジのエッジを単純化。カバレッジのトポロジを保全し、妥当なカバレッジを返す。

アルゴリズム概要

単純化を正しく理解するには、主要な2つのアルゴリズムは知る必要がありそうです。

Douglas Peuckerアルゴリズム
距離ベースの単純化アルゴリズム。ほぼ直線のセグメント上にある頂点を減らしていく方法。

Visvalingam-Whyattアルゴリズム
面積ベースの単純化アルゴリズム。細長いスパイクやほぼ直線上にあるセグメントなど、非常に小さな面積を生み出す頂点を削除していく方法。

トポロジとは

これらの単純化関数では、「トポロジの保全」も大きく影響します。トポロジとは何でしょうか？「PostGIS トポロジ入門」によると、ジオメトリと比較して以下のようなことが言えるかと思います。

ジオメトリには、ポイント(点)、ライン(線)、ポリゴン(面)があり、互いに独立している特徴を持つ。
トポロジには、ノード(点)、エッジ(線)、フェイス(面)があり、独立している訳ではなく、それぞれの共有関係が記録されている。

ジオメトリの単純化における「トポロジの保全」とは、境界の共有情報をある程度保持することによって働く、安全装置と言って良いと思います。

カバレッジの単純化とは

最新の単純化関数「ST_CoverageSimplify」では、対象がジオメトリではなく、ポリゴンジオメトリの集合であるポリゴンカバレッジへと変わっています。妥当なカバレッジの条件としては

ポリゴン同士がオーバーラップしないこと
隣接するエッジ(線)の頂点が確実に合致すること

が提示されており、単純化の入出力時に必要となる条件のようです。

またST_CoverageSimplifyは、ST_Simplify, ST_SimplifyPreserveTopology, ST_SimplifyVWの説明にもあるように、これらの関数にはできていなかった「ポリゴン間で共有されるエッジの保持」を実現したものであり、より安全性の高い単純化関数のようです。

比較方法

単純化関数の比較については、以下のような方法を取りました。
対象とする町丁目ポリゴンは、東京都港区に限定させました。

比較基準としては、ポリゴンをGeoJSONとして出力したときのファイルサイズを考えました（座標値の小数点以下桁数も統一）。ファイルサイズの縮小効果が出始めて、かつポリゴンが大きく変わらないレベルを元の65%前後と仮定し、ファイルサイズをある程度統一させました。

各単純化関数のパラメータは、ビューでいろいろな値を試して決めていきました。最終的なパラメータまたはビューは、下記SQLのようになります。

CREATE VIEW minatoku_chomoku_polygons AS
SELECT
    geocode,
    geom AS original,
    ST_Simplify(
        geom,
        0.00001,
        true
    ) AS result_simplify,
    ST_SimplifyPreserveTopology(
        geom,
        0.00001
    ) AS result_simplify_preserve_topology,
    ST_SimplifyVW(
        geom,
        0.000000003
    ) AS result_simplify_vw,
    ST_SimplifyPolygonHull(
        geom,
        0.65
    ) AS result_simplify_polygon_hull,
    ST_CoverageSimplify(
        geom,
        0.00006
    ) OVER () AS result_coverage_simplify
FROM
    chomoku_polygon
WHERE
    geocode LIKE '13103%'
;

このビューからデータを取得できるようにQGISを設定します。
各ポリゴンは、QGISのレイヤーとして表示し比較しました。単純化したものは50%透過させ、オリジナルは赤のラインポリゴンで最下層に配置させたので、赤色が目立つほどオリジナルとの差が大きいことになります。

表示結果

ST_Simplify

パラメータ　tolerance=0.00001, preserveCollapsed=true
ファイルの縮小率　66.3%

Douglas-Peukerアルゴリズムでジオメトリを単純化している最初の関数です。下図の縮尺率でも赤みがかったラインがみられますので拡大すると差異が現れますが、比較的オリジナルのポリゴンに近い結果が出ました。

ST_SimplifyPreserveTopology

パラメータ　tolerance=0.00001
ファイルの縮小率　65.5%

Douglas-Peukerアルゴリズムでジオメトリを単純化している２番目の関数です。同じアルゴリズムのST_Simplifyと比べると、見た目の違いはほとんど分かりませんでした。トポロジを保全しているので、返すジオメトリの妥当性を重視すれば、後発のST_SimplifyPreserveTopologyを選ぶことが多いのではないでしょうか。

ST_SimplifyVW

パラメータ　tolerance=0.000000003
ファイルの縮小率　66.7%

Visvalingam-Whyattアルゴリズムでジオメトリを単純化している最初の関数です。細かい箇所で赤色のオリジナルラインがはみ出ていることが分かります。非常に小さな面積を生み出す頂点を削除していく方法なので、小さい凹凸部での差が顕著に表れるようです。

ST_CoverageSimplify

パラメータ　tolerance=0.00006
ファイルの縮小率　65.1%

Visvalingam-Whyattアルゴリズムでポリゴンカバレッジのエッジを単純化している関数です。PostGIS 3.5における最新の単純化関数で、返すものの妥当性に関しては一番高いようです。同じアルゴリズムのST_SimplifyVWと近い傾向が出ており、違いもほとんど分からないレベルでした。

ST_SimplifyPolygonHull

パラメータ　vertex_fraction=0.65
ファイルの縮小率　66.7%

最後は、頂点数が目標値に達するまで最も少ない面積を持つ凹の角を徐々に削除していく関数です。この関数もトポロジを保全しているようですが、目標値が優先されているようです。オリジナルとの違いは比較的顕著に現れており、ポリゴン同士がオーバーラップしている箇所も見受けられます。

この関数は、単純化をやり過ぎてしまう印象を受ける結果となりましたが、今回のように目標とする縮小率があれば、一番パラメータを指定しやすい関数でもあります。

さいごに

比較検証の結果は以上になります。

5つもある単純化関数を理解して選択するためにまとめてみましたが、基本的にはPostGISが徐々に改善した関数を導入しているということが分かりました。

最後のおまけですが、最新の単純化関数ST_CoverageSimplifyで単純化の許容範囲をさらに広げた結果は以下のようになります。縮小率は25.3%、他の関数ならば不自然な重なりや隙間が出てきますが、この関数ではありませんでした。用途によっては十分使える気がします。

ST_CoverageSimplify

パラメータ　tolerance=0.0006
ファイルの縮小率　25.3%