HTMLのcanvasで任意の4点をクリックして四角形を描く

なんか、ライブラリであるかな？と思ったけど、意外と書いちゃった方が楽なんじゃないかと思って書いた。

結論から申し上げますと、外積がメッチャ役に立った。

任意の4点から四角形を描く方法

なんかこれどう考えればいいんだろう？って思ったけど、良いのがあった。

4点をpi(i=1,2,3,4)とします.

逆の発想で線分が交わるかどうかを考えます.

線分p1-p2と線分p3-p4が交わりかつ重なっていない場合には, 四角形p1 p3 p2 p4は凸四角形になります (証明は幾何学か計算幾何学の本に載っていると思います).

なので線分p1-p2と線分p3-p4, 線分p1-p3とp2-p4, 線分p1-p4と線分p2-p3が交わるかどうかを調べて交わっているものがあればそれを採用し凸四角形を作ります.

アルゴリズムをまとめると

p1-p2とp3-p4の交差判定交わったら凸四角形p1 p3 p2 p4を描く交わらなかったら次へ p1-p3とp2-p4の交差判定交わったら凸四角形p1 p2 p3 p4を描く交わらなかったら次へ p1-p4とp2-p3の交差判定交わったら凸四角形p1 p2 p4 p3を描く交わらなかったら凸四角形が作れないと判断するとなります.

おー。なるほど。四角形なら高々3回の判定でできるわけだ。

…で、2つの線分が交点を作るかどうか…って。

2つの線分が交点を作るかどうかの判定

これも良いのがあった。

これを判定部分にすると入力値の4点pに対して四角形を描くのに都合の良い配列sが得られる。

というわけで、これを合体させて

こんな感じ。

p = [[79, 30], [283, 44], [19, 228], [325, 219]];

let is_cross = function(line1, line2) {
    var l1_from  = line1[0];
    var l1_to    = line1[1];
    var l2_from  = line2[0];
    var l2_to    = line2[1];
    var line_formula = function(l){
        return l[1]-l1_from[1]-(l[0]-l1_from[0])*(l1_to[1]-l1_from[1])/(l1_to[0]-l1_from[0]);
    }
    return line_formula(l2_from)*line_formula(l2_to)<0;
}
if (is_cross([p[0], p[1]] , [p[2], p[3]])){
    s = [p[0], p[2], p[1] , p[3]];
}
else if (is_cross([p[0], p[2]] , [p[1], p[3]])){
    s = [p[0], p[1], p[2] , p[3]];
}
else {
    s = [p[0], p[1], p[3] , p[2]];
}
console.table(s);
// s = [[79, 30], [19, 228], [325, 219], [283, 44]]

HTMLで書くとこんな感じ。

コピペで動くコードだとこんな。

<html>
<head>
<script>
var points = [];
drawSquare = function(e) {
    let cvs = document.getElementById('c');
    let ctx = cvs.getContext('2d');
    points.push([e.offsetX, e.offsetY]);
    if (points.length > 4){
        points.shift();
    }
    ctx.clearRect(0, 0, cvs.width, cvs.height);
    ctx.strokeStyle = "#14ff10";
    ctx.fillStyle   = "#ff6b6b";
    ctx.lineWidth   = 2;
    for (let i in points){
        ctx.beginPath();
        ctx.arc(points[i][0], points[i][1], 3, 0, Math.PI*2, true);
        ctx.fill();
    }
    if (points.length === 4) {
        // draw square
        let p = points.slice(0, points.length);
        let s = [];
        let is_cross = function(line1, line2) {
            var l1_from  = line1[0];
            var l1_to    = line1[1];
            var l2_from  = line2[0];
            var l2_to    = line2[1];
            var line_formula = function(l){
                return l[1]-l1_from[1]-(l[0]-l1_from[0])*(l1_to[1]-l1_from[1])/(l1_to[0]-l1_from[0]);
            }
            return line_formula(l2_from)*line_formula(l2_to)<0;
        }
        if (is_cross([p[0], p[1]] , [p[2], p[3]])){
            s = [p[0], p[2], p[1] , p[3]];
        }
        else if (is_cross([p[0], p[2]] , [p[1], p[3]])){
            s = [p[0], p[1], p[2] , p[3]];
        }
        else {
            s = [p[0], p[1], p[3] , p[2]];
        }
        // draw lines
        for (let i=0,j=s.length; i<j; i++){
            ctx.beginPath();
            ctx.moveTo(s[i][0] , s[i][1]);
            let k = (i === s.length -1 ? 0 : i + 1);
            ctx.lineTo(s[k][0] , s[k][1]);
            ctx.stroke();
        }
    }
}
</script>
</head>
<body>
<canvas width="400" height="400" style="border:1px solid #ccc; margin: 20px;" id="c" onclick="drawSquare(event)"></canvas>
</body>
</html>

