Skip to content

Instantly share code, notes, and snippets.

@shspage
Last active May 10, 2021 15:25
Show Gist options
  • Save shspage/8b03817a6e3b2fb88193386c90fb9717 to your computer and use it in GitHub Desktop.
Save shspage/8b03817a6e3b2fb88193386c90fb9717 to your computer and use it in GitHub Desktop.
Delaunay triangulation for Illustrator (Commented in Japanese)
#target "illustrator"
// 選択オブジェクトの各中心点を母点として
// ドロネー分割した三角形を描画します。
// 以下のページを参考にさせて頂きました。
// http://tercel-sakuragaoka.blogspot.jp/2011/06/processingdelaunay.html
// ここから delaunay 関連
// ------------------------------------------------
// Illustratorでの描画用。黒色を返す
function getBlack(){
var col = new GrayColor();
col.gray = 100;
return col;
}
// Illustratorでの描画用。多角形を描画する。points : 座標値[x, y]([float, float]) の配列
function drawPolygon(points){
var p = app.activeDocument.activeLayer.pathItems.add();
p.setEntirePath(points);
p.closed = true;
p.filled = false;
p.strokeColor = getBlack();
p.strokeWidth = 0.5;
}
// ------------------------------------------------
// 点 x, y: 座標値(float)
// idx:一意のインデックス(int)。三角形の頂点に使わない場合は省略可
var Point = function(x, y, idx){
this.x = x;
this.y = y;
this.idx = idx;
}
Point.prototype = {
eq : function(p){ // p : point
return this.x == p.x && this.y == p.y;
},
dist2 : function(p){ // p : point
var dx = this.x - p.x;
var dy = this.y - p.y;
return dx * dx + dy * dy;
},
dist : function(p){ // p : point
return Math.sqrt(this.dist2(p));
},
toArray : function(){
return [this.x, this.y];
}
}
// ------------------------------------------------
// 三角形 p1, p2, p3 : 頂点の Point
var Triangle = function(p1, p2, p3){
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
// 外接円
var circumCircle = getCircumscribedCirclesOfTriangle(this);
this.o = circumCircle.o; // 外接円の中心
this.r2 = circumCircle.r * circumCircle.r; // 外接円の半径の2乗
this.key = this.getKey();
this.overlap; // 重複判定用
}
Triangle.prototype = {
_hasCommon_sub : function(p, tri){ // p : Point, tri : Triangle
return p.eq(tri.p1) || p.eq(tri.p2) || p.eq(tri.p3);
},
hasCommonPoints : function(tri){ // tri : Triangle
return this._hasCommon_sub(this.p1, tri)
|| this._hasCommon_sub(this.p2, tri)
|| this._hasCommon_sub(this.p3, tri);
},
isInsideCircle : function(p){ // p : point
return p.dist2(this.o) <= this.r2;
},
getKey : function(){ // 連想配列のキーに用いる
var r = [this.p1.idx, this.p2.idx, this.p3.idx];
r.sort();
return r.join("_");
},
draw : function(){
drawPolygon([this.p1.toArray(), this.p2.toArray(), this.p3.toArray()]);
}
}
// --------------------------------------
// 円 o:中心(Point), r:半径(float)
var Circle = function(o, r){
this.o = o;
this.r = r;
}
// --------------------------------------
// Point の配列 points を元にドロネー分割を行う
function delaunay(points){
function addElementToRedundanciesMap(set, tri){
if(tri.key in set){
set[tri.key].overlap = true;
} else {
set[tri.key] = tri;
}
}
// キー: 頂点の Point の idx をソートして "_" で join したもの
// 値:Triangle
var triangles = {};
var hugeTriangle = getHugeTriangle(points);
triangles["huge"] = hugeTriangle;
for(var i = 0, iEnd = points.length; i < iEnd; i++){
var p = points[i];
var tmp_triangles = {}; // 一時オブジェクト。キー・値は trianglesと同じ
for(var key in triangles){
var t = triangles[key];
if(t.isInsideCircle(p)){
addElementToRedundanciesMap(tmp_triangles, new Triangle(p, t.p1, t.p2));
addElementToRedundanciesMap(tmp_triangles, new Triangle(p, t.p2, t.p3));
addElementToRedundanciesMap(tmp_triangles, new Triangle(p, t.p3, t.p1));
delete triangles[key];
}
}
for(var key in tmp_triangles){
var t = tmp_triangles[key];
if( ! t.overlap) triangles[t.key] = t;
}
}
for(var key in triangles){
if(hugeTriangle.hasCommonPoints(triangles[key])) delete triangles[key];
}
return triangles;
/* for(var key in triangles){
triangles[key].draw();
} */
}
// Point の配列 points 全てが内側に入る Triangle を返す
function getHugeTriangle(points){
var p = points[0];
var rect = { left:p.x, top:p.y, right:p.x, bottom:p.y }; // pointsを囲む矩形
for(var i = 1; i < points.length; i++){
p = points[i];
if(p.x < rect.left) rect.left = p.x;
if(p.x > rect.right) rect.right = p.x;
if(p.y > rect.top) rect.top = p.y;
if(p.y < rect.bottom) rect.bottom = p.y;
}
// points を囲む矩形の外接円
var center = new Point((rect.left + rect.right)/2, (rect.top + rect.bottom)/2);
var topleft = new Point(rect.left, rect.top);
var radius = center.dist(topleft);
// 外接円の外接三角形
var x1 = center.x - Math.sqrt(3) * radius;
var y1 = center.y - radius;
var p1 = new Point(x1, y1, -1);
var x2 = center.x + Math.sqrt(3) * radius;
var y2 = center.y - radius;
var p2 = new Point(x2, y2, -2);
var x3 = center.x;
var y3 = center.y + 2 * radius;
var p3 = new Point(x3, y3, -3);
return new Triangle(p1, p2, p3);
}
// ------------------------------------------------
// Triangle t の外接円を取得
function getCircumscribedCirclesOfTriangle(t){
var x1 = t.p1.x;
var y1 = t.p1.y;
var x2 = t.p2.x;
var y2 = t.p2.y;
var x3 = t.p3.x;
var y3 = t.p3.y;
var c = 2.0 * ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
var x = ((y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)
+ (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1))/c;
var y = ((x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)
+ (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1))/c;
var center = new Point(x, y);
var radius = center.dist(t.p1);
return new Circle(center, radius);
}
// ------------------------------------------------
// delaunay 関連ここまで
function drawCircle(o, r){ // デバッグ用
var circle = app.activeDocument.activeLayer.pathItems.ellipse(
o[1] + r, o[0] - r, r*2, r*2);
circle.filled = false;
circle.strokeColor = getBlack();
circle.strokeWidth = 0.5;
}
// --------------------------------------
// 選択範囲 sel の、インデックス idx のオブジェクトの中心座標を返す
function getCenter(sel, idx){
var gb = sel[idx].geometricBounds; // left, top, right, bottom
return new Point((gb[0] + gb[2]) / 2, (gb[1] + gb[3]) / 2, idx);
}
// --------------------------------------
function main(){
// 選択オブジェクトの各中心点を母点としてドロネー分割を行う
var sel = activeDocument.selection;
var points = [];
for(var i = 0; i < sel.length; i++){
points.push(getCenter(sel, i));
}
if(points.length < 3) return;
// 三角形の情報を取得
var triangles = delaunay(points);
// 描画
for(var key in triangles){
triangles[key].draw();
}
}
main();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment