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

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">凸包を可視化してみる。<a href="https://t.co/4ldAMExlGN">https://t.co/4ldAMExlGN</a> <a href="https://t.co/ggJ8phaBKE">pic.twitter.com/ggJ8phaBKE</a></p>&mdash; s-yoshiki | スクリプトカス (@s_yoshiki_dev) <a href="https://twitter.com/s_yoshiki_dev/status/1025964653631877120?ref_src=twsrc%5Etfw">2018年8月5日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


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

<img src="https://qiita-image-store.s3.amazonaws.com/0/82419/f30eacd6-1651-eff7-bd98-c4426c64efce.png" width="30%">
### 参考
[【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](https://ja.wikipedia.org/wiki/%E5%87%B8%E5%8C%85)

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

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

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

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


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

### グラハムスキャン
※偏角順にソートされているものとする

```javascript
//グラハムスキャン
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]
}
```

### 昇順ソート

```javascript
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
        })
    }
```


### 偏角順のソート

```javascript
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】](https://tech-blog.s-yoshiki.com/entry/15)
[【JavaScript】凸包(ギフト包装法)を可視化・アニメーション【Canvas】](https://tech-blog.s-yoshiki.com/entry/14/)