🗺️
MapLibre GL JSで透過PNG画像から輪郭を抽出して地図上で衝突判定を実装する
はじめに
株式会社 Geolonia が提供する「地図ぼうけんラボ」の開発において、地図上でのスプライトアイコン同士の衝突判定を実装する必要がありました。単純な円形や矩形の判定では不十分で、任意の形状での正確な判定が求められたため、透過 PNG 画像から輪郭を抽出し、ポリゴン化して衝突判定を行うサンプルを実装しました。
本記事では、Canvas API を使用したピクセルレベルの画像解析から地理座標系での衝突判定まで、実装の詳細を解説します。
実装の概要
システム構成
このシステムは以下の要素で構成されています。
- MapLibre GL JS: 地図表示とインタラクション
- Canvas API: PNG 画像の解析と輪郭抽出
- 衝突判定アルゴリズム: ポリゴン同士の交差判定
処理の流れ
- ユーザーが透過 PNG 画像をアップロード
- Canvas API で画像のアルファチャンネルを解析
- Moore 近傍追跡アルゴリズムで輪郭を抽出
- Douglas-Peucker アルゴリズムで輪郭を簡略化
- 画像座標を地理座標に変換
- 地図上でドラッグ時にリアルタイム衝突判定
Canvas API による画像解析
画像の読み込みと Canvas 描画
まず、アップロードされた PNG 画像を Canvas に描画し、ピクセルデータを取得します。
async function loadImage(file) {
return new Promise((resolve, reject) => {
const reader = new FileReader();
reader.onload = (e) => {
const img = new Image();
img.onload = () => resolve(img);
img.onerror = reject;
img.src = e.target.result;
};
reader.onerror = reject;
reader.readAsDataURL(file);
});
}
function processImage(img) {
const canvas = document.createElement("canvas");
const ctx = canvas.getContext("2d");
// 画像サイズが大きい場合はリサイズ
const maxSize = 256;
const scale = Math.min(maxSize / img.width, maxSize / img.height, 1);
canvas.width = img.width * scale;
canvas.height = img.height * scale;
ctx.drawImage(img, 0, 0, canvas.width, canvas.height);
return { canvas, ctx };
}
アルファチャンネルの抽出と 2 値化
透過 PNG 画像から形状を検出するため、アルファチャンネル（透明度）情報を抽出します。
function extractAlphaChannel(canvas, ctx, threshold = 128) {
// getImageDataでRGBA形式のピクセルデータを取得
const imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
const data = imageData.data; // Uint8ClampedArray [R,G,B,A,R,G,B,A,...]
// 2次元配列として2値マスクを作成
const binaryMask = [];
for (let y = 0; y < canvas.height; y++) {
binaryMask[y] = [];
for (let x = 0; x < canvas.width; x++) {
// 各ピクセルは4バイト（RGBA）で構成
const idx = (y * canvas.width + x) * 4;
const alpha = data[idx + 3]; // アルファ値は4番目
// 閾値処理により2値化
binaryMask[y][x] = alpha > threshold ? 1 : 0;
}
}
return binaryMask;
}
getImageData() で取得したデータは 1 次元配列ですが、RGBA の 4 バイトで 1 ピクセルを表現しています。アルファ値が閾値を超えるピクセルを物体として扱い、2 値マスクを生成します。
輪郭抽出アルゴリズム
Moore 近傍追跡
2 値画像から輪郭線を抽出するために、Moore 近傍追跡アルゴリズムを使用します。このアルゴリズムは、物体の境界を 8 方向の近傍を探索しながら追跡します。
function findContour(binaryMask) {
const height = binaryMask.length;
const width = binaryMask[0].length;
const contourPoints = [];
// 開始点（最初の物体ピクセル）を探索
let startX = -1,
startY = -1;
outer: for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
if (binaryMask[y][x] === 1) {
startX = x;
startY = y;
break outer;
}
}
}
if (startX === -1) return [];
// 8近傍の定義（時計回り）
const neighbors = [
[0, -1], // 上
[1, -1], // 右上
[1, 0], // 右
[1, 1], // 右下
[0, 1], // 下
[-1, 1], // 左下
[-1, 0], // 左
[-1, -1], // 左上
];
let x = startX,
y = startY;
let dir = 0; // 探索開始方向
const visited = new Set();
do {
contourPoints.push([x, y]);
visited.add(`${x},${y}`);
// 8方向を探索して次の輪郭点を見つける
let found = false;
for (let i = 0; i < 8; i++) {
const checkDir = (dir + i) % 8;
const nx = x + neighbors[checkDir][0];
const ny = y + neighbors[checkDir][1];
if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
if (binaryMask[ny][nx] === 1 && !visited.has(`${nx},${ny}`)) {
x = nx;
y = ny;
// 次回の探索方向を更新
dir = (checkDir + 6) % 8;
found = true;
break;
}
}
}
if (!found) break;
} while (
!(x === startX && y === startY) &&
contourPoints.length < width * height
);
return contourPoints;
}
アルゴリズムは以下の手順で動作します。
- 画像を左上から走査し、最初の物体ピクセルを見つける
- 現在の位置から時計回りに 8 近傍を探索
- 次の物体ピクセルが見つかったら移動
- 開始点に戻るまで繰り返す
Douglas-Peucker による簡略化
抽出された輪郭は多くの頂点を持つため、Douglas-Peucker アルゴリズムで簡略化します。
function simplifyContour(points, tolerance = 2) {
if (points.length <= 2) return points;
function douglasPeucker(points, start, end, tolerance) {
let maxDist = 0;
let maxIndex = 0;
// 全ての中間点から直線への距離を計算
for (let i = start + 1; i < end; i++) {
const dist = perpendicularDistance(points[i], points[start], points[end]);
if (dist > maxDist) {
maxDist = dist;
maxIndex = i;
}
}
// 最大距離が許容誤差を超える場合は分割
if (maxDist > tolerance) {
const leftPoints = douglasPeucker(points, start, maxIndex, tolerance);
const rightPoints = douglasPeucker(points, maxIndex, end, tolerance);
return [...leftPoints.slice(0, -1), ...rightPoints];
} else {
return [points[start], points[end]];
}
}
return douglasPeucker(points, 0, points.length - 1, tolerance);
}
function perpendicularDistance(point, lineStart, lineEnd) {
const dx = lineEnd[0] - lineStart[0];
const dy = lineEnd[1] - lineStart[1];
if (dx === 0 && dy === 0) {
return Math.sqrt(
Math.pow(point[0] - lineStart[0], 2) +
Math.pow(point[1] - lineStart[1], 2)
);
}
const normalLength = Math.sqrt(dx * dx + dy * dy);
return (
Math.abs((point[0] - lineStart[0]) * dy - (point[1] - lineStart[1]) * dx) /
normalLength
);
}
このアルゴリズムは再帰的に動作し、形状の特徴を保ちながら不要な頂点を削除します。
地理座標への変換
画像の輪郭座標を地図上の地理座標に変換する必要があります。
function createShapeOnMap(normalizedContour, center, sizeInMeters) {
const [lng, lat] = center;
const earthRadius = 6371000; // 地球の半径（メートル）
// メートルから緯度・経度オフセットへの変換
const latOffset = (sizeInMeters / earthRadius) * (180 / Math.PI);
// 経度オフセットは緯度によって変化
const lngOffset =
((sizeInMeters / earthRadius) * (180 / Math.PI)) /
Math.cos((lat * Math.PI) / 180);
// 正規化座標を地理座標に変換
return normalizedContour.map(([x, y]) => [
lng + lngOffset * x,
lat + latOffset * y,
]);
}
function normalizeContour(contour) {
// バウンディングボックスを計算
let minX = Infinity,
minY = Infinity;
let maxX = -Infinity,
maxY = -Infinity;
for (const [x, y] of contour) {
minX = Math.min(minX, x);
minY = Math.min(minY, y);
maxX = Math.max(maxX, x);
maxY = Math.max(maxY, y);
}
const width = maxX - minX;
const height = maxY - minY;
const maxDimension = Math.max(width, height);
const centerX = (minX + maxX) / 2;
const centerY = (minY + maxY) / 2;
// 中心を原点に、最大寸法を1に正規化
return contour.map(([x, y]) => [
(x - centerX) / maxDimension,
(y - centerY) / maxDimension,
]);
}
緯度による経度の補正（cos(lat)）を適用することで、地球の曲率を考慮して正確に変換します。
衝突判定の実装
ポリゴン同士の交差判定
2 つのポリゴンが交差しているかを判定するために、以下の 2 つのチェックを行います。
- いずれかのポリゴンの頂点が他方の内部にあるか
- エッジ同士が交差しているか
function polygonsIntersect(poly1, poly2) {
// 頂点の内部判定
for (let i = 0; i < poly1.length - 1; i++) {
if (pointInPolygon(poly1[i], poly2)) return true;
}
for (let i = 0; i < poly2.length - 1; i++) {
if (pointInPolygon(poly2[i], poly1)) return true;
}
// エッジの交差判定
for (let i = 0; i < poly1.length - 1; i++) {
for (let j = 0; j < poly2.length - 1; j++) {
if (
lineSegmentsIntersect(poly1[i], poly1[i + 1], poly2[j], poly2[j + 1])
) {
return true;
}
}
}
return false;
}
Ray Casting による点の内部判定
点がポリゴンの内部にあるかを判定する Ray Casting アルゴリズムを実装します。
function pointInPolygon(point, polygon) {
let inside = false;
const x = point[0],
y = point[1];
for (let i = 0, j = polygon.length - 2; i < polygon.length - 1; j = i++) {
const xi = polygon[i][0],
yi = polygon[i][1];
const xj = polygon[j][0],
yj = polygon[j][1];
// 点から水平に伸ばした半直線とエッジの交差判定
const intersect =
yi > y !== yj > y && x < ((xj - xi) * (y - yi)) / (yj - yi) + xi;
if (intersect) inside = !inside;
}
return inside;
}
点から水平方向に半直線を伸ばし、ポリゴンのエッジとの交差回数をカウントします。交差回数が奇数なら内部、偶数なら外部と判定します。
線分の交差判定
2 つの線分が交差するかを CCW（Counter-ClockWise）テストで判定します。
function lineSegmentsIntersect(p1, p2, p3, p4) {
const ccw = (A, B, C) => {
return (C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0]);
};
// p3とp4がp1-p2の異なる側にあり、かつ
// p1とp2がp3-p4の異なる側にある場合に交差
return (
ccw(p1, p3, p4) !== ccw(p2, p3, p4) && ccw(p1, p2, p3) !== ccw(p1, p2, p4)
);
}
MapLibre GL JS への統合
抽出した輪郭を MapLibre GL JS の地図上に表示し、ドラッグ操作と衝突判定を実装します。
// マップの初期化
const map = new maplibregl.Map({
container: "map",
style: {
version: 8,
glyphs: "https://demotiles.maplibre.org/font/{fontstack}/{range}.pbf",
sources: {
osm: {
type: "raster",
tiles: ["https://a.tile.openstreetmap.org/{z}/{x}/{y}.png"],
tileSize: 256,
},
},
layers: [
{
id: "osm",
type: "raster",
source: "osm",
},
],
},
center: [139.767, 35.6814], // 東京駅周辺
zoom: 16,
});
// カスタム形状のポリゴンをGeoJSONとして作成
const draggableMarker = {
type: "FeatureCollection",
features: [
{
type: "Feature",
geometry: {
type: "Polygon",
coordinates: [createShapeOnMap(normalizedContour, center, size)],
},
},
],
};
// 地図に追加
map.addSource("draggable", {
type: "geojson",
data: draggableMarker,
});
map.addLayer({
id: "draggable-fill",
type: "fill",
source: "draggable",
paint: {
"fill-color": "rgba(100, 100, 255, 0.4)",
"fill-outline-color": "#4444ff",
},
});
ドラッグ操作の実装
let isDragging = false;
map.on("mousedown", "draggable-fill", (e) => {
e.preventDefault();
isDragging = true;
map.dragPan.disable(); // 地図のパンを一時無効化
});
map.on("mousemove", (e) => {
if (!isDragging) return;
const center = [e.lngLat.lng, e.lngLat.lat];
// 新しい位置でポリゴンを再生成
draggableMarker.features[0].geometry.coordinates = [
createShapeOnMap(normalizedContour, center, size),
];
map.getSource("draggable").setData(draggableMarker);
// 衝突判定を実行
checkCollisions();
});
map.on("mouseup", () => {
if (isDragging) {
isDragging = false;
map.dragPan.enable();
}
});
パフォーマンス最適化
画像サイズの制限
大きな画像は処理時間とメモリ使用量に影響するため、適切なサイズにリサイズします。
function resizeImage(img, maxSize = 256) {
const scale = Math.min(maxSize / img.width, maxSize / img.height, 1);
if (scale === 1) return img;
const canvas = document.createElement("canvas");
canvas.width = img.width * scale;
canvas.height = img.height * scale;
const ctx = canvas.getContext("2d");
ctx.imageSmoothingEnabled = false; // アンチエイリアスを無効化
ctx.drawImage(img, 0, 0, canvas.width, canvas.height);
return canvas;
}
輪郭の簡略化レベル調整
頂点数が多いと衝突判定のパフォーマンスが低下するため、用途に応じて簡略化レベルを調整します。
// 簡略化レベルに応じた許容誤差の設定
const simplificationLevel = 5; // 1-10のスケール
const tolerance = 11 - simplificationLevel; // 高いレベルほど詳細
const simplifiedContour = simplifyContour(contour, tolerance);
実装時の注意点
CORS 制限への対応
外部ドメインの画像を使用する場合、CORS 設定が必要です。
const img = new Image();
img.crossOrigin = "anonymous"; // CORS設定
img.src = imageUrl;
メモリ管理
不要になった Canvas は明示的に破棄し、メモリリークを防ぎます。
// Canvasのクリア
ctx.clearRect(0, 0, canvas.width, canvas.height);
canvas.width = 0;
canvas.height = 0;
エラーハンドリング
画像処理の各段階で適切なエラーハンドリングを実装します。
try {
const img = await loadImage(file);
if (!img.width || !img.height) {
throw new Error("無効な画像ファイル");
}
const { canvas, ctx } = processImage(img);
const binaryMask = extractAlphaChannel(canvas, ctx);
if (binaryMask.flat().every((v) => v === 0)) {
throw new Error("輪郭が検出できません");
}
// 処理を続行
} catch (error) {
console.error("画像処理エラー:", error);
// ユーザーへのフィードバック
}
まとめ
本記事では、透過 PNG 画像から輪郭を抽出し、地図上で衝突判定を行う実装について解説しました。Canvas API によるピクセルレベルの解析、輪郭追跡アルゴリズム、座標変換、そして MapLibre GL JS への統合まで、各段階の処理を詳しく説明しました。
この実装により、任意の形状のスプライトアイコンを地図上に配置し、正確な衝突判定を行うことが可能になります。地図を使ったゲームやシミュレーション、インタラクティブなアプリケーションの開発に活用できるでしょう。
完全なソースコードはGitHub リポジトリで公開しています。
Discussion