🔲
2次ベジェ曲線のバウンディングボックスを求める
概要
この記事では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); // 右下座標
実際に引かれるベジェ曲線が各制御点を結んでできる三角形の外側に来ることがないので、各制御点の位置だけを考慮すればいい。各点が min(p0, p1, p2) 、右下座標が max(p0, p1, p2) になる。
実際に引かれるベジェ曲線を含む最小の矩形範囲を求める
始点と終点に加えて、ベジェ曲線の山（上記の赤点）の位置を計算できれば矩形範囲が分かりそうである。
2次ベジェ曲線は名前の通り2次関数の式で定義できる。なのでその式の微分して、傾きが 0 になる場所を求めればいい。
上記は2次ベジェ曲線を2次関数の式で定義したものになる。
この式を微分する。
式を整理する。
傾きが 0 になるように式を定義する。
t = に変形する。
後はコードに落とし込むだけだが、いくつか注意点がある。
分母の
t < 0 か t > 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
実装例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