反転変換(円に関する反転)について（２）

前回（１） の続きです。

反転変換した円を Illustrator で描く

反転変換は円を円に変換しますが、変換後の円をIllustratorでどう描けばよいでしょう。

前回の図で見たように、元の円の中心は写った先の円の中央には来ません。
円周上の点にアンカーポイントを置いていくのも非効率的です。

しかし基準円の中心から見て、元の円の最も近い点・遠い点は、 それぞれ変換後の円の最も遠い点・近い点になることは言えます。

そこで、この２点の中点を中心として、２点を通る円を描けばよいことになります。

Illustrator のスクリプトの関数として書くと以下のようになります。

// 半径 r, 中心 o の円に関する 円 circle の反転を返す。
// o: Point
// r2: float 半径の２乗
// circle: Circle
// return: Circle
function inverseCircle(o, r2, circle){
    var d = dist(circle.center, o);
    
    var v = d == 0
      ? new Point(circle.radius, 0)
        : circle.center.sub(o).mul(circle.radius / d);  // ※

    var p1 = circle.center.sub(v);
    var p2 = circle.center.add(v); 

    var i1 = inverse(o, r2, p1);
    var i2 = inverse(o, r2, p2);

    var c = new Circle(getMidPoint(i1, i2),
                       dist(i1, i2) / 2);
    return c;
}
// ----------------------------------------------
Point.prototype = {
    add : function(p){  // p : Point
        return new Point(this.x + p.x, this.y + p.y);
    },
    sub : function(p){  // p : Point
        return new Point(this.x - p.x, this.y - p.y);
    },
    mul : function(m){  // m : float
        return new Point(this.x * m, this.y * m);
    }
}
// ------------------------
// 円
// o : Point, 中心
// r : float, 半径
function Circle(o, r){
    this.center = o;
    this.radius = r;
}
// ------------------------
// Point p1, p2 の間の距離を返す
function dist(p1, p2) {
    return Math.sqrt(dist2(p1, p2));
}
// ------------------------
// Point p1, p2 の中点を返す
function getMidPoint(p1, p2){
    return new Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
}

inverse, dist2, Point(コンストラクタ) については前回載せたものになるので省略しています。

inverseCircle の
circle.center.sub(o).mul(circle.radius / d); の部分についてですが、

まず元の円の中心の座標値から基準円の中心の座標値を引くと、 基準円の中心を原点とした場合の、元の円の中心へのベクトルが得られます。

それを中心同士の距離 d で割ると単位ベクトル *1 になります。

ここではその単位ベクトルに元の円の半径を掛けたベクトルを作っています。

これを元の円の中心から引いたものを、基準円の中心に最も近い点(p1)、 足したものを最も遠い点(p2)としています。

反転変換しても接点は保たれる。

次のネタに行く前に、反転変換の性質をもう一つ挙げておきます。

接している円が共有している接点は１つの点です。 反転の仕組みから考えて、 １つの点を反転すると２つに分かれるというのはあり得ません。

なので接している２円を反転した場合、接している２円になります。

２円に交点があるなら、交点についても同じことが言えます。

これを踏まえて、

２円に接し１点を通る円を描く

これは前に書いた「 ３つの円の隙間に円を描く 」で保留した説明にもなるのですが、単に面白い形を描く以外にも反転が役立つ例です。

下の図の点 P を通り２円に接する円を描きたいというときに、反転変換が利用できます。

Illustratorのスクリプトは、長くなったのでGistに置きました。

Illustrator : １点を通り２円に接する円を描く · GitHub

手順としては、まず点 P を中心とした適当な円を基準円として、２円を反転変換します。 そのうえで、変換後の２円に共通接線を引きます。 *2

前回書いたように、この直線は無限遠を通る円と考えられます。
そしてこの「円」は２円に接していますので、 反転すると元の２円に接する円になるはずです。

また、無限遠を反転変換すると基準円の中心になるのでした。

つまり、共通接線の接点を反転すると、
基準円の中心点 P と合わせて求める円の円周上の３点が決まります。

あとは３点を結ぶ三角形の外接円を描く要領で円を描くことができます。

考えてみると反転によって無限遠をはるばる点 P の位置に持ってきてるわけで、 無限遠が目の前に！おおっ！って感じです。

