newmo 技術ブログ

技術で地域をカラフルに

最終更新日

Coding Agentと幾何学アルゴリズムを活用した地図上の滑らかなピン操作の実現

Mobile iOS AI

newmo のモバイルアプリ開発において、ユーザーが乗車位置を指定するピン操作は、乗車体験の入り口となる重要な機能です。

本記事では、バックエンドから配信される複雑な「乗降車禁止エリア」を回避しつつ、ユーザーにストレスを感じさせない滑らかな操作感を実現するために行った幾何学アルゴリズムの選定と、Coding Agentを活用したTDD（テスト駆動開発）の実装アプローチについて紹介します。

背景: 禁止エリアとUXの衝突

タクシー配車アプリにおいて、ユーザーが地図上で指定した場所が、法令や施設の都合で「配車できない場所」だったとします。

リクエスト送信後に「ここには配車できません」とエラーダイアログを表示する仕様は実装が簡単ですが、ユーザーにとっては手戻りとなり、良い体験とは言えません。

そこで newmo では、マップ上でピンをドラッグしている段階で、禁止エリアに入ったピンをシステムが自動的にエリア外の最適な位置へ誘導（Nudge）する、インタラクティブな制御を実装することにしました。

対象となる禁止エリアのデータはバックエンドから API 経由でリアルタイムに取得され、法令上の駐停車禁止区域、商業施設の敷地、公園など、多種多様かつ膨大な数の地図上の座標で構成された多角形（ポリゴン）として定義されています。

💡 技術補足: 本記事のポリゴンデータは、Google Maps SDKのGMSPathで表現されています。座標のエンコード形式についてはPolyline Algorithmを参照してください。

課題：隣接エリアによる無限ループ

当初、私たちはシンプルなロジックで実装を検討していました。「ピンが禁止ポリゴン内にあれば、そのポリゴンの最も近い辺から外側へ一定距離押し出す」というものです。 しかし、実データを用いた検証において、「隣接または密集する禁止エリア」が存在する場合に重大な問題が発生することが判明しました。

ピンの押し出しがループしてる図
ピンの押し出しの無限ループ

具体的には、以下の現象です。

  1. エリア A から押し出された座標が、隣接するエリア B に入る。
  2. エリア B の判定ロジックが働き、再びエリア A（または別のエリア C）へ押し戻す。
  3. 上記が再帰的に繰り返され、ピンが境界線上で激しく振動したり、計算処理が無限ループに陥る。

外部データであるポリゴンの微小な隙間や重複を、すべて手動で隣接しないように修正することは現実的ではないため、クライアントサイドのロジックのみで、この幾何学的な図形同士の重なり合いからどうピンを押し出すか？を解消する必要がありました。

アプローチ：再帰的な図形の結合による動的なエリア拡張

無限ループを防ぐ解決策として、「押し出した先がさらに別の禁止エリアだった場合、それらのエリアを動的に結合して再評価する」という再帰的なアプローチを採用しました。

最終的なピンの押し出し動作

  1. ピンが禁止エリア A にある場合、エリア A の外へ押し出す。
  2. 押し出した先の座標が、別の禁止エリア B に含まれているか判定する。
  3. もし含まれていた場合、エリア A とエリア B を統合した「巨大な一つのエリア (A+B)」を生成する。
  4. その巨大なエリア (A+B) の境界から、再度ピンを押し出す。
  5. これを「押し出した先がどの禁止エリアにも含まれなくなる」まで再帰的に繰り返す。

このロジックにより、ピンがエリア間を行き来するたびに「回避すべき領域」が動的に拡張されていくため、最終的には隣接する全ての禁止エリア群の外殻の外側へと確実に脱出することができます。

なお、この「図形の統合」には複数の手法が存在しますが、後述するように、凸包（Convex Hull）を採用した場合は図形の凹みが消失するため、「ユーザーが本来置きたい場所に最も近い配車可能ポイント」ではなく、少し遠い位置に押し出されるケースがあります。このトレードオフについては次のセクションで詳しく説明します。

Coding AgentとTDDを用いた実装プロセス

