iOS 多角形のヒット判定を検証する：境界、穴、塗りつぶし規則

地図の選択領域には穴が開いて見えるのに、穴の中をクリックしても選択されてしまう。キャンバス上の点が線分上にあるはずなのに、ズーム倍率によって判定が変わる。こうした不具合は、リモートデスクトップのクリック精度ではなく、描画、座標変換、幾何判定で前提となる仕様が食い違っていることが原因になりがちです。まずはクラウド Mac で純粋な Swift の回帰テストスクリプトを実行し、幾何処理の問題と UI の問題を切り分けましょう。

まずは3状態の判定結果と座標の単位を定義する

最初から真偽値を返す設計にはしません。判定結果を内部、外部、境界の3状態に分け、そのうえで境界を選択対象に含めるかを決めます。地図エディタでは輪郭の選択を許可しても、立ち入り禁止領域では境界への進入も認めない場合があります。両者に、意味を明示しないまま同じ真偽値の判定ルールを適用してはいけません。

本記事で扱うのは、同一の平面座標系上にある、直線の線分で構成された単純な閉じたリングです。外周リングの内側に穴がある場合も扱いますが、緯度・経度の直接投影、自己交差の修復、曲線までの距離は対象外です。入力する点と頂点には、同じ座標変換を適用しておく必要があります。

幾何判定の許容誤差とタッチ領域は別物です。前者は数値による分類を安定させるためのもので、後者はインタラクション設計の問題です。許容誤差を大きくして、選択領域を暗黙に広げてはいけません。

座標にキャンバスの論理単位を使うなら、許容誤差にも同じ単位を使います。画面上で固定のクリック半径を設ける場合は、逆変換によってキャンバス座標に換算する必要があります。縦横で倍率が異なる非等方スケーリングでは、単一の倍率で割るだけでは換算できません。

点と線分の距離で境界を判定する

まず境界を調べ、その後でパスの包含判定を呼び出します。射影位置を計算する際は、必ず線分の両端の間に収めてください。そうしないと、無限に延びる直線に近い点を誤って境界と判定してしまいます。重複した頂点によって長さゼロの辺が生じた場合は、点同士の距離として処理します。

以下を polygon-check.swift として保存します。例で使う許容誤差は座標単位で 0.000001 です。この固定テストデータのための値であり、あらゆる地図やキャンバスに適用できる汎用的な精度ではありません。

import Foundation
import CoreGraphics

enum Location: Equatable {
    case inside, outside, boundary
}

func distance(_ p: CGPoint, _ a: CGPoint, _ b: CGPoint) -> CGFloat {
    let dx = b.x - a.x
    let dy = b.y - a.y
    let lengthSquared = dx * dx + dy * dy
    if lengthSquared == 0 {
        return hypot(p.x - a.x, p.y - a.y)
    }
    let projection = ((p.x - a.x) * dx + (p.y - a.y) * dy)
        / lengthSquared
    let t = min(1, max(0, projection))
    return hypot(p.x - a.x - t * dx, p.y - a.y - t * dy)
}

func locate(
    _ point: CGPoint,
    rings: [[CGPoint]],
    rule: CGPathFillRule,
    epsilon: CGFloat
) -> Location {
    precondition(epsilon.isFinite && epsilon >= 0)
    precondition(point.x.isFinite && point.y.isFinite)
    precondition(!rings.isEmpty)

    let path = CGMutablePath()
    for ring in rings {
        precondition(ring.count >= 3)
        precondition(ring.allSatisfy { $0.x.isFinite && $0.y.isFinite })
        for i in ring.indices {
            let next = (i + 1) % ring.count
            if distance(point, ring[i], ring[next]) <= epsilon {
                return .boundary
            }
        }
        path.move(to: ring[0])
        for vertex in ring.dropFirst() {
            path.addLine(to: vertex)
        }
        path.closeSubpath()
    }
    return path.contains(point, using: rule) ? .inside : .outside
}

これらの事前条件は、入力時の検証を済ませたテストデータを想定しています。本番コードでファイルを読み込む場合は、不正な座標でプロセスを終了させるのではなく、呼び出し側で処理できる検証エラーを返すべきです。また、二乗計算でオーバーフローしないよう、座標値の大きさにも制限が必要です。入力が有限値でも、すべての中間結果が有限値になるとは限りません。

穴のテストデータを固定して塗りつぶし規則を比較する