……ところで２円の共通接線は上の図に書いたものの他にも最大３本あります。 上の考え方からすると、これらも反転すると点Pを通り２円に接する円になるはずです。 この場合はいずれかまたは両方の円が描いた円の内側に接するような形になります。

円の内側に接するケースも考えると、共通接線が引けない場合でも 円が描けることがあります。 このためサンプルスクリプトは本当はもっと場合分けする必要があります。

詳しくは「 アポロニウスの問題 - Wikipedia 」を調べてみてください。

つづく

↓つづき

反転変換(円に関する反転)について（３） - s.h's page

*1:長さが１のベクトル

*2:スクリプトでの共通接線の書き方は以前の記事「２円をつなぐ線を描く」参照

反転変換(円に関する反転)について（１）

反転変換は、下の図で、点 を になるような点 に写す座標変換です。

が円の中心に近いほど、は中心から遠ざかり、
が円の中心と同じ位置の場合、 までの距離は無限遠になります。

反転に使った半径 の円を基準円と呼びます。

Illustratorのスクリプトの関数として書くと以下のようになります。

var Point = function(x, y){
    this.x = x;
    this.y = y;
}
// --------------------------------------
// Point p1, p2 の間の距離の２乗を返す
function dist2(p1, p2) {
    var dx = p1.x - p2.x;
    var dy = p1.y - p2.y;
    return dx*dx + dy*dy;
}
// --------------------------------------
// 半径 r, 中心 o の円に関して点 p を反転変換する。
// r2: float 半径 r の２乗
// o, p: Point
function inverse(o, r2, p){
    var d2 = dist2(o, p);
    if(d2 == 0){
        return Infinity;
    }

    var m = r2 / d2;  // ※

    var q = new Point((p.x - o.x) * m + o.x,
                      (p.y - o.y) * m + o.y);
    return q;
}

var m = r2 / d2; の部分についてですが、

の位置は、 の をそれぞれ で割って を掛ければ求められますので、 *1

最初の式から ですので、

分数の分母と分子に d を掛けると

となります。

たいていは多くの点について繰り返し使うような用途になるので、 半径をあらかじめ２乗しておき、距離も２乗として使い、 無駄な乗算や平方根の計算による処理時間のロスを減らしています。

で？

って感じですが、
これを図形に適用するとだんだん面白くなってきます。

1. 反転変換は円を円にする

下の図で基準円の内側にある、円周に沿って並べた点は、それぞれ基準円の外側にある点のように反転変換されます。

点が等間隔でなくなって、中心も変なところに行っていますが、変換された点も円を描いているようではありますね。

もっと点を増やすと、明らかに円を描いているのがわかります。

反転変換には「円を円に写す」という性質があります。

2. 反転変換は中心を通る円を直線にする

下の図で基準円の内側にある、中心を通る円に沿って並べた点は、 それぞれ外側にある直線に沿って並んだ点に変換されます。

「1」と矛盾するようですが、実はこれは同じことで、
私のイメージとしては、
と、下のような図を描くと数学のできる人がブチ切れそうですが、

前述のように、基準円の中心に置いた点は反転変換によって無限遠に飛ばされます。
つまり中心を通る円を反転すると、無限遠を通る円になります。
直線とは、無限遠を通る円の円周と考えることもできるのですね。

3. 反転変換の結果を反転変換すると元に戻る

反転変換の式、 は、 としても同じことですので、これは当然ですが、
この性質にしたがって言えば、「2」の「中心を通る円を直線にする」は「直線を中心を通る円にする」とも言えます。

※ 図を描くのに使用したスクリプトを記事の最後に掲載します。

活用例

円の外に描いた六角形（辺上にアンカーポイントをたくさん追加している）を 円を使って反転変換して、赤い線の形状にしました。

何か面白い形ができそうな感じがしないでしょうか。

記事の最後に掲載しているスクリプトはオブジェクトの中心座標を移動していますが、 この例ではアンカーポイントを反転変換しています。 スクリプトはほとんど似た感じなので Gist に置きました。

Illustrator：最背面のパス（円）に関して残りの選択パスのアンカーポイントを反転変換した座標に移動する · GitHub

つづく

今回はここまで。

たぶん（３）まで続く予定。

付録：図を描くのに使用したスクリプト

「で？」の節の図の作成に使用したスクリプトです。

