内外判定
地図を目次にする簡潔方法では、47都道府県をすべて長方形に見立てて、クリックした位置から詳細な情報にたどり着くために道筋を立てられるような内容でした。
地図画像の複数点をクリックして、その位置に応じた流れにするには、ある点が多角形に内包するかという問題に帰着します。今回はもう少し、複雑な領域をサポートしてみます。
《多角形に点が含まれるかどうか判定する》には、点と多角形の１辺が作る符号付き角度(a,b,c,d)の総和が 360 度であれば、その点は多角形の内部にあり、そうでなければ外にあると判定する簡便法があります。
多角形が単純な凸型ならば問題は起きませんが、左図のような凹部があると期待した動作にならないことが知られています。
これらの問題をクリアした、点から正の方向に伸ばした x 軸（半直線）が多角形境界線と交差する回数を数える方式(crossing Number Algorithm)があります。
この回数(cN)が奇数ならば、その点は多角形の内側にあり、偶数ならば外側にあると判定されます。Crossing Number Algorithm は Ray Casting Algorithm とも呼ばれています。
Ray Casting Algorithm
符号付き角度(a,b,c,d)の総和が 360 度であるかどうかで判定する方法では、九州・沖縄の地図を図のように簡略化して実装したときに、鹿児島県をクリックしたときに誤動作しました。
これらを解決するために、多くの研究者が技術を公開しており、二次元多角形領域内部に点が含まれるかどうかを判定を参考にさせていただきました。
ここでは、九州・沖縄に限定して実装を試みました。1ヶ所で独立しているのは北海道と沖縄だけであり、この課題をクリアすれば47都道府県をカバーできるでしょう。
サンプルコード
[html]
<html>
ray casting algorithm<BR>
<body onload="starting()"><canvas id="kyu8" width="300" height="444" style="border: 1px orange solid"></canvas></body>
<audio id="sound3" src="https://aidesign.lolipop.jp/wp-content/uploads/2015/09/select06.mp3"></audio>
<script type="text/javascript" charset="Shift_JIS">
const KX=160; // 表示位置x
const KY=400; // 表示位置y
const pref=["長崎", "佐賀", "福岡", "大分", "熊本", "宮崎", "鹿児島", "沖縄"]; // # n 県名
const poly=[[ 10, 9, 96, 9, 96,100, 10,100], // 0 4 長崎
[ 96, 9, 170, 9, 170,100, 96,100], // 1 4 佐賀
[170, 9, 288, 9, 288,101, 214,101, 214,149, 129,149, 129,100, 170,100],// 2 8 福岡
[214,101, 288,101, 288,198, 214,198], // 3 4 大分
[129,149, 214,149, 214,268, 129,268], // 4 4 熊本
[214,198, 288,198, 288,314, 214,314], // 5 4 宮崎
[129,268, 214,268, 214,314, 288,314, 288,357, 129,357], // 6 6 鹿児島
[ 14,341, 79,341, 79,423, 14,423]]; // 7 4 沖縄
var img1 = new Image(); // 画像オブジェクト,ロードする
img1.src = "https://aidesign.lolipop.jp/wp-content/uploads/2017/03/Kyushu08.png"; // 九州・沖縄の地図
var ctx; // コンテキスト
//——————————————————// 2017-03-20 Completed.
function starting(){ // draw-top、ページの読み込み時に実行される
var canvas = document.getElementById(‘kyu8’); // canvasの要素を取得する
if(canvas.getContext){ // canvasオブジェクト
ctx = canvas.getContext(‘2d’); // canvasのコンテキスト
canvas.addEventListener(‘click’, clickfunc , false);// マウスイベントを取り付ける
ctx.drawImage(img1, 0, 0, 300, 444); // <<<<< 九州・沖縄の地図を描画 >>>>>
ctx.fillStyle = "navy"; // 現在地名の色
ctx.fillText("\xA9TacM,2017 Ver0.01", KX, 430); // copyright
}
} // draw-bottom
function clickfunc(event){ // クリックされた時の処理
document.getElementById("sound3").play(); // キー押下音
ctx.clearRect(KX, KY-30, 120, 34); // 前に表示した内容をクリアする
ctx.font = "30px Gill Sans MT Bold"; // set font.
ctx.fillStyle = "red"; // メッセージの色
for(var i=0; i<poly.length; ++i){ // 地点を検索する
if(pointInPolygon(event.offsetX, event.offsetY, poly, i)){// judgeInclusion 検索地の左端・上端～右端・下端
ctx.fillText(pref[i]+"県", KX, KY); // 検索にヒットした
return; // breakはNG、returnの省略は不可
}
}
ctx.fillText("該当なし", KX, KY); // 検索にヒットしない
return; // 戻り値のない関数は省略可能
}
function pointInPolygon(px, py, Array, m){ // px:event.offsetX, py:event.offsetY, Array:array-addr, m:index
var crossingNumber=0; // cNが奇数ならば点Pは多角形Tの内側に、偶数ならば外側にあると判定
for(var i=Array[m].length-2,j=0,yi,yj,counterClockwise; i>=0; j=i,i-=2){// Arrayテーブルの大きさ:8, 6 4 2 0
yi=Array[m][i+1]-py; // <<<<< 点の多角形に対する内外判定 >>>>>
yj=Array[m][j+1]-py; // role-1:上向きの辺。点Pがy軸方向について、始点と終点の間にある。
if((yi>0)!=(yj>0) && (counterClockwise=sign(yj,yi))==sign(yj*(Array[m][i]-px), yi*(Array[m][j]-px))){
crossingNumber+=counterClockwise; // role-2:下向きの辺。点Pがy軸方向について、始点と終点の間にある。
} // role-3:ルール1,ルール2を確認することで、ルール3も確認できる。
} // role-4:辺は点pよりも右側にある。
return crossingNumber%2==1; // ray casting algorithm
}
function sign(a, b) { // 両者を比較して、-1 0 1を返す
return (a > b) ? 1 : (a < b) ? -1 : 0;
}
</script>
</html>
[/html]
実装例
福岡県は8角形、鹿児島県は6角形でありともに凹部を含んでいます。他県はすべて4角形です。本格的な処理に発展させるには38行と42行を拡張させるとよいでしょう。県内、県外の領域をクリックし、納得のいくメッセージが表示されるかを試してください。
ray casting algorithm