Illustratorの曲線の交点を抽出するスクリプト

あけましておめでとうございますです。皆様におかれましてはご清祥のこととお慶び申し上げる次第でございます。ということで始まっちゃった2025年ですが、年始はやっぱりスクリプト書かないと落ち着かないTenです。
ということで書きました。Ilustratorの曲線２つの交点を計算するやつです。

仕組み的には…
ベジェ曲線って交点を数学的にポンっと計算できません。ChatGPTとかに聞くと面白いんですけど、３次のベジェの数式に対してニュートン法をつかって追い込んだりといった提案をしてくれます。動くものが出来た試しがないんですけど…
で、今回のものは２つのパスオブジェクトのgeometricBoundsの交差を判定基準として追い込むという手法を取っています。すご〜くスタンダードなベジェ曲線の操作ですね。では細かい処理をまとめておきましょう。

1. ２つのパスオブジェクトのgeometricBoundsを取得
2. これらが交差するエリアを計算、交差しない場合はパスは交わっていない
3. 交差する場合、パスを半分に分割する
4. 分割したもののうち交差する部分のパスの組を更に分割して交差する部分を半分に分割する
5. 以下繰り返し

という具合です。おおよその場合、この処理を10回程度繰り返せばIllustratorのパスの精度である800ppi以下の精度まで追い込むことが可能です。
ここで、手動でこのプロセスを行った場合を見てみましょう。

こちらのスクショは４回めの状態を表します。これだけで随分とエリアが絞り込まれているのが見て取れます。

最終的にはこのように0.01mm程度のエリアに絞り込まれます。これは10回目の結果となります。最終的にはこの追い込んだ四角いエリアの中心点を交点としてピックアップします。

さて、やること自体は非常に単純だということをおわかり頂けただろうということで、一番処理が面倒そうな部分、曲線の分割という部分なんですが、ここはデ・カステリョのアルゴリズムを使います。

デ・カステリョアルゴリズムを利用した制御点計算
元の制御点
p0 : 始点アンカー
p1 : 始点ハンドル
p2 : 終点ハンドル
p3 : 終点アンカー
分割後の制御点 指定したtの値で次の中間点を計算
q0 = (1−t)*p0 + t*p1
q1 = (1−t)*p1 +t*p2
q2 =(1−t)*p2 +t*p3
さらに分割して:
r0 =(1−t)*q0 +t*q1
r1 =(1−t)*q1 +t*q2
最後に
b = (1−t)r0 +tr1
b : 曲線上の点（すでに計算されているアンカーポイント）
r0, r1 : 分割後の新しい制御点の位置

数式を見ると結構複雑に感じますが、やってることはアンカーとハンドルの距離等をtの割合で分割してベジェ曲線上の点とその制御点を新たに得るというものです。
今回は中点を拾うのでt=0.5となります。セグメントを構成するハンドルを半分の長さにハンドル同士を結んだ線分の中点と半分の長さになったハンドルから結び出来た２本の線分の中点同士を結べはその線分の中心が元のベジェ曲線のセグメントに重なります。その部分が求める新しいアンカーポイントの位置となります。
これを描画すると以下のようになります。

で、このような計算で分割した点のanchorやdirectionを計算して利用しますが、今回は実際には数値だけを利用してアンカーポイントを追加したり削除したりはしません。
本当は交差エリアでパスをぶった切りながら回すのが良いのですが演算負荷が大きくなることを鑑みて単純な手順になる真ん中でぶった切って交差する方を利用するような手法を取っています。なので、実際のコードでは再帰処理を回す際に４パターンチェックしながら回します。

var sel = app.activeDocument.selection;
alert(getIntersectPoints(sel[0],sel[1]));