// 最背面のパス（円）に関して残りの選択オブジェクトを
// それぞれの中心を反転変換した座標に移動する
// --------------------------------------
var Point = function(x, y){
    this.x = x;
    this.y = y;
}
// --------------------------------------
// 半径 r, 中心 o の円に関して点 p を反転変換する
// r2: float, 半径 r の２乗
// o, p: Point
function inverse(o, r2, p){
    var d2 = dist2(o, p);
    if(d2 == 0){
        return Infinity;
    }
    var m = r2 / d2;
    var q = new Point((p.x - o.x) * m + o.x,
                       (p.y - o.y) * m + o.y);
    return q;
}
// --------------------------------------
// Point p1, p2 の間の距離の２乗を返す
function dist2(p1, p2) {
    var dx = p1.x - p2.x;
    var dy = p1.y - p2.y;
    return dx*dx + dy*dy;
}
// --------------------------------------
// PageItem item の中心の座標を返す
function getCenter(item){
    var gb = item.geometricBounds;  // [left, top, right, bottom]
    return new Point((gb[0] + gb[2]) / 2,
                     (gb[1] + gb[3]) / 2);
}
// --------------------------------------
function main(){
    // 選択範囲を取得。最背面は反転に使用する円
    var sel = activeDocument.selection;
    
    var circle = sel.pop();
    var o = getCenter(circle);
    var r = circle.width / 2;
    var r2 = r * r;

    for(var si = 0; si < sel.length; si++){
        var p = getCenter(sel[si]);
        var q = inverse(o, r2, p);
        
        if(q != Infinity){  // 無限遠は無視
            sel[si].translate(q.x - p.x, q.y - p.y);
        }
    }
}
main();

*1:Oが原点の場合

pythonのライブラリtriangleをIllustrator用に使ってみる

先日見つけた、pythonで三角形分割をするライブラリ triangle をIllustratorで使ってみるの巻。

このライブラリはドロネー三角形分割とかボロノイ分割に加えて、 高品質な三角形分割をするメソッドもあるのです。

三角形分割の品質を上げるには Ruppert’s algorithm などがあり、 仕組みは比較的シンプルなのですが実装するとなるととても面倒なのです。 ライブラリがあるなら使わない手はない、というわけです。

Illustratorからpythonを呼べればいいんですけど、
何かいい方法あるのかもしれませんが、
とりあえずファイルを介してデータをやりとりすることにします。

1. Illustratorで元になるパスを作る

文字をアウトライン化しました。

ベジエ曲線はpython側で扱えないので、 以前作ったスクリプト「 brokenCurve.jsx 」で曲線を直線に分割しました。

これは曲線部分の「高さ」が指定値以下になるように分割するやつで、

できればアンカー間の距離が近くなりすぎないような制限も入れたりしたいところですけど。 とりあえず。

直線化したもののグループと複合パスを解除して、 「穴」になる部分はまとめてグループ化して最前面にしておきます。
穴は分かりやすいように黄色にしました。

2. 座標の情報をファイルに書き出す

Illustratorのスクリプトで座標の情報をファイルに書き出します。

python側では “vertices”, “segments”, “holes” をキーとする辞書が必要ですので、 書き出すのはその元になる情報です。

vertices は2D座標の配列、 segments はverticesのインデックスのペアの配列です。 holes はオプションで、穴になる部分の内側の点の座標（穴ごとに１つ）の配列です。

function main(){
    var paths = [];
    var sel = activeDocument.selection
    extractGroup(sel, paths);
    // 穴は最前面のグループにする
    
    var vertices = [];  // 頂点座標(x, y)の配列
    var segments = [];  // 頂点インデックスのペアの配列
    var holes = [];     // 穴の中に含まれる座標(x, y)の配列

    // verticesとsegmentsの要素を生成
    var idx_base = 0;
    for(var ip = 0; ip < paths.length; ip++){
        var pp = paths[ip].pathPoints;
        
        for(var i = 0; i < pp.length; i++){
            var j = i == pp.length - 1 ? 0 : i + 1;
    
            var anc = pp[i].anchor;
            vertices.push(anc[0] + " " + anc[1]);
            
            var seg = (idx_base + i) + " " + (idx_base + j);
            segments.push(seg);
        }
        
        idx_base += pp.length;
    }

    // 穴の要素を生成（最前面がグループの場合）
    if(sel[0].typename == "GroupItem"){
        for(var i = 0; i < sel[0].pathItems.length; i++){
            with(sel[0].pathItems[i]){
                // 中心の座標を穴の目印にする
                holes.push((left + width / 2) + " " + (top - height / 2));
            }
        }
    }

    // ファイルに書き出し
    var fw = new File("~/data.txt");
    if(fw.open("w")){
        fw.write(vertices.join(",") + "\r\n");
        fw.write(segments.join(",") + "\r\n");
        fw.write(holes.join(",") + "\r\n");
        fw.close();
        alert("saved");
    } else {
        alert("failed to save");
    }
}

