🔲

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

2023/02/03に公開

概要

この記事では2次ベジェ曲線のバウンディングボックスを求める方法を解説する。

求めるバウンディングボックスは2つあり、2次ベジェ曲線の3つの制御点(始点・制御点・終点)を囲む最小の矩形範囲(上記の青線)と、実際に引かれるベジェ曲線を囲む最小の矩形範囲(上記の橙線)になる。

まずは、計算が簡単な前者から解説する。

3つの制御点を囲む最小の矩形範囲を求める

type Point = {
  x: number;
  y: number;
};

const min = (a: Point, b: Point): Point => {
  return { x: Math.min(a.x, b.x), y: Math.min(a.y, b.y) };
};

const max = (a: Point, b: Point): Point => {
  return { x: Math.max(a.x, b.x), y: Math.max(a.y, b.y) };
};

const minP = min(min(p0, p1), p2); // 左上座標
const maxP = max(max(p0, p1), p2); // 右下座標

実際に引かれるベジェ曲線が各制御点を結んでできる三角形の外側に来ることがないので、各制御点の位置だけを考慮すればいい。各点が P_0,P_1,P_2 だとすると、 左上座標が min(p0, p1, p2) 、右下座標が max(p0, p1, p2) になる。

実際に引かれるベジェ曲線を含む最小の矩形範囲を求める

始点と終点に加えて、ベジェ曲線の山(上記の赤点)の位置を計算できれば矩形範囲が分かりそうである。

2次ベジェ曲線は名前の通り2次関数の式で定義できる。なのでその式の微分して、傾きが 0 になる場所を求めればいい。

P(t) = (1-t)^2⋅P_0 + 2⋅(1-t)⋅t⋅P_1 + t^2⋅P_2

上記は2次ベジェ曲線を2次関数の式で定義したものになる。

P'(t) = (-2+2t)⋅P_0+(2-4t)⋅P_1 + 2t⋅P_2

この式を微分する。

P'(t) = 2⋅t⋅(P_0 - 2P_1 + P_2) + 2⋅(P_1-P_0)

式を整理する。

P'(t) = 2⋅t⋅(P_0 - 2P_1 + P_2) + 2⋅(P_1-P_0) = 0

傾きが 0 になるように式を定義する。

t = \cfrac{P_0-P_1}{P_0-2P_1+P_2}

t = に変形する。

後はコードに落とし込むだけだが、いくつか注意点がある。

分母の P_0-2P_1+P_2 が 0 だとゼロ除算になるので、その場合は、始点から終点までの矩形範囲を求めればいい。

t < 0t > 1 になる場合は、始点か終点の外の位置が返ることになるので、t の範囲は 0~1 にクランプする必要がある。

const bezier2d = (p0: number, p1: number, p2: number, t: number): number => {
  return (1 - t) ** 2 * p0 + 2 * (1 - t) * t * p1 + t ** 2 * p2;
};

const clamp = (value: number, min: number, max: number): number => {
  return Math.max(Math.min(value, max), min);
};

const bezier2dBox = (p0: Point, p1: Point, p2: Point): Rect => {
  let minP = min(p0, p2);
  let maxP = max(p0, p2);

  if (p1.x < minP.x || p1.x > maxP.x || p1.y < minP.y || p1.y > maxP.y) {
    const t = { x: clamp((p0.x - p1.x) / (p0.x - 2 * p1.x + p2.x), 0.0, 1.0), y: clamp((p0.y - p1.y) / (p0.y - 2 * p1.y + p2.y), 0.0, 1.0) };
    const q = { x: bezier2d(p0.x, p1.x, p2.x, t.x), y: bezier2d(p0.y, p1.y, p2.y, t.y) };
    minP = min(minP, q);
    maxP = max(maxP, q);
  }

  return { x: minP.x, y: minP.y, width: maxP.x - minP.x, height: maxP.y - minP.y };
};

実装例1

https://twitter.com/BaroqueEngine/status/1620390989113479170

実装例2 (p5.js + TypeScript)

import p5 from "p5";

new p5((p: p5) => {
  type Point = {
    x: number;
    y: number;
  };

  type Rect = {
    x: number;
    y: number;
    width: number;
    height: number;
  };

  const min = (a: Point, b: Point): Point => {
    return { x: p.min(a.x, b.x), y: p.min(a.y, b.y) };
  };

  const max = (a: Point, b: Point): Point => {
    return { x: p.max(a.x, b.x), y: p.max(a.y, b.y) };
  };

  const bezier2d = (p0: number, p1: number, p2: number, t: number): number => {
    return (1 - t) ** 2 * p0 + 2 * (1 - t) * t * p1 + t ** 2 * p2;
  };

  const bezier2dOuterBox = (p0: Point, p1: Point, p2: Point): Rect => {
    let minP = min(min(p0, p2), p1);
    let maxP = max(max(p0, p2), p1);

    return { x: minP.x, y: minP.y, width: maxP.x - minP.x, height: maxP.y - minP.y };
  };

  const bezier2dBox = (p0: Point, p1: Point, p2: Point): Rect => {
    let minP = min(p0, p2);
    let maxP = max(p0, p2);

    if (p1.x < minP.x || p1.x > maxP.x || p1.y < minP.y || p1.y > maxP.y) {
      const t = { x: p.constrain((p0.x - p1.x) / (p0.x - 2 * p1.x + p2.x), 0.0, 1.0), y: p.constrain((p0.y - p1.y) / (p0.y - 2 * p1.y + p2.y), 0.0, 1.0) };
      const b = { x: bezier2d(p0.x, p1.x, p2.x, t.x), y: bezier2d(p0.y, p1.y, p2.y, t.y) };
      minP = min(minP, b);
      maxP = max(maxP, b);
    }

    return { x: minP.x, y: minP.y, width: maxP.x - minP.x, height: maxP.y - minP.y };
  };

  let a: Point;
  let b: Point;
  let c: Point;

  p.setup = () => {
    p.createCanvas(600, 400);
    p.background("#161616");

    p.noFill();
    p.stroke(240);

    a = { x: 100, y: 300 };
    b = { x: 450, y: 40 };
    c = { x: 550, y: 380 };

    p.push();
    p.line(a.x, a.y, b.x, b.y);
    p.line(b.x, b.y, c.x, c.y);

    p.strokeWeight(5);
    p.beginShape();
    p.vertex(a.x, a.y);
    p.quadraticVertex(b.x, b.y, c.x, c.y);
    p.endShape();
    p.pop();

    const outerBox = bezier2dOuterBox(a, b, c);
    p.push();
    p.strokeWeight(3);
    p.stroke("#009ad6");
    p.noFill();
    p.rect(outerBox.x, outerBox.y, outerBox.width, outerBox.height);
    p.pop();

    const box = bezier2dBox(a, b, c);
    p.push();
    p.strokeWeight(3);
    p.stroke("#ff9900");
    p.noFill();
    p.rect(box.x, box.y, box.width, box.height);
    p.pop();

    p.push();
    p.strokeWeight(3);
    p.fill("#161616");
    p.circle(a.x, a.y, 10);
    p.circle(b.x, b.y, 10);
    p.circle(c.x, c.y, 10);
    p.pop();
  };
});

Discussion