【JavaScript】凸包 グラハムスキャンを実装、アニメーション化 する！？【canvas】

凸包を可視化してみる。https://t.co/4ldAMExlGN pic.twitter.com/ggJ8phaBKE

— s-yoshiki | スクリプトカス (@s_yoshiki_dev) 2018年8月5日

概要

JavaScriptでグラハムスキャンによってソートされていくアニメーションを実装した。
下の方で、デモとして紹介。

### 参考 [【JavaScript】凸包(グラハムスキャン)を可視化・アニメーション【Canvas】](https://tech-blog.s-yoshiki.com/2018/06/172/) [【JavaScript】凸包(ギフト包装法)を可視化・アニメーション【Canvas】](https://tech-blog.s-yoshiki.com/2018/06/152/)

環境

JavaScript
Canvas
ライブラリとかは利用せず

デモ

とりあえずデモ。
https://jsfiddle.net/s_yoshiki/wntshy3m/show

実装は、もっと下の方で紹介。

凸包

凸包について
凸包 | Wikipedia

様々なアルゴリズムがあるようだが、
その中でも代表的なグラハムスキャンを実装した。

処理のフローは以下の通り。

1. 点群の中からx,y共に最も小さい点を見つけこれを基準点にする(昇順にソートしたときのindex=0)。
2. 基準点から残りの点群に対し偏角の順にソートする。
3. ソートした配列に対しグラハムスキャンを適用
4. 結果を描画

実際には、
※グラハムスキャンの点の比較に関しては、外積を用いて比較している。
※偏角順のソートは、実際には傾きを利用して計算している。

実装

重要な処理だけ抜粋して紹介。

グラハムスキャン

※偏角順にソートされているものとする

//グラハムスキャン
function grahamScan(map){
    var path = []
    var k = 0
    
    for (var i = 0; i < map.length; ++i) {
        while (true) {
            if (k < 2) {
                break
            }
            var current = [
                map[path[k-1]][0] - map[path[k - 2]][0],
                map[path[k-1]][1] - map[path[k - 2]][1]
            ]
            var next = [
                map[i][0] - map[path[k - 2]][0],
                map[i][1] - map[path[k - 2]][1]
            ]
            
            if (crossVec(current, next) < 0) {
                k--
            } else {
                break
            }
        }
        path[k++] = i
    }
    path = path.slice(0, k)
    path.push(path[0])
    return path
}

//外積
function crossVec(v1,v2){
    return v1[0]*v2[1] - v1[1]*v2[0]
}

昇順ソート

function sortMat(map ,index) {
    	if (index === null || index === undefined) {
        	index = 0
        }
    
    	return map.sort(function(a,b){
        	if( a[index] > b[index] ) {
            	return 1
            } 
            if( a[index] < b[index] ) {
            	return -1
            }
            return 0
        })
    }

偏角順のソート

function sortMatByAngle(map ,p) {

    function norm(v){
        var sum = 0
        for (var j = 0; j < v.length; j++) {
            sum += v[j]*v[j]
        }
        sum = Math.sqrt(sum)
        for (var i = 0; i < v.length; i++) {
            v[i] /= sum
        }
        return v
    }
    
    return map.sort(function(a,b){
        var p1 = [
            p[0] - a[0],
            p[1] - a[1],
        ]
        
        var p2 = [
            p[0] - b[0],
            p[1] - b[1],
        ]
        
        // iOSの場合浮動小数点によるバグが発生する
        if(!navigator.userAgent.match(/(iPhone|iPad|iPod|Android)/)){
            p1 = norm(p1)
            p2 = norm(p2)
        }
        
        if (p1[0] === 0 || p2[0] === 0) {
            return 1
        }
        if( p1[1]/p1[0] > p2[1]/p2[0] ) {
            return 1
        } else {
            return -1
        }
        return 0
    })
}

参考

【JavaScript】凸包(グラハムスキャン)を可視化・アニメーション【Canvas】
【JavaScript】凸包(ギフト包装法)を可視化・アニメーション【Canvas】