しかし、幾何学アルゴリズムをゼロから学習・実装するには、本来の開発タスクとは別に多大な時間がかかります。 そこで着目したのが、「Convex HullやGraham Scanのような古典的なアルゴリズムは、学習データが豊富なため、Coding Agentが比較的高い精度で実装できる領域である」という点です。図形の結合などの古典的なアルゴリズムは情報が古くからあり、ウェブ上に豊富な実装例が存在するため、AIの学習データも潤沢です。最新のライブラリ事情などとは異なり、枯れた技術領域では非常に精度の高いアウトプットが期待できます。

今回は、人間が「振る舞いの期待値」をテストコードとして定義し、その実装をAIに任せるというTDD（テスト駆動開発）のスタイルを採用することで、数学的な専門知識のギャップを埋めつつ実装を進めました。

1. 幾何学アプローチによるアルゴリズム選定

まず、「複数の図形を統合して一つのエリアとみなす」ための手法を選定する必要がありました。 Coding Agent との壁打ちを通じて、精度・計算コスト・実装難易度の観点から以下の4つのアプローチを比較検討しました。

検討した4つのアプローチ

  1. Polygon Union（ポリゴン結合/論理和）
    • 図形同士を数学的に正確に結合する。形状は完璧だが、計算コストが非常に高い
  2. Concave Hull（凹包）
    • 図形群の形状（凹み）を維持して包む。Unionに近い形状になるが、パラメータ調整が難しい
  3. Convex Hull（凸包）
    • 図形群全体を「輪ゴム」で囲むように包む。凹みは埋まるが、計算が高速で安定している
  4. Bounding Box（AABB / 境界箱）
    • 図形群全体が入る最小の「長方形」で囲む。計算は最速だが、余白（膨らみ）が最大になる

【アルゴリズム比較表】

手法 形状の正確さ (UX) 計算速度 (Performance) 実装難易度 (Robustness) 判定
Polygon Union ◎ 完全 (凹み維持) △ 低速 (O(N2)等) × 難 (自己交差などのバグ多発) 見送り
Concave Hull ◯ 高 (凹み維持) ◯ 中速 △ 中 (パラメータ調整が困難) 見送り
Convex Hull △ 中 (凹み消失) ◎ 高速 (O(N \log N)) ◎ 易 (枯れたアルゴリズム) 採用
Bounding Box × 低 (過剰な膨らみ) ◎ 最速 (O(N)) ◎ 易 (最大最小を取るだけ) 見送り

選定のプロセス

まず、UXとして理想的なのは形状が正確な Polygon Union ですが、モバイルアプリのクライアントサイドでリアルタイムに（ドラッグ操作のたびに）複雑なブーリアン演算を行うことは、計算リソースの観点から非現実的でした。また、複雑なポリゴン同士の結合はエッジケースでの計算不全を招きやすく、ロバスト性に欠けます。

次に検討した Concave Hull は、形状と速度のバランスが良いものの、「どの程度の凹みを許容するか」を決めるパラメータ（Alpha Shapesなど）の調整が非常に難解です。今回のように「小さな公園」から「巨大な商業施設」まで大小様々なエリアが混在する地図データにおいて、万能なパラメータを定義することは困難でした。

逆に、最も単純な Bounding Box は計算が最速ですが、L字型のエリアなどを長方形で囲むと、本来配車可能な場所まで大きく削られてしまい、UXへの影響が大きくなります。

結論：Convex Hull の採用とトレードオフ

検討の結果、

Convex Hull（凸包） が「計算速度」と「UX（形状の近似度）」のバランスが最も優れた解であると判断しました。

Convex Hull を採用する際、懸念点として挙がったのが下図のような「Bulge Area（膨らみ）」の発生です。凹み部分が直線で結ばれることで、本来は禁止エリアではない場所（赤い斜線部分）までピンが置けなくなる可能性があります。

しかし、実際損なわれるUXとのトレードオフを検討した結果、この影響は極めて限定的であると判断しました。

  1. 発生頻度が低いエッジケースである この「膨らみ」が形成されるのは、あくまで「エリアAからエリアBへ押し出され、無限ループが発生した」時のみです。通常の操作でピンが禁止エリアの別の辺（隣接していない側）に近い場合は、そちらへ押し出されるため、統合処理自体が走りません。
  2. 直接のピン打ちは可能である もしユーザーが最初から「Bulge Area（赤い斜線部）」にピンを置いた場合、そこはどの禁止ポリゴンの内部でもないため、システムは何の制御も行いません。つまり、ユーザーが意図してその場所を選べば、問題なく配車位置として指定可能です。

