Zenn
🦊

3次ベジエ曲線のバウンディングボックス

2023/02/07に公開
p5.js
tech

3次ベジエ曲線のバウンディングボックスを求める。

コード

BD of bezier for article

// ばぐはっけん！
// これで落とす

function setup() {
  createCanvas(640, 640);
}

function draw(){
  background(255);
  const px = [113,540,341,208];
  const py = [271,210,522,154];

  drawBezier(px, py, 0, 96, 192);
}

function drawBezier(px,py,r,g,b){
  stroke(r,g,b);
  noFill();
  strokeWeight(2);
  bezier(px[0],py[0],px[1],py[1],px[2],py[2],px[3],py[3]);

  const data = getBezierBD(px, py);
  stroke(64,90);
  fill(r,g,b,40);
  rect(data.x, data.y, data.w, data.h);
}

function getPos(t,a,b,c,d){
  const m0 = pow(1-t,3);
  const m1 = 3*t*pow(1-t,2);
  const m2 = 3*t*t*(1-t);
  const m3 = t*t*t;
  return m0*a+m1*b+m2*c+m3*d;
}

// これで極値が出る
function getCritical(a,b,c,d){
  const _D = pow(b-c,2)-(a-b)*(c-d);
  if(_D<0){ return []; }
  if(c-d==0 && b-c ==0){ return []; }
  if(c-d==0){
    const x0 = -(a-b)/(2*(b-c)); // ばぐ！！
    if(x0>0){
      return [x0/(x0+1)];
    }else{
      return [];
    }
  }
  const _E = Math.sqrt(_D);
  const x1 = (-b+c+_E)/(c-d);
  const x2 = (-b+c-_E)/(c-d);
  const result=[];
  if(x1>0){result.push(x1/(x1+1));}
  if(x2>0){result.push(x2/(x2+1));}
  return result;
}

function getBezierBD(px, py){
  const results = [0,1];
  results.push(...getCritical(...px));
  results.push(...getCritical(...py));
  
  // mapが便利
  const xData = results.map(t => getPos(t, ...px));
  const yData = results.map(t => getPos(t, ...py));

  // reduceの方が多いときとか安全らしいので
  const minX = xData.reduce((a, b) => min(a, b), Infinity);
  const maxX = xData.reduce((a, b) => max(a, b), -Infinity);
  const minY = yData.reduce((a, b) => min(a, b), Infinity);
  const maxY = yData.reduce((a, b) => max(a, b), -Infinity);

  return {x:minX, y:minY, w:maxX-minX, h:maxY-minY};
}

説明

関数getCriticalはベジエ曲線をx軸方向、y軸方向に分けてそれぞれについて極値を求める。求まったらそれに対応する点を求めて端点とともにgetBezierBD内で考慮する。それによりx方向、y方向の最大最小を求めて長方形を作る。
計算には微分を用いる。2次方程式になったり1次方程式になったりするので場合分けが重要で、これをうまく分けないとコーナーケースで引っかかることになる。

数式による解説

3次ベジエ曲線は~x,y~共に4つの数~a,b,c,d~により、

f(t) = a(1-t)^3 + 3b(1-t)^2 t + 3c(1-t)t^2 + dt^3 ~~~~(0 \leq t \leq 1)

という形であらわされるので、これの極値を求めればよい。0と1は端点として別に考慮すればよいので考えない。これを微分するわけだが、展開してからだと煩雑になるので、このまま合成関数の微分則を使って計算する方が楽。

f'(t) = (-3a+3b)(1-t)^2 + (-6b+6c)(1-t)t + (-3c+3d)t^2

とし、これが0になる点を~0<t<1~の範囲で求めるのだが、もちろん展開はしない。0になるところを出せばよいのだから、両辺を~(-3)(1-t)^2~で割って、

(c-d)\left( \frac{t}{1-t} \right)^2 + 2(b-c)\left(\frac{t}{1-t}\right) + (a-b)=0

を解けばよい。変数変換で、

r = \frac{t}{1-t}~~~~(r>0,~~0<t<1)

とすれば~r~についての2次以下の方程式になる。2次「以下」というのは1次方程式になる場合もあるからである（いわゆる退化）。これの解として~r~を求めたうえで、正のものだけ取り上げて、

t=\frac{r}{1+r}

で~t~に戻して出力すればよい。

b=c=dの場合を除く理由

~b=c=d~の場合、~a=b~なら直線だし、そうでないなら解が存在しないので、考える必要はない。だから除いてある。たとえばそれが~x~で起こった場合、~y~の方で考慮した結果がバウンディングボックスを求める際の情報を提供する（しない場合もある）。

2次ベジエ曲線の場合

この場合は2次式を微分するので簡単になる。一応コードも載せておく。この場合の式は、

f(t) = a(1-t)^2 + 2b(1-t) t + ct^2 ~~~~(0 \leq t \leq 1)

となる。

function setup() {
  createCanvas(640, 640);
}

function draw(){
  background(255);
  const px = [100, 450, 550];
  const py = [300, 40, 380];

  drawQuadratic(px, py, 0, 96, 192);
}

function drawQuadratic(px,py,r,g,b){
  stroke(r,g,b);
  noFill();
  strokeWeight(2);

  beginShape();
  vertex(px[0], py[0]);
  quadraticVertex(px[1], py[1], px[2], py[2]);
  endShape();

  const data = getQuadraticBD(px, py);
  stroke(64,90);
  fill(r,g,b,40);
  rect(data.x, data.y, data.w, data.h);
}

function getQuadPos(t,a,b,c){
  const m0 = pow(1-t,2);
  const m1 = 2*t*(1-t);
  const m2 = t*t;
  return m0*a+m1*b+m2*c;
}

// これで極値が出る
function getCritical(a,b,c){
  if(b-c ==0){ return []; }

  const x0 = -(a-b)/(b-c); // こんだけ！
  if(x0>0){
    return [x0/(x0+1)];
  }
  return [];
}

function getQuadraticBD(px, py){
  const results = [0,1];
  results.push(...getCritical(...px));
  results.push(...getCritical(...py));
  
  // mapが便利
  const xData = results.map(t => getQuadPos(t, ...px));
  const yData = results.map(t => getQuadPos(t, ...py));

  // reduceの方が多いときとか安全らしいので
  const minX = xData.reduce((a, b) => min(a, b), Infinity);
  const maxX = xData.reduce((a, b) => max(a, b), -Infinity);
  const minY = yData.reduce((a, b) => min(a, b), Infinity);
  const maxY = yData.reduce((a, b) => max(a, b), -Infinity);

  return {x:minX, y:minY, w:maxX-minX, h:maxY-minY};
}

蛇足：曲線の一部のバウンディングボックスを求める場合

たとえば~0.2\leq t \leq 0.8~に対する曲線の一部分のバウンディングボックスが欲しい場合もあるかもしれない。そういう場合は、

  const results = [0,1];
  results.push(...getCritical(...px));
  results.push(...getCritical(...py));

ここを、~t_0\leq t \leq t_1~までほしいとして、

  let results = [t0,t1];
  results.push(...getCritical(...px));
  results.push(...getCritical(...py));
  
  results = results.map(t => constrain(t, t0, t1));

とすればいい。あとはすべて同じ。

Discussion