更に、時計回りか反時計回りか分かるように判定ロジックを入れて確認できるようにした。

<html>
<head>
<script>
var drawVerticalLineAnim = function(p1, p2) {
    let count = 50;
    let counter = 0;
    let cvs = document.getElementById('c');
    let ctx = cvs.getContext('2d');

    var render = function() {
        counter++;
        let next = [
           Math.round( (p2[0] - p1[0])/count * counter ) + p1[0],
           Math.round( (p2[1] - p1[1])/count * counter ) + p1[1]
            ];
        ctx.beginPath();
        ctx.moveTo(p1[0], p1[1]);
        ctx.lineTo(next[0], next[1]);
        ctx.closePath();
        ctx.stroke();

        // 描画を繰り返す条件
        if (counter <= count ){
            requestAnimationFrame(render);
        }
      
    };
    render();
};

var points = [];
drawSquare = function(e) {
    let cvs = document.getElementById('c');
    let ctx = cvs.getContext('2d');
    if (points.length === 4){
        points = [];
    }
    points.push([e.offsetX, e.offsetY]);
    ctx.clearRect(0, 0, cvs.width, cvs.height);
    ctx.strokeStyle = "#14ff10";
    ctx.fillStyle   = "#ff6b6b";
    ctx.lineWidth   = 2;
    for (let i in points){
        ctx.beginPath();
        ctx.arc(points[i][0], points[i][1], 3, 0, Math.PI*2, true);
        ctx.fill();
    }
    if (points.length === 4) {
        // draw square
        let p = points.slice(0, points.length);
        let s = [];
        let is_cross = function(line1, line2) {
            var l1_from  = line1[0];
            var l1_to    = line1[1];
            var l2_from  = line2[0];
            var l2_to    = line2[1];
            var line_formula = function(l){
                return l[1]-l1_from[1]-(l[0]-l1_from[0])*(l1_to[1]-l1_from[1])/(l1_to[0]-l1_from[0]);
            }
            return line_formula(l2_from)*line_formula(l2_to)<0;
        }
        if (is_cross([p[0], p[1]] , [p[2], p[3]])){
            s = [p[0], p[2], p[1] , p[3]];
        }
        else if (is_cross([p[0], p[2]] , [p[1], p[3]])){
            s = [p[0], p[1], p[2] , p[3]];
        }
        else {
            s = [p[0], p[1], p[3] , p[2]];
        }
        // draw lines
        for (let i=0,j=s.length; i<j; i++){
            let k = (i === s.length -1 ? 0 : i + 1);
            drawVerticalLineAnim(s[i], s[k]);
            /*
            ctx.beginPath();
            ctx.moveTo(s[i][0] , s[i][1]);
            let k = (i === s.length -1 ? 0 : i + 1);
            ctx.lineTo(s[k][0] , s[k][1]);
            ctx.stroke();
            */
        }
        checkDirection(s);
    }
}
var checkDirection = function(s){
    let anti = '反';
    
    let S = 0;
    for (let i=0,j=s.length; i<j; i++){
        let a = s[i];
        let b = i == j-1 ? s[0] : s[i+1];
        S += a[0] * b[1] - b[0] * a[1];
    }
    console.log('---'); 
    if (S > 0) {
        anti =  '';
    }
    document.getElementById('direction').innerText = anti + '時計回り';
};
</script>
</head>
<body>
<p id="direction"></p>
<canvas width="400" height="400" style="border:1px solid #ccc; margin: 20px;" id="c" onclick="drawSquare(event)"></canvas>
</body>
</html>

時計回りか反時計回りかの判定ロジック

外積を使うとできる。外積なんて20年振りに効いたわ。

当たり前だけど、多角形の場合にも使える。

外積は符号に「右向き」「左向き」の意味を持つのでこの外積の符号で判定する。

ベクトルABから見て・・・ACとの外積とADとの外積の2つがどっちとも正なら同じ向きにあるので交わらない。外積の符号が逆ならどっちかが反対回りなので交わっている。文で書くと理解できないけど、図にするとすぐわかる。自分で図を書くとすぐわかるかな。

