1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@shimauma0322(みやまる ふき)

地図上でシンプルな陣取りロジックを組むメモ

1
Last updated at Posted at 2026-09-14

ランニングアプリ KYRO を見て、地図と陣取りの仕組みを個人的にてきとーに検証した記録です。

はじめに

こんにちは

KYROというフィットネスアプリには、ランニングをしながらマップを一周すると囲んだ場所が自分の陣地になる機能があります。

これがかなり中毒性が強くて、近隣ユーザーとの領土の取り合いがエスカレートして脚部が疲労骨折する可能性があり、限界を超えたい方にはオススメなアプリです。

私はほぼ毎日これを使って陣取りに勤しんでるのですが、散歩のたびに仕組みが気になって、自分で実装して確かめてみることにしました。

気になってたのはこの2つです。

  • 一周した範囲を塗りつぶす仕組み
  • その処理をマップ上で再現する仕組み

この辺の技術は完全に未履修ですが、道路に沿ったルートを点列として用意し、線から面を作って地図へ重ねるところまで、とりあえず手を動かして確かめました。

※ 勝手に自己解釈して進めてるので、KYROと実装方法は絶対に異なります。

地図を出す

地図の表示にはMapLibre GL JSを使ってみます。

MapLibre GL JSは、ブラウザで操作できる地図を描画するオープンソースのTypeScriptライブラリです。
公式ドキュメントでは、WebGLを使ってベクタータイルから地図を描画するライブラリと説明されています。

地図を表示するだけでなく、ズーム移動等のカメラ操作、緯度経度と画面座標の変換とかもやれます。

const map = new MapLibreMap({
  container: mapContainer,
  style: {
    version: 8,
    sources: {
      osm: {
        type: 'raster',
        tiles: ['https://tile.openstreetmap.org/{z}/{x}/{y}.png'],
        tileSize: 256,
        attribution: '© <a href="https://www.openstreetmap.org/copyright">OpenStreetMap contributors</a>',
      },
    },
    layers: [{ id: 'osm', type: 'raster', source: 'osm' }],
  },
})

画面には、次のようにOpenStreetMapの地図が表示されました。

01-map.png

地図の描画と操作はMapLibreへ任せ、陣地を作る処理はTypeScriptとSVGで実装します。

点列を地図上の線にする

今回は、神田駅の東らへんの道路・歩道を良い感じにたどる63点の座標列を用意しました。

type Position = [longitude: number, latitude: number]

const route: Position[] = [
  [139.772255, 35.690701],
  [139.772282, 35.690635],
  // ...
  [139.772204, 35.690827],
]

SVGには、複数の点を順番に線でつなぐ<polyline>という要素があります。ここへ点を順番に渡せば、点列を1本の線として描けます。

ただ、ルートが持っているのは経度と緯度です。
SVGが必要とするのは表示領域の左上を原点にしたピクセル座標なので、そのままでは使えません。

なので、MapLibreの project() を使って座標を変換します。

const screenPoints = route.map((point) => map.project(point))

<polyline
  points={screenPoints.map(({ x, y }) => `${x},${y}`).join(' ')}
  fill="none"
  stroke="#d62828"
/>

ひとまず<polyline>をレンダリングすると、線だけの状態になりました。

02-polyline.png

まだただの赤い落書きです。

地図の操作に線を追従させる

この辺は本題と関係ないのでやらなくてもいいのですが、私が気になりすぎるのでやっていきます。

SVGの<polyline>は地図のcanvasとは別のDOM要素なので、最初の1回だけproject()で変換して描画を終えるだけだと、地図を動かしても追従しません。

地図だけ引っ越して、線だけ置いてけぼりを食らっている図です。

03-not-following.gif

そこでMapLibreの move と resize を監視し、そのたびに全点を変換し直すようにします。
moveはドラッグ中やズーム中も含めて地図の見た目が変わるたびに連続して発火するイベントなので、操作が終わってからまとめて1回描画し直すのではなく、操作している最中もリアルタイムに追従して再変換されます。

const redrawWhenFollowing = () => {
  if (followMap) {
    setScreenRoute(route.map((point) => map.project(point)))
  }
}

map.on('move', redrawWhenFollowing)
map.on('resize', redrawWhenFollowing)

これで、地図を操作するたびに線が追従するようになり、置いてけぼり問題は解決です。

