23. 妥当性

「なぜクエリで 'TopologyException' エラーが発生するのでしょうか?」という質問の90%は「一つ以上の入力が不正だったから」となります。ここから疑問が投げかけられます: 不正であるという意味は何か? またなぜ注意すべきか?

23.1. 妥当性とは

Validity is most important for polygons, which define bounded areas and require a good deal of structure. Lines are very simple and cannot be invalid, nor can points.

Some of the rules of polygon validity feel obvious, and others feel arbitrary (and in fact, are arbitrary).

  • Polygon rings must close.

  • Rings that define holes should be inside rings that define exterior boundaries.

  • Rings may not self-intersect (they may neither touch nor cross themselves).

  • Rings may not touch other rings, except at a point.

  • Elements of multi-polygons may not touch each other.

The last three rules are in the arbitrary category. There are other ways to define polygons that are equally self-consistent but the rules above are the ones used by the OGC SFSQL standard that PostGIS conforms to.

The reason the rules are important is because algorithms for geometry calculations depend on consistent structure in the inputs. It is possible to build algorithms that have no structural assumptions, but those routines tend to be very slow, because the first step in any structure-free routine is to analyze the inputs and build structure into them.

Here's an example of why structure matters. This polygon is invalid:

POLYGON((0 0, 0 1, 2 1, 2 2, 1 2, 1 0, 0 0));

You can see the invalidity a little more clearly in this diagram:

_images/figure_eight.png

The outer ring is actually a figure-eight, with a self-intersection in the middle. Note that the graphic routines successfully render the polygon fill, so that visually it is appears to be an "area": two one-unit squares, so a total area of two units of area.

Let's see what the database thinks the area of our polygon is:

SELECT ST_Area(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

 st_area
---------
       0

What's going on here? The algorithm that calculates area assumes that rings do not self-intersect. A well-behaved ring will always have the area that is bounded (the interior) on one side of the bounding line (it doesn't matter which side, just that it is on one side). However, in our (poorly behaved) figure-eight, the bounded area is to the right of the line for one lobe and to the left for the other. This causes the areas calculated for each lobe to cancel out (one comes out as 1, the other as -1) hence the "zero area" result.

23.2. 妥当性検出

前の例では、不正だと**知っていた**一つのポリゴンを使いました。テーブル内の数百のジオメトリについて不正を検知するにはどうすればいいでしょうか? ST_IsValid(geometry) 関数を使います。8の字ポリゴンに対して使うと、すぐに答が得られます:

SELECT ST_IsValid(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

f

この地物が不正なのは知っていますが、なぜ不正なのかは知りません。ST_IsValidReason(geometry) 関数を使うと、不正の原因を見つけることができます:

SELECT ST_IsValidReason(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

Self-intersection[1 1]

理由 (自己交差) に加えて、不正位置 ((1 1)座標) も返されることに注意して下さい。

テーブルのテストにも ST_IsValid(geometry) 関数を使えます:

-- Find all the invalid polygons and what their problem is
SELECT name, boroname, ST_IsValidReason(geom)
FROM nyc_neighborhoods
WHERE NOT ST_IsValid(geom);

          name           |   boroname    |          st_isvalidreason
-------------------------+---------------+-----------------------------------------
 Howard Beach            | Queens        | Self-intersection[597264.08 4499924.54]
 Corona                  | Queens        | Self-intersection[595483.05 4513817.95]
 Steinway                | Queens        | Self-intersection[593545.57 4514735.20]
 Red Hook                | Brooklyn      | Self-intersection[584306.82 4502360.51]

23.3. 不正なものの修復

ポリゴンを単純な構造 (リング) に分解して、リングが妥当性の規則に従うことを確実にして、リング同士の規則に従った新しいポリゴンを生成することで、不正を修復できます。多くの場合、結果は直感的ですが、非常に行儀の悪い入力の場合には、妥当な出力なのに、どのように見えるかの直感を満たさない場合があります。PostGIS の最近のバージョンでは、ジオメトリの修復のための異なるアルゴリズムがあります: マニュアルページ を注意深く読んで、お好みのものを採用して下さい。

たとえば、不正の古典的な例の「バナナポリゴン」があります。単一のリングで一つの領域を囲みますが、リング自身に接触するように曲がっていて、実際には穴でない「穴」が残ったものです。

POLYGON((0 0, 2 0, 1 1, 2 2, 3 1, 2 0, 4 0, 4 4, 0 4, 0 0))
_images/banana.png

ポリゴンで ST_MakeValid を実行すると、妥当な OGC ポリゴンであって、外側リングと内側リングとが一つの点で接触するポリゴンが得られます。

SELECT ST_AsText(
         ST_MakeValid(
           ST_GeometryFromText('POLYGON((0 0, 2 0, 1 1, 2 2, 3 1, 2 0, 4 0, 4 4, 0 4, 0 0))')
         )
       );

POLYGON((0 0,0 4,4 4,4 0,2 0,0 0),(2 0,3 1,2 2,1 1,2 0))

注釈

「バナナポリゴン」 (あるいは「逆さシェル」) は、妥当なジオメトリのための OGC トポロジモデルと、ESRI が内部で使用するモデルが異なります。ESRI モデルは、接触するリングを無効と考えられ、この種の形状にはバナナ形が好まれます。OGC もで鵜は逆です。両方とも「正しい」というわけでなく、同じ状況をモデル化するための異なる方法です。

23.4. 大規模妥当性修復

修復されたものをテーブルに追加する間に再調査用としてジメトリにフラグを立てるSQLの例を示します。

-- Column for old invalid form
ALTER TABLE nyc_neighborhoods
  ADD COLUMN geom_invalid geometry
  DEFAULT NULL;

-- Fix invalid and save the original
UPDATE nyc_neighborhoods
  SET geom = ST_MakeValid(geom),
      geom_invalid = geom
  WHERE NOT ST_IsValid(geom);

-- Review the invalid cases
SELECT geom, ST_IsValidReason(geom_invalid)
  FROM nyc_neighborhoods
  WHERE geom_invalid IS NOT NULL;

不正ジオメトリの修復に関して視覚的に良いツールは OpenJump (http://openjump.org) です。Tools->QA->Validate Selected Layers に評価ルーチンを持っています。

23.5. 関数リスト

ST_IsValid(geometry A): ジオメトリが妥当かどうかを示す真偽値を返します。

ST_IsValidReason(geometry A): 不正の理由と不正箇所の座標値を示す文字列を返します。

ST_MakeValid(geometry A): 妥当性規則に従って再構築したジオメトリを返します。