function extractGroup(sel, paths){
    for(var i = 0; i < sel.length; i++){
        if(sel[i].typename == "PathItem"){
            paths.push(sel[i]);
        } else if(sel[i].typename == "GroupItem"){
            extractGroup(sel[i].pageItems, paths);
        }
    }
}
main();

書き出されたファイルはこんな感じ。

175.3955078125 -36.068359375,174.177705535043 -31.5290598790816,...
0 1,1 2,2 3,3 4,4 5,5 6,6 0,7 8,8 9,9 10,10 11,11 12,12 13,13 14,...
170.613525390625 -32.98388671875,128.70361328125 -38.602783203125

3. pythonで処理

ファイルをpythonで読み取って処理します。

triangulateのオプションは色々あって、一部を挙げると、
“p” は Planar Straight Line Graph を構成します。穴がある場合はこれをやらないとダメっぽい。
“q” は 三角形の角が20度以下にならないように分割品質を向上させます。（角度は指定も可）
“a” は 三角形の最大の面積を制限します。値を小さくすると三角形の数が増えます。

triangulate が返す辞書には以下のキーがあります。 ‘segment_markers’, ‘segments’, ‘holes’, ‘vertices’, ‘vertex_markers’, ‘triangles’

ここでは vertices と triangles だけ使います。 triangles は頂点インデックス３つの組み合わせの配列です。

import numpy as np
import triangle

tri = {}
f = open("data.txt", "r")
r = f.readline().strip().split(",")
tri["vertices"] = np.array([map(float, x.split(" ")) for x in r])

r = f.readline().strip().split(",")
tri["segments"] = np.array([map(int, x.split(" ")) for x in r], dtype=np.int)

r = f.readline().strip().split(",")
if r[0] != "":
    tri["holes"] = np.array([map(float, x.split(" ")) for x in r])
f.close()

# triangulate!
result = triangle.triangulate(tri,'pqa10')

vs = result["vertices"]

fw = open("data_out.txt", "w")
for t in result["triangles"]:
    fw.write(\
      "%f %f" % tuple(vs[t[0]].tolist())\
      + " %f %f" % tuple(vs[t[1]].tolist())\
      + " %f %f" % tuple(vs[t[2]].tolist())\
      + "\n")
fw.close()

複雑な形状だと無理があるのか、実行すると時々pythonが異常終了します。 この例の場合は結局「tri」と「angle」で別々に処理しました。

書き出されたファイルはこんな感じ。

15.524214 -50.253923 17.989927 -52.059161 17.915429 -47.283785
16.083425 -39.977783 19.255991 -39.439819 17.169918 -36.654585
20.664551 -36.546631 18.826192 -33.653442 17.169918 -36.654585
...

4. Illustratorで描画

書き出したファイルをIllustratorのスクリプトで読み込んで描画させます。

function main(){
    var f = new File("~/data_out.txt");
    if(!f.open("r")){
        alert("failed to open");
        return;
    }
    var lines = f.read();
    f.close();

    var data = lines.split("\n");

    for(var i = 0; i < data.length; i++){
        var vs = data[i].split(" ");

        var r = [];
        for(var j = 0; j < vs.length; j+= 2){
            r.push([parseFloat(vs[j]), parseFloat(vs[j+1])]);
        }
        var path = activeDocument.activeLayer.pathItems.add();
        path.setEntirePath(r);
        path.closed = true;
    }
}
main();

これだけだと面白くないので、 以前作った「 noiseFill.jsx 」というスクリプトで色分けしました。

灰色だと寂しいので、 Illustratorの「カラーを編集」の機能で適当に再配色してみました。

なんとなく春らしく。

という感じです。

おしまい。