04-following.gif

一周されたルートかを判定する

塗りつぶす前に「このルートは一周しているか」を判定させる処理を挟んでみます。

ここを飛ばして途中で終わっているルートをそのまま渡すと、とんでもなく歪な陣地ができるからです。
実際にKYROを使っていても、領地を奪うときは始点の近くまで戻らなければ陣地化されず、ルートの線だけが残る仕様になってます。

この挙動を参考に、今回はPosition[]で持っているルートの最初と最後の座標が30m以内なら、一周したルートと判定することにします。点が3つ未満では範囲を囲めないため、その場合は判定対象から外します。

始点と終点の距離を求める関数の中で、2点の座標差をメートルに換算する関数を呼び、その返り値から距離を求めます。

function projectToMeters(point: Position, origin: Position): [number, number] {
  const latitudeScale = Math.PI * EARTH_RADIUS_METERS / 180
  const longitudeScale = latitudeScale * Math.cos(toRadians(origin[1]))
  return [
    (point[0] - origin[0]) * longitudeScale,
    (point[1] - origin[1]) * latitudeScale,
  ]
}

function distanceMeters(a: Position, b: Position): number {
  const [dx, dy] = projectToMeters(a, b)
  return Math.hypot(dx, dy)
}

で、次のようになりました。

const LOOP_CLOSE_THRESHOLD_METERS = 30

export function isLoopRoute(points: Position[]): boolean {
  if (points.length < 3) return false

  const first = points[0]
  const last = points[points.length - 1]
  return distanceMeters(first, last) <= LOOP_CLOSE_THRESHOLD_METERS
}

ついでに、判定がtrueになったら始点と終点を同じ座標へ統一する処理も発火するようにしときます。
<polyline>は渡された点を順番に結ぶ仕様なので、これをやっておくと綺麗な多角形の線になります。

具体的には下記のような感じに整形します。


// 開いた点列（始点と終点が違う）
const open: Position[] = [
  [139.772255, 35.690701],
  [139.772282, 35.690635],
  [139.772204, 35.690827],
]

// 閉じた点列（末尾に始点と同じ座標を追加した）
const closed: Position[] = [
  [139.772255, 35.690701],
  [139.772282, 35.690635],
  [139.772204, 35.690827],
  [139.772255, 35.690701],
]

この処理をcloseRing()としてまとめ、最終的に点列を次のように扱うことにします。

  • すでに始点と終点が同じなら、そのまま返す
  • 一周判定がtrueなら、末尾へ始点を追加して返す
  • 一周判定がfalseなら、始点を追加せずにそのまま返す

一周したルートを陣地として描画する

さっきのcloseRing()の判定結果を使って、一周したルートだけを陣地として描画します。
使うSVG要素の役割はこんな感じです。

  • <polyline>は元のルートを線で表示する
  • <polygon>は一周したと判定したルートの内側を塗りたくる

※ <polygon>もSVG要素のひとつで、経度・緯度をそのまま扱えないです。<polyline>と同じようにルートの各点をproject()で座標へ変換してから描画します。

実装では、ルートが一周されてなければ<polygon>を描画せず、元のルートを<polyline>だけで表示するようなロジックにします。一周されてれば<polygon>も一緒に描画させます。

その状態で、同じルートを一周し切っていない途中（43点目あたり）までレンダリングすると、末尾は始点から数百メートル離れているため、線だけが残ります。

image.jpeg

ちゃんと未練がましく一本線のままでいてくれました。狙い通りです。

始点と終点の距離がしきい値以内のときは<polygon>が描画され、陣地になります。この塗りつぶしは、<polygon>が勝手にやってくれます。

05-territory.png

<polygon>へ点列を渡すと、内側と判定された領域がfillに指定した色で塗られます。

ちなSVGの<polygon>はどうやって内側を決めるのか

ここまでルートの内側を塗る処理は<polygon>に丸投げしました。
とはいえ、中で何をしてるか分からないままなのもアレなので、その仕組みまで見てみます。

fill-ruleは、SVGで囲まれた領域のどこを内側とみなして塗るかを決める属性です。指定できるのはnonzeroかevenoddで、今回はnonzeroを見てみます。

