Delaunay triangulation for Illustrator (Commented in Japanese)

delaunay-for-illustrator.jsx

#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;  // 外接円の半径の２乗
    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();