前回やっと Delaunay 分割まで辿り着いた。お目当ての Delaunay 分割も片付いたので、あとは軽く仕上げるだけ。今回は Delaunay 分割した三角形を塗りたいと思います。
さっそくソースコード。
予め canvas のサイズをもとに色テーブルを作っておいて、Delaunay 分割した三角形の外接円の中心をみて色を決めます。んで、塗る。以下、JavaScript だけ。
$(document).ready(function () {
var SAMPLE = {};
SAMPLE.Main = (function () {
var canJqObj = $("#can"),
canDom = document.getElementById('can'),
ctx = document.getElementById('can').getContext("2d"),
// 色のコレクション（最低4色）
colors = [
// http://www.colourlovers.com/palette/2490997/HJ_Project_Palette
["#000000", "#FF0080", "#00D4ED", "#D2D2D2", "#FFFFFF"],
// http://www.colourlovers.com/palette/2490986/all_night_long_.
["#ED146F", "#EDDE45", "#61D2D6", "#242424", "#FAFAFA"],
// http://www.colourlovers.com/palette/2490977/SILVIA_PELISSERO_APC
["#110E19", "#B60F19", "#F86F07", "#FF9F33", "#C1D8A0"],
// http://www.colourlovers.com/palette/2490968/navy_blend
["#14343C", "#DDE915", "#1C15E9", "#A83C17", "#159797"],
// http://www.colourlovers.com/palette/2491000/w_a_t_e_r_m_e_l_o_n
["#E9625C", "#B5C368", "#0A3D5D", "#CCE9C7", "#C9D88A"],
//http://www.colourlovers.com/palette/1483942/The_Autumn_Queen_HPP
["#4E2E1E", "#EA4F6C", "#F99548", "#FCCA55"],
//http://www.colourlovers.com/palette/1297074/Autumn_Rainbow
["#6D2243", "#EC5E0C", "#F78F1E", "#85871A"],
//http://www.colourlovers.com/palette/36998/french_roast
["#A7321C", "#FFDC68", "#928941", "#352504"],
//http://www.colourlovers.com/palette/582235/October_Roads
["#821F29", "#F6E03F", "#ADBD06", "#D46600"], ],
// 使用する色をランダムに選定
colorIndex = Math.floor(Math.random() * (colors.length - 1));
// ==================================================
// 頂点
// ==================================================
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 (colorTable) {
if (colorTable != undefined) {
// 色を格納・設定
var rgb = colorTable.getColor(this.circle.center);
ctx.fillStyle = "rgb(" + rgb.R + ", " + rgb.G + ", " + rgb.B + ")";
// パスのリセット・三角形を指定
ctx.beginPath();
ctx.moveTo(v0.x, v0.y);
ctx.lineTo(v1.x, v1.y);
ctx.lineTo(v2.x, v2.y);
ctx.closePath();
// 塗る
ctx.fill();
}
var drawLine = function (vs, vd) {
var lineColor = "rgb(200, 200, 200)";
if (4 < colors[colorIndex].length) {
var lineRgb = new RGB(colors[colorIndex][4]);
lineColor = "rgb(" + lineRgb.R + ", " + lineRgb.G + ", " + lineRgb.B + ")";
}
// パスのリセット
ctx.beginPath();
// 線の太さ
ctx.lineWidth = 1;
// 線の色
ctx.strokeStyle = lineColor;
// 線を設定
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.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
// ==================================================
// 外接円を描画
// ==================================================
this.drawCircle = function () {
// 外接円の色
ctx.strokeStyle = "rgb(191, 214, 191)";
// 外接円を描画
this.circle.draw();
// 外接円の中心の色
ctx.fillStyle = "rgb(191, 214, 191)";
// 外接円の中心を描画
this.circle.drawCenter();
}; // drawCircle
} // 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
// ==================================================
// RGB
// ==================================================
function RGB(hex) {
var h = hex.substring(1, 7);
return {
R: parseInt(h.substring(0, 2), 16),
G: parseInt(h.substring(2, 4), 16),
B: parseInt(h.substring(4, 6), 16)
}
} // RGB
// ==================================================
// 色テーブル
// ==================================================
function ColorTable() {
var colorTable = [],
columnW = 20,
columnH = 15;
// ==================================================
// 指定された頂点の色を取得
// ==================================================
this.getColor = function (v) {
if (v == undefined) return new RGB("#000000");
// 座標を補正
var adjust = function (p, limit) {
var absP = Math.abs(p);
if (limit < absP) {
return (absP - (limit * Math.floor(absP / limit)));
} else {
return absP;
}
};
v.x = adjust(v.x, canDom.width);
v.y = adjust(v.y, canDom.height);
for (var i in colorTable) {
if (colorTable[i].start.x <= v.x && colorTable[i].end.x >= v.x && colorTable[i].start.y <= v.y && colorTable[i].end.y >= v.y) {
return colorTable[i].color;
}
}
return new RGB("#000000");
}; // getColor
// ==================================================
// 色テーブルを描画（デバッグ用）
// ==================================================
this.draw = function () {
for (var i in colorTable) {
ctx.fillStyle = "rgb(" + colorTable[i].color.R + ", " + colorTable[i].color.G + ", " + colorTable[i].color.B + ")";
ctx.fillRect(colorTable[i].start.x,
colorTable[i].start.y,
colorTable[i].end.x - colorTable[i].start.x,
colorTable[i].end.y - colorTable[i].start.y);
}
}; // draw
// ==================================================
// 色テーブルを初期化
// ==================================================
function initialize() {
var x = 0,
y = 0;
for (var i = 0; i < Math.ceil(canDom.width / columnW); i++) {
y = 0;
for (var j = 0; j < Math.ceil(canDom.height / columnH); j++) {
var col = Math.floor(Math.random() * 4);
colorTable.push({
color: new RGB(colors[colorIndex][col]),
start: new Vertex(x, y),
end: new Vertex(x + columnW, y + columnH)
});
y += columnH;
}
x += columnW;
}
} // initialize
// 初期化
initialize();
} // ColorTable
// ==================================================
// 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 < 40; 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 updateVertexList(list) {
for (var i = 0; i < list.length; i++) {
// 頂点を更新
list[i].update();
// 頂点を描画（デバッグ用）
//list[i].draw();
}
} // updateVertexList
// ==================================================
// 指定された座標を包含する円に外接する三角形を取得
// ==================================================
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, colorTable) {
for (var i in triangleList) {
// 三角形を描画
triangleList[i].draw(colorTable);
// 外接円を描画
//triangleList[i].drawCircle();
}
} // drawTriangleList
// ==================================================
// 開始
// ==================================================
function init() {
var colorTable,
vertexList,
triangleList;
// canvas のサイズを指定
canDom.width = 400;
canDom.height = 350;
// 色テーブルを初期化
colorTable = new ColorTable();
// 頂点リストを初期化
vertexList = initializeVertexList();
// 一定時間で繰り返す
setInterval(function () {
// canvas をクリア
clearCanvas();
// ドロネー分割
triangleList = initializeTriangleList(vertexList);
// 三角形リストを描画
drawTriangleList(triangleList, colorTable);
// 色テーブルを描画（デバッグ用）
//colorTable.draw();
// 頂点リストを更新
updateVertexList(vertexList);
}, 33);
} // init
// 開始
init();
})(); // Main
});