「システムが自動で押し出す際のみ、安全策として少し広めに回避する」という挙動であれば、ユーザー体験を損なうことなく、アプリとしての「ロバスト性（堅牢さ）」と「パフォーマンス」を担保できると判断し、今回は Convex Hull を採用しました。

2. 期待値の定義

アルゴリズムが決まったところで、最も懸念していた「隣接するエリア間でピンが無限に振動する（Ping-Pong）問題」を防ぐため、以下のようなテストケースを定義しました。これは「2つの隣接エリア」があり、その境界付近にピンがある場合、両方のエリアの外側に一度で押し出されることを保証するものです。

@Test
func testPushFromBoundaryRecursively_avoidsPingPong() {
    // 2つの近接した制限エリアを作成（往復移動を引き起こしやすい配置）
    let path1 = createSquareArea(centerLat: 35.6585, centerLon: 139.7020, size: 0.0008)
    let path2 = createSquareArea(centerLat: 35.6585, centerLon: 139.7022, size: 0.0008)

    let coordinate = CLLocationCoordinate2D(latitude: 35.6585, longitude: 139.7021)

    // 実行：再帰的な押し出し処理
    let result = GeometryHelper.pushFromBoundaryRecursively(
      originalCoordinate: coordinate,
      accumulatedPaths: Set([path1]),
      allRestrictedPaths: [path1, path2],
      offsetMeters: 50
    )

    // 検証：エリア蓄積機能により両方のエリア外に押し出されていること
    #expect(!GMSGeometryContainsLocation(result, path1, false))
    #expect(!GMSGeometryContainsLocation(result, path2, false))
}

3. 再帰的なエリア統合の実装

このテストをパスするためにAIと共に実装したのが、以下のコアロジックです。 「押し出し先がまた別の禁止エリアだった場合、そのエリアも取り込んで『巨大な凸包』を作り直し、再評価する」という再帰処理を行っています。

func pushFromBoundaryRecursively(
    originalCoordinate: CLLocationCoordinate2D,
    accumulatedPaths: Set<GMSPath>, // これまでに通過した禁止エリアの蓄積
    allRestrictedPaths: [GMSPath],
    offsetMeters: CLLocationDistance,
    maxIterations: Int
) -> CLLocationCoordinate2D {
    guard maxIterations > 0 else { return originalCoordinate }

    // 1. 蓄積されたエリアを統合して1つの「凸包」を作成
    let unifiedPath = createUnifiedPath(from: Array(accumulatedPaths))
    
    // 2. 統合された境界から外側へ押し出す
    let edge = findClosestEdge(to: originalCoordinate, on: unifiedPath)
    // ... (押し出し方向の計算など) ...
    let newCoordinate = computeOffset(from: foot, distance: offsetMeters, heading: heading)

    // 3. 押し出し先が、まだ考慮していない「別の禁止エリア」内かチェック
    let restrictedPaths = allRestrictedPaths.filter(isInside: newCoordinate)
    
    if restrictedPaths.isEmpty {
        return newCoordinate // 安全な場所なら終了
    }

    // 4. 新たに見つかったエリアを追加して再帰呼び出し
    var additionalAccumulatedPaths = accumulatedPaths
    restrictedPaths.forEach { additionalAccumulatedPaths.insert($0) }

    return pushFromBoundaryRecursively(
        originalCoordinate: originalCoordinate, // 起点は変えずに評価エリアだけ広げる
        accumulatedPaths: additionalAccumulatedPaths,
        allRestrictedPaths: allRestrictedPaths,
        // ...
    )
}

4. 比較検討とアルゴリズムの選定

Coding Agentの活用は、アルゴリズムの「載せ替え検証」において大きな効果を発揮しました。 当初、実装が容易な「ギフト包装法」を試しましたが、計算量が O(N2) となるため、頂点数が増えた際のパフォーマンスに懸念がありました。そこで、「計算量 O(N log N) のグラハムスキャン（Graham Scan）で書き直して」と指示することで、即座に実装を切り替えることができました。