nonzeroのルールはSVG2の仕様で決まっています。内側か判定したい点から好きな方向へ半直線を伸ばし、その半直線が図形の境界を横切るたびに、横切る向きに応じて +1 か -1 を足していきます。合計が0なら外側、0以外ならその点は内側です。

方向はどこでもいいので、実装するときは右向きの水平な半直線にすると楽です。
こうすると、各辺について見るのは次の2つだけで済みます。

  • その辺が、点と同じ高さ（緯度）をまたいでいるか
  • その辺が、点より右側を通っているか

ここでは緯度が増える方向を上として考えます。両方を満たす辺が「半直線を横切った辺」で、上向きにまたいでいれば +1、下向きなら -1 を足します。「点より右側を通っているか」は、外積の符号で判定できます。

08-winding-rule.png

この交差判定をルートを構成するすべての辺に対して順番に繰り返し、windingへ値を足し引きします。すべての辺を調べ終えたとき、合計が0なら外側、0以外なら内側ということになります。

コードにしてみると恐らくこうです。

// 点pが線分a→bの左右どちら側にあるかを符号で返す（正なら左）
function isLeft(a: Position, b: Position, p: Position): number {
  return (b[0] - a[0]) * (p[1] - a[1]) - (p[0] - a[0]) * (b[1] - a[1])
}

function windingNumber(point: Position, points: Position[]): number {
  let winding = 0

  for (let i = 0; i < points.length; i++) {
    const a = points[i]
    const b = points[(i + 1) % points.length]

    if (a[1] <= point[1]) {
      // 上向きにまたいでいて、辺が点の右側を通っている
      if (b[1] > point[1] && isLeft(a, b, point) > 0) winding += 1
    } else {
      // 下向きにまたいでいて、辺が点の右側を通っている
      if (b[1] <= point[1] && isLeft(a, b, point) < 0) winding -= 1
    }
  }

  return winding
}

上向きの辺に対して点が左側にあれば、その辺は点の右側を通っています。下向きの辺なら逆になるので、符号の判定が上下で反転しています。

まとめ

最初に気になってた2点は、自分の中では結局こうでした。

  • 一周した範囲を塗りつぶす仕組み：始点と終点の距離から一周したルートか判定し、通過したルートだけをSVGの<polygon>へ渡して描画するのが簡単そう。
  • その処理をマップ上で再現する仕組み：緯度経度をMapLibreのproject()で画面座標へ変換し、地図の移動・ズームのたびに変換し直すことで追従させれる。

おわり。

補足

本編の2点を確認する過程で気になったことを残しときます。

別解のFlood Fill

アルゴリズム問題とかに出てくるようなやつで、Flood Fill（塗りつぶし探索）でグリッド上を塗る方法もありますが、なんかやりたいイメージと違うので今回は割愛しました。

面積を求めたいとき

陣地ができると、面積も出したくなるケースもあると思います。
これは靴ひも公式で計算できます。外周順に並んだ頂点を隣同士で掛け合わせ、その差の合計を2で割る公式です。

面積 = 1/2 × |Σ(xᵢ yᵢ₊₁ - xᵢ₊₁ yᵢ)|

経度と緯度は「度」なので、そのまま計算しても平方メートルにはなりません。
一周判定で使ったprojectToMeters()で、各点を平面上のメートルへ変換してから公式へ渡します。

面積計算でも最後の点から最初の点へ戻る辺を計算に含めるため、一周判定のあとに使ったcloseRing()で点列を閉じてから靴ひも公式へ渡します。

if (!isLoopRoute(points)) return 0

const ring = closeRing(points)
const origin = ring[0]
const projected = ring.map((point) => projectToMeters(point, origin))

const twiceArea = projected.slice(0, -1).reduce((sum, point, index) => {
  const next = projected[index + 1]
  return sum + point[0] * next[1] - next[0] * point[1]
}, 0)

const areaSquareMeters = Math.abs(twiceArea) / 2

この平面近似は今回のような狭い範囲向けで、広域の計算には向きません。

自己交差するルートへの対処

今回は始点と終点を繋いで内側を塗りつぶす手法でしたが、他にも「8の字交差」「始点と終点は離れてるが途中点が始点と隣接してる」みたいなケースも考えると、もう一工夫必要ですね。

今回の自前実装はここまでは踏み込まず、自己交差しない1本の外周だけを扱っています。気が向いたらそのうち。

参考

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?