前回、canvas にランダムな点を撒いて移動させるところまでやったので、やっとお目当ての Delaunay（ドロネー）分割に入れる。
Delaunay 分割の仕組みについては、素晴らしい記事があったのでそちらを参照されたい。
さて、じゃあさっそくソースコード。
以下、JavaScript だけ。
$(document).ready(function () {
var SAMPLE = {};
SAMPLE.Main = (function () {
var canJqObj = $("#can"),
canDom = document.getElementById('can'),
ctx = document.getElementById('can').getContext("2d");
// ==================================================
// 頂点
// ==================================================
function Vertex(x, y, vx, vy) {
this.x = x;
this.y = y;
// 固定頂点かどうか（true:固定、false:移動）
this.isStatic = ((vx == undefined || vy == undefined) ? true : false);
// X 軸の移動速度
this.velocityX = ((vx == undefined) ? Math.random() * 0.7 - 0.35 : vx);
// Y 軸の移動速度
this.velocityY = ((vy == undefined) ? Math.random() * 0.7 - 0.35 : vy);
// ==================================================
// 頂点を描画
// ==================================================
this.draw = function () {
// 固定は黒、移動は赤
ctx.fillStyle = (this.isStatic ? "rgb(66, 66, 66)" : "rgb(255, 66, 22)");
ctx.beginPath();
ctx.arc(this.x, this.y, 2, 0, 360, true);
ctx.fill();
};
// ==================================================
// 頂点を更新
// ==================================================
this.update = function () {
// 移動する頂点の場合
if (!this.isStatic) {
// canvas の端で跳ね返す（X）
if (0 > this.x || canDom.width < this.x) {
this.velocityX *= -1;
}
// canvas の端で跳ね返す（Y）
if (0 > this.y || canDom.height < this.y) {
this.velocityY *= -1;
}
// 座標を更新
this.x += this.velocityX;
this.y += this.velocityY;
}
};
} // Vertex
// ==================================================
// エッジ
// ==================================================
function Edge(v0, v1) {
this.v0 = v0;
this.v1 = v1;
} // Edge
// ==================================================
// 三角形
// ==================================================
function Triangle(v0, v1, v2) {
// 外接円の求め方
var x1 = v0.x,
y1 = v0.y,
x2 = v1.x,
y2 = v1.y,
x3 = v2.x,
y3 = v2.y,
c = 2.0 * ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)),
x = ((y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) + (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)) / c,
y = ((x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) + (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)) / c,
center = new Vertex(x, y), // 外接円の中心
dx = center.x - v0.x,
dy = center.y - v0.y,
radius_squared = (dx * dx) + (dy * dy),
radius = Math.sqrt(radius_squared), // 外接円の半径
circle = new Circle(center, radius);
this.v0 = v0;
this.v1 = v1;
this.v2 = v2;
this.circle = circle;
this.radius_squared = radius_squared;
// ==================================================
// 三角形を描画
// ==================================================
this.draw = function () {
var drawLine = function (vs, vd) {
// パスのリセット
ctx.beginPath();
// 線の太さ
ctx.lineWidth = 1;
// 線の色
ctx.strokeStyle = "rgb(162, 206, 226)";
// 開始位置
ctx.moveTo(vs.x, vs.y);
// 次の位置
ctx.lineTo(vd.x, vd.y);
// 描画
ctx.stroke();
};
drawLine(this.v0, this.v1);
drawLine(this.v1, this.v2);
drawLine(this.v2, this.v0);
};
// ==================================================
// 外接円を描画
// ==================================================
this.drawCircle = function () {
// 外接円の色
ctx.strokeStyle = "rgb(191, 214, 191)";
// 外接円を描画
this.circle.draw();
// 外接円の中心の色
ctx.fillStyle = "rgb(191, 214, 191)";
// 外接円の中心を描画
this.circle.drawCenter();
}; // drawCircle
// ==================================================
// 指定された頂点が外接円の内側にあるかどうかを返す
// ==================================================
this.InCircumcircle = function (v) {
var dx = this.circle.center.x - v.x,
dy = this.circle.center.y - v.y,
dist_squared = dx * dx + dy * dy;
return (dist_squared <= this.radius_squared);
}; // InCircumcircle
} // Triangle
// ==================================================
// 円
// ==================================================
function Circle(center, radius) {
// 中心座標と半径
this.center = center;
this.radius = radius;
// ==================================================
// 円を書く
// ==================================================
this.draw = function () {
ctx.beginPath();
ctx.arc(this.center.x, this.center.y, this.radius, 0, 360, true);
ctx.stroke();
};
// ==================================================
// 円の中心を書く
// ==================================================
this.drawCenter = function () {
ctx.beginPath();
ctx.arc(this.center.x, this.center.y, 2, 0, 360, true);
ctx.fill();
};
} // Circle
// ==================================================
// canvas をクリア
// ==================================================
function clearCanvas() {
ctx.clearRect(0, 0, canDom.width, canDom.height);
ctx.globalAlpha = 1;
} // clearCanvas
// ==================================================
// 頂点リストを初期化
// ==================================================
function initializeVertexList() {
var vertexList = [];
// 四隅に頂点を追加
vertexList.push(new Vertex(0, 0));
vertexList.push(new Vertex(canDom.width, 0));
vertexList.push(new Vertex(0, canDom.height));
vertexList.push(new Vertex(canDom.width, canDom.height));
// ランダムに頂点を追加（固定）
for (var i = 0; i < 10; i++) {
vertexList.push(new Vertex(
Math.floor(Math.random() * canDom.width),
Math.floor(Math.random() * canDom.height)));
}
// ランダムに頂点を追加（移動）
for (var j = 0; j < 10; j++) {
vertexList.push(new Vertex(
Math.floor(Math.random() * canDom.width),
Math.floor(Math.random() * canDom.height),
Math.random() * 0.7 - 0.35,
Math.random() * 0.7 - 0.35));
}
return vertexList;
} // initializeVertexList
// ==================================================
// 頂点リストを描画
// ==================================================
function drawVertexList(list) {
for (var i = 0; i < list.length; i++) {
// 頂点を更新
list[i].update();
// 頂点を描画
list[i].draw();
}
} // drawVertexList
// ==================================================
// 指定された座標を包含する円に外接する三角形を取得
// ==================================================
function getHugeTriangle(start, end) {
// start が左上、end が右下になるように補正
if (end.x < start.x) {
var xTmp = start.x;
start.x = end.x;
end.x = xTmp;
}
if (end.y < start.y) {
var yTmp = start.y;
start.y = end.y;
end.y = yTmp;
}
// 四角形を描画
//ctx.strokeRect(start.x, start.y, end.x - start.x, end.y - start.y)
// 渡された座標を包含する円を求める
var center = new Vertex(((end.x - start.x) / 2.0) + start.x, ((end.y - start.y) / 2.0) + start.y),
dx = center.x - start.x,
dy = center.y - start.y,
radius = Math.sqrt((dx * dx) + (dy * dy));
// 円を描画
//(new Circle(center, radius)).draw();
//(new Circle(center, radius)).drawCenter();
// その円に外接する正三角形を求める
var x1 = center.x - Math.sqrt(3) * radius,
y1 = center.y - radius,
v1 = new Vertex(x1, y1),
x2 = center.x + Math.sqrt(3) * radius,
y2 = center.y - radius,
v2 = new Vertex(x2, y2),
x3 = center.x,
y3 = center.y + 2 * radius,
v3 = new Vertex(x3, y3);
return new Triangle(v1, v2, v3);
} // getHugeTriangle
// ==================================================
// 三角形のリストを初期化
// ==================================================
function initializeTriangleList(vertexList) {
var triangleList = [];
// canvas を包含する円に外接する三角形を格納
triangleList.push(getHugeTriangle(new Vertex(0, 0), new Vertex(canDom.width, canDom.height)));
// １つずつ頂点を追加していく
for (var i = 0; i < vertexList.length; i++) {
var vertex = vertexList[i];
AddVertex(vertex, triangleList);
}
return triangleList;
} // initializeTriangleList
// ==================================================
// 三角形のリストに頂点を追加
// ==================================================
function AddVertex(vertex, triangleList) {
// エッジリスト
var edgeList = [];
for (var i in triangleList) {
var triangle = triangleList[i];
// 追加する頂点が外接円の内側にある場合
if (triangle.InCircumcircle(vertex)) {
// エッジに分解
edgeList.push(new Edge(triangle.v0, triangle.v1));
edgeList.push(new Edge(triangle.v1, triangle.v2));
edgeList.push(new Edge(triangle.v2, triangle.v0));
// 三角形のリストから削除
delete triangleList[i];
}
}
// 分解したエッジの中からユニークなエッジを取得
// 重複したエッジを除外することで不正な三角形が除外される
// （ドロネー分割において不正な三角形が重複する特性を利用している）
edgeList = UniqueEdges(edgeList);
// ユニークなエッジをもとに三角形を生成
for (var j in edgeList) {
var edge = edgeList[j];
// 追加する頂点とユニークなエッジをもとに新しい三角形を生成
triangleList.push(new Triangle(edge.v0, edge.v1, vertex));
}
} // AddVertex
// ==================================================
// ユニークなエッジを取得
// ==================================================
function UniqueEdges(edgeList) {
var uniqueEdges = [];
for (var i in edgeList) {
var edge1 = edgeList[i];
var unique = true;
for (var j in edgeList) {
if (i != j) {
var edge2 = edgeList[j];
// 重複したエッジの場合
if ((edge1.v0 == edge2.v0 && edge1.v1 == edge2.v1) || (edge1.v0 == edge2.v1 && edge1.v1 == edge2.v0)) {
unique = false;
break;
}
}
}
// ユニークなものだけ格納
if (unique) {
uniqueEdges.push(edge1);
}
}
return uniqueEdges;
} // UniqueEdges
// ==================================================
// 三角形リストを描画
// ==================================================
function drawTriangleList(triangleList) {
for (var i in triangleList) {
// 三角形を描画
triangleList[i].draw();
// 外接円を描画
triangleList[i].drawCircle();
}
} // drawTriangleList
// ==================================================
// 開始
// ==================================================
function init() {
var vertexList,
triangleList;
// canvas のサイズを指定
canDom.width = 400;
canDom.height = 350;
// 頂点リストを初期化
vertexList = initializeVertexList();
// 一定時間で繰り返す
setInterval(function () {
// canvas をクリア
clearCanvas();
// ドロネー分割
triangleList = initializeTriangleList(vertexList);
// 三角形リストを描画
drawTriangleList(triangleList);
// 三角形の要素数をセット
var count = 0;
for (var i in triangleList)
count++;
// ※確認用
$("#triangleListLength").text("triangleList.length : " + triangleList.length);
$("#triangleCount").text("triangle count : " + count);
// 頂点リストを描画
drawVertexList(vertexList);
}, 33);
} // init
// 開始
init();
})(); // Main
});
確認用で頂点、三角形、三角形の外接円とその中心が描画されます。分割できた途端満足しちゃったので配列からでっかい三角形も除去してないです。
参考記事「Tercel::Diary: ProcessingでDelaunay分割（実装篇）」とちょっと違うのは三角形の重複判定あたり。エッジを定義して判定する方が個人的にはわかり易かったので参考記事とは別の方法で判定してます。
0 Comments :
Post a Comment