function getIntersectPoints(path1,path2)
{
if (path1.typename!=="PathItem" && path2.typename!=="PathItem") return false;
var tolerance = 0.01; //許容誤差
var intersections = [];

//各セグメントを比較
for (var i=0; i<path1.pathPoints.length-1; i++)
{
var p0a = path1.pathPoints[i].anchor;
var p1a = path1.pathPoints[i].rightDirection;
var p2a = path1.pathPoints[i+1].leftDirection;
var p3a = path1.pathPoints[i+1].anchor;

for (var j=0; j<path2.pathPoints.length-1; j++) 
{
  var p0b = path2.pathPoints[j].anchor;
  var p1b = path2.pathPoints[j].rightDirection;
  var p2b = path2.pathPoints[j+1].leftDirection;
  var p3b = path2.pathPoints[j+1].anchor;
  findIntersections(p0a, p1a, p2a, p3a, p0b, p1b, p2b, p3b);
}

}

if (intersections.length>0)
{
var pts =[];
var n = 0;
pts.push(intersections[0])
for (var k=0; k<intersections.length; k++)
{
if (distanceCheck(pts[n],intersections[k]))
{
pts.push(intersections[k]);
n++;
}
}

var clr= new CMYKColor();
clr.cyan = 0;
clr.magenta = 0;
clr.yellow = 0;
clr.black = 75;

for (var k=0; k<pts.length; k++) 
{
  var point = pts[k];
  var maru = app.activeDocument.pathItems.ellipse(point[1]+2, point[0]-2, 4, 4);
  maru.stroked = false;
  maru.filled = true;
  maru.fillColor = clr;
}
return pts.length;

}
else
{
return false;
}
function deCasteljau(p0, p1, p2, p3, t)
{
function interpolate(a, b, t)
{
return [(1-t)a[0] + tb[0], (1-t)a[1] + tb[1]];
}
var q0 = interpolate(p0, p1, t);
var q1 = interpolate(p1, p2, t);
var q2 = interpolate(p2, p3, t);
var r0 = interpolate(q0, q1, t);
var r1 = interpolate(q1, q2, t);
var b = interpolate(r0, r1, t);
return {left: [p0, q0, r0, b], right: [b, r1, q2, p3]};
}

function getBoundingBox(p0, p1, p2, p3)
{
var xValues = [p0[0], p1[0], p2[0], p3[0]];
var yValues = [p0[1], p1[1], p2[1], p3[1]];
return {
minX: Math.min.apply(null, xValues),
maxX: Math.max.apply(null, xValues),
minY: Math.min.apply(null, yValues),
maxY: Math.max.apply(null, yValues)
};
}

function isBoundingBoxIntersecting(box1, box2)
{
return (
box1.minX <= box2.maxX && box1.maxX >= box2.minX &&
box1.minY <= box2.maxY && box1.maxY >= box2.minY
);
}

function findIntersections(p0a, p1a, p2a, p3a, p0b, p1b, p2b, p3b)
{
var box1 = getBoundingBox(p0a, p1a, p2a, p3a);
var box2 = getBoundingBox(p0b, p1b, p2b, p3b);
if (!isBoundingBoxIntersecting(box1, box2))
{
return;
}

if (Math.abs(box1.maxX-box1.minX)<tolerance && Math.abs(box1.maxY-box1.minY)<tolerance) 
{
  var x = (box1.minX + box1.maxX) / 2;
  var y = (box1.minY + box1.maxY) / 2;
  intersections.push([x, y]);
  return;
}

// 曲線を分割
var curve1 = deCasteljau(p0a, p1a, p2a, p3a, 0.5);
var curve2 = deCasteljau(p0b, p1b, p2b, p3b, 0.5);

// 分割後のセグメントを再帰的にチェック
findIntersections(
  curve1.left[0], curve1.left[1], curve1.left[2], curve1.left[3],
  curve2.left[0], curve2.left[1], curve2.left[2], curve2.left[3]
);
findIntersections(
  curve1.left[0], curve1.left[1], curve1.left[2], curve1.left[3],
  curve2.right[0], curve2.right[1], curve2.right[2], curve2.right[3]
);
findIntersections(
  curve1.right[0], curve1.right[1], curve1.right[2], curve1.right[3],
  curve2.left[0], curve2.left[1], curve2.left[2], curve2.left[3]
);
findIntersections(
  curve1.right[0], curve1.right[1], curve1.right[2], curve1.right[3],
  curve2.right[0], curve2.right[1], curve2.right[2], curve2.right[3]
);

}

function distanceCheck(p0, p1)
{
var dst = Math.sqrt((p1[0]-p0[0])(p1[0]-p0[0]) + (p1[1]-p0[1])(p1[1]-p0[1]))
if (dst<tolerance*2) return false;
return true;
}
}

Illustrator上で交差するパス２つ選択した状態でこのスクリプトを実行すると交差部分をマークしたうえで何箇所交差しているかアラートを出してくれます。

パスの方は各セグメント毎にチェックしますので交点は全てピックアップ可能です。また、処理の性質上重複でピックアップしてしまう可能性がありますのでピックアップ後に距離が近すぎるものは省いています。あと、閉図形は最後のセグメントを見る事が出来ないので正常に処理されません。これは最初のパスポイントの情報を最後に付加することで回避可能なんですけどやってませんので誰かやってください。