続けて以下のコードを追加します。外周リングと内周リングの頂点の並びは同じ向きなので、非ゼロワインディング規則では内周リングの内側も塗りつぶされます。一方、偶奇規則では内周リングの内側を穴として扱います。どちらもそれぞれの規則に沿った結果であり、スクリーンショットだけで幾何ライブラリの不具合と判断してはいけません。

let outer: [CGPoint] = [
    CGPoint(x: 0, y: 0), CGPoint(x: 10, y: 0),
    CGPoint(x: 10, y: 10), CGPoint(x: 0, y: 10)
]
let hole: [CGPoint] = [
    CGPoint(x: 3, y: 3), CGPoint(x: 7, y: 3),
    CGPoint(x: 7, y: 7), CGPoint(x: 3, y: 7)
]
let rings = [outer, hole]
let epsilon: CGFloat = 0.000001

func check(_ x: CGFloat, _ y: CGFloat, _ expected: Location) {
    precondition(
        locate(
            CGPoint(x: x, y: y),
            rings: rings,
            rule: .evenOdd,
            epsilon: epsilon
        ) == expected
    )
}

check(1, 1, .inside)
check(5, 5, .outside)
check(12, 5, .outside)
check(0, 5, .boundary)
check(3, 5, .boundary)
check(0, 0, .boundary)
check(-epsilon / 2, 5, .boundary)
check(-epsilon * 2, 5, .outside)

precondition(
    locate(
        CGPoint(x: 5, y: 5),
        rings: rings,
        rule: .winding,
        epsilon: epsilon
    ) == .inside
)

ノードのターミナルで実行します。

xcrun --find swift
xcrun swift polygon-check.swift

正常に終了し、終了コードがゼロなら、これらのアサーションはすべて通過しています。いずれかが失敗すると、終了コードは非ゼロになります。この検証スクリプトは、アサーションのチェックを無効にする最適化設定では実行しないでください。

向き、変換、退化ケースのテストを追加する

長方形だけで確認できるのは、ごく基本的なパスに限られます。回帰テストには、少なくとも凹多角形、水平な辺、連続する同一直線上の頂点、頂点の前後にある2つの近傍点も追加します。くぼみの中にある点は外部と判定されるべきで、外接する長方形の内側にあるという理由だけで選択されてはいけません。

偶奇規則では、任意のリングの頂点順序を反転しても、境界以外のすべてのサンプルで分類が変わらないはずです。すべての頂点とテスト点をまとめて平行移動しても、元と同じ結果になる必要があります。全体を相似拡大する場合は、許容誤差も同じ倍率で拡大します。そうしなければ、同じ境界帯を比較していることにはなりません。

異なる頂点が3つ未満の場合、リング全体が同一直線上にある場合、自己交差がある場合、穴が外周リングからはみ出す場合は、入力時に個別に拒否するか、扱いを明確に定義する必要があります。例にある頂点数のチェックは、多角形の妥当性検証の代わりにはなりません。異常な点を自動で削除してテストを続けると、ユーザーの入力を別の領域に変えてしまうおそれがあります。

失敗を再現できる情報を記録する

失敗時の記録には、各リングの頂点順序、点の座標、塗りつぶし規則、許容誤差、変換行列を保存します。浮動小数点値は十分な精度で保存し、UI 上で丸められた座標だけを残さないでください。丸めによって、境界の両側にある点が同じ値になってしまう可能性があります。

iOS の UI に戻したら座標変換の経路を確認する

純粋な幾何処理のテストが通ったら、同じ判定関数をアプリに組み戻します。タッチ位置がビュー座標からパス座標に変換されているか、スクロールオフセットを二重に差し引いていないか、パスの描画とヒットテストで同じ塗りつぶし規則を使っているかを、段階ごとに確認します。

ズーム前後で同じ論理座標の点を選べば、結果は一致するはずです。一致しない場合は、許容誤差を増やすのではなく、まず逆変換を確認してください。また、ストロークの幅と塗りつぶし領域も別物です。ストロークをクリック対象にする場合は、専用のヒット判定を用意します。

最終的には、2種類のテストを残します。純粋な Swift スクリプトでは幾何処理の仕様を検証し、少数の UI テストでは座標の対応付けを検証します。前者はリモート Mac でコミットごとに実行するのに適しており、後者は実際の操作経路を確認する役割を担います。こうしておけば、失敗したときにデータ、規則、ビューの座標変換のどこに問題があるかを先に切り分けられ、クリック位置を何度も推測し直す必要がなくなります。

よくある質問