凸包とは？
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ナビゲーションに移動検索に移動
赤で表される集合の凸包(Wiki)は、青で表された凸集合である。
数学における凸包（とつほう、英: convex hull）または凸包絡（とつほうらく、英: convex envelope）は、与えられた集合を含む最小の凸集合である。例えば X がユークリッド平面内の有界な点集合のとき、その凸包は直観的には X をゴム膜で包んだときにゴム膜が作る図形として視認することができる。
凸包を描画
凸包に関するアルゴリズムはたくさんあると思いますが、どれもシンプルとはいえないので、ここではD3.jsを利用した凸包描画方法を紹介いたします。サンプルコードではSVGになっていますが、D3.jsはCanvasの描画もサポートしているため、ちょっと書き方を変えればCanvasでも描画可能です。
HTMLとCSS定義
html
<html>
<head>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.14.2/d3.min.js"></script>
</head>
<body>
<div class="graph-area"></div>
</body>
</html>
css
.graph-area {
width:500px;
height:500px;
border:1px solid blue;
}
STEP1
ランダムの点の座標を生成する。
javascript
// グラフィックエリアサイズ500*500px
let width = 500;
let height = 500;
// ランダムX座標
let randomX = d3.randomNormal(width / 2, 60);
// ランダムY座標
let randomY = d3.randomNormal(height / 2, 60);
// 100組ランダム座標を作成
let dataset = d3.range(100).map(function() {
return [randomX(), randomY()];
});
STEP2
サンプル点を描画する
javascript
// SVGタグ初期化
let svgContainer = d3.select("div.graph-area")
.append("svg")
.attr("width", width)
.attr("height", height);
// サンプルポイント描画
dataset.forEach(function(val,idx,arr){
svgContainer.append("circle")
.attr("cx", val[0])
.attr("cy", val[1])
.attr("r", 2);
});
STEP3
D3.jsで凸包の座標を計算し、描画する。
javascript
// 凸包データ生成
let hulldata = d3.polygonHull(dataset);
// 凸包描画
let beforePoint = hulldata[hulldata.length - 1];
hulldata.forEach(function(val,idx,arr){
svgContainer.append("line")
.attr("stroke", "black")
.attr("x1", beforePoint[0])
.attr("y1", beforePoint[1])
.attr("x2", val[0])
.attr("y2", val[1]);
beforePoint = val;
});
結果