f:id:tohokuaiki:20201006131202p:plain — 交わらない場合の外積

f:id:tohokuaiki:20201009150735p:plain — 交わる場合の外積

交差する判定も、外積で行った

<html>
<head>
<script>
var drawVerticalLineAnim = function(p1, p2) {
    let count = 50;
    let counter = 0;
    let cvs = document.getElementById('c');
    let ctx = cvs.getContext('2d');

    var render = function() {
        counter++;
        let next = [
           Math.round( (p2[0] - p1[0])/count * counter ) + p1[0],
           Math.round( (p2[1] - p1[1])/count * counter ) + p1[1]
            ];
        ctx.beginPath();
        ctx.moveTo(p1[0], p1[1]);
        ctx.lineTo(next[0], next[1]);
        ctx.closePath();
        ctx.stroke();

        // 描画を繰り返す条件
        if (counter <= count ){
            requestAnimationFrame(render);
        }
      
    };
    render();
};

var points = [];
drawSquare = function(e) {
    let cvs = document.getElementById('c');
    let ctx = cvs.getContext('2d');
    if (points.length === 4){
        points = [];
    }
    points.push([e.offsetX, e.offsetY]);
    ctx.clearRect(0, 0, cvs.width, cvs.height);
    ctx.strokeStyle = "#14ff10";
    ctx.fillStyle   = "#ff6b6b";
    ctx.lineWidth   = 2;
    for (let i in points){
        ctx.beginPath();
        ctx.arc(points[i][0], points[i][1], 3, 0, Math.PI*2, true);
        ctx.fill();
    }
    if (points.length === 4) {
        // draw square
        let p = points.slice(0, points.length);
        let s = [];
        /*
        // 線分の式を用いる方法
        let is_cross = function(line1, line2) {
            var l1_from  = line1[0];
            var l1_to    = line1[1];
            var l2_from  = line2[0];
            var l2_to    = line2[1];
            var line_formula = function(l){
                return l[1]-l1_from[1]-(l[0]-l1_from[0])*(l1_to[1]-l1_from[1])/(l1_to[0]-l1_from[0]);
            }
            return line_formula(l2_from)*line_formula(l2_to)<0;
        }
        */
        // 外積を用いる方法
        let is_cross = function(line1, line2){
            var a = line1[0]; // A
            var b = line1[1]; // B
            var c = line2[0]; // C
            var d = line2[1]; // D
            let s = (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]);
            let t = (b[0] - a[0]) * (d[1] - a[1]) - (d[0] - a[0]) * (b[1] - a[1]);
            return s * t < 0 ;
        }
        if (is_cross([p[0], p[1]] , [p[2], p[3]])){
            s = [p[0], p[2], p[1] , p[3]];
        }
        else if (is_cross([p[0], p[2]] , [p[1], p[3]])){
            s = [p[0], p[1], p[2] , p[3]];
        }
        else {
            s = [p[0], p[1], p[3] , p[2]];
        }
        // draw lines
        for (let i=0,j=s.length; i<j; i++){
            let k = (i === s.length -1 ? 0 : i + 1);
            drawVerticalLineAnim(s[i], s[k]);
            /*
            ctx.beginPath();
            ctx.moveTo(s[i][0] , s[i][1]);
            let k = (i === s.length -1 ? 0 : i + 1);
            ctx.lineTo(s[k][0] , s[k][1]);
            ctx.stroke();
            */
        }
        checkDirection(s);
    }
}
var checkDirection = function(s){
    let anti = '反';
    
    let S = 0;
    for (let i=0,j=s.length; i<j; i++){
        let a = s[i];
        let b = i == j-1 ? s[0] : s[i+1];
        S += a[0] * b[1] - b[0] * a[1];
    }
    console.log('---'); 
    if (S > 0) {
        anti =  '';
    }
    document.getElementById('direction').innerText = anti + '時計回り';
};
</script>
</head>
<body>
<p id="direction"></p>
<canvas width="400" height="400" style="border:1px solid #ccc; margin: 20px;" id="c" onclick="drawSquare(event)"></canvas>
<script>
window.onload = function(){
//    drawVerticalLineAnim([10, 10], [100, 100]);
};
</script>
</body>
</html>

先ほどの判定だとzero divが起こってしまう可能性があったので。

tohokuaikiのチラシの裏

技術的ネタとか。