// Graham Scanアルゴリズムによる凸包生成（抜粋）
static func generateConvexHull(from coordinates: [CLLocationCoordinate2D]) -> [CLLocationCoordinate2D] {
    // ... (最下点の探索など) ...

    // 開始点を基準に極角でソート（これが O(N log N) の肝）
    let sortedPoints = coordinates.sorted { a, b in
        // ... (角度計算によるソートロジック)
    }

    // 左折（Left Turn）のみを保持して凸包を構築（O(N)）
    return sortedPoints.reduce(into: [startPoint]) { hull, point in
        removeRightTurns(&hull, newPoint: point)
        hull.append(point)
    }
}

人間は複雑な数式の実装に時間を取られることなく、「どのアルゴリズムが今回の要件に最適か」という意思決定に集中できました。

5. AIによる品質担保

また、このプロセスにおいてAIは「ロジックのレビュアー」としても機能しました。 特に印象的だったのは、以下のような「上下左右を5つの異なるエリアに囲まれた」非常に複雑なケースのテストを作成していた時のことです。

ここでは、Swift Testingのパラメタライズドテスト（Parameterized Testing）を活用し、複数の異なる開始位置（arguments）から、どのように押し出されても最終的に全エリア外へ脱出できるかを網羅的に検証しています。

/*
   139.7010   139.7018  139.7020       139.7030  139.7032  139.7040
         |         |      |                 |       |         |
35.6595 ─├────────────────────────────────────────────────────┤
         │                 X4   Top Area                      │
35.6590 ─├─────────┬──────┬─────────────────┬───────┬─────────┤
         │     X1  │      │   Center Area   │       │  Right  │
         │ Left    │ Tiny │                 │  Tiny │  Area   │
         │  Area   │ Gap  │  X2             │  Gap  │  X3     │
35.6580 ─┤         ├──────┴─────────────────┴───────┴─────────┤
         │         │     Bottom Area      X5                  │
35.6575 ─├─────────┴──────────────────────────────────────────┤
*/
// 5つのエリアが複雑に入り組んだ状況での押し出し処理を検証
@Test(arguments: [
  (latitude: 35.6589, longitude: 139.7016, description: "左側エリア左上"),
  (latitude: 35.6581, longitude: 139.7022, description: "中央エリア右下"),
  // ... 他のパターン（計5箇所）
])
func testPushPoint_variousOffsets(latitude: Double, longitude: Double, description: String) {
  // Top, Left, Center, Right, Bottom の5つのPathを作成して配置
  // ... (省略) ...
  let allRestrictedPaths: [GMSPath] = [topArea, leftArea, centerArea, rightArea, bottomArea]

  // 実行
  let result = GeometryHelper.pushFromBoundaryRecursively(
    originalCoordinate: coordinate,
    accumulatedPaths: Set(restrictedArea),
    allRestrictedPaths: allRestrictedPaths,
    offsetMeters: 25
  )

  // 期待値：どの隙間に入っても、最終的に全エリアの外へ脱出できること
  #expect(!allRestrictedPaths.contains(coordinate: result), "\(description)：制限エリア外にある")
}

このケースにおいて、私が手計算で導き出した「押し出し位置」や「境界マージン」の期待値に対して、AIが提示した結果は異なっていました。

検証してみると、私の計算では考慮漏れしていた微細な隙間やマージンをAIが正しく処理しており、AIが作成したロジックの方が正しかったのです。

（もちろん、これはAIが「優秀」だったのではなく、人間が見落としやすい網羅的な計算をAIが得意としている、という特性の表れです。）

このように、振る舞いベースのテストを先に書き、AIに実装と検証を委ねることで、専門外の領域であっても自信を持ってリリースできる品質を担保することができました。

おわりに

本記事では、地図アプリにおける「ピン制御」の裏側にある技術的な課題と、その解決策について紹介しました。

一見すると単純な座標移動に見える機能ですが、その実現には幾何学的なエッジケースへの対応と、モバイルアプリとしてのパフォーマンス（計算量）を意識したアルゴリズム選定が必要でした。また、難解になりがちな幾何学ロジックの実装において、Coding Agentにテストコードを書かせて品質を担保する TDD アプローチが非常に有効であることが確認できました。

newmo では、こうした技術的な課題解決を通じて、ユーザーが裏側の複雑さを意識することなく「心地よい」と感じられる移動体験を作ることに取り組んでいます。

書いた人: Gemini

書かせた人: @kazuma_nagano