Нахождение мин / макс квадратичного Безье с CoreGraphics

Question

Я использую CoreGraphics для рисования квадратичной кривой Безье, но хочу вычислить минимальное / максимальное значение кривой. Я не из математического происхождения, так что это стало немного хлопотно. У кого-нибудь есть какие-нибудь статьи или идеи о том, как решить эту проблему?

Answer 1

Для квадратичного Безье это на самом деле довольно просто.

Определите ваши три контрольные точки как P0 = (x0,y0), P1 = (x1,y1) и P2 = (x2,y2). Чтобы найти экстремумы в x, решите это уравнение:

t = (x0 - x1) / (x0 - 2*x1 + x2)

Если 0 <= t <= 1, тогда оцените свою кривую на t и сохраните местоположение как Px. Сделайте то же самое для y:

t = (y0 - y1) / (y0 - 2*y1 + y2)

Опять же, если 0 <= t <= 1, оцените свою кривую на t и сохраните местоположение как Py. Наконец, найдите ограничивающий прямоугольник с осями, содержащий P0, P2, Px (если найдено) и Py (если найдено) Этот ограничивающий прямоугольник также будет тесно ограничивать вашу двумерную квадратичную кривую Безье.

Answer 2

Исчисление дает стандартную коробку трюков для нахождения минимума / максимума непрерывных, дифференцируемых кривых.

Вот пример обсуждения:

http://newsgroups.derkeiler.com/Archive/Comp/comp.graphics.algorithms/2005-07/msg00334.html

Answer 3

Я сделал это в javascript:

Jsfiddle link

function P(x,y){this.x = x;this.y = y; }
function pointOnCurve(P1,P2,P3,t){
    if(t<=0 || 1<=t || isNaN(t))return false;
    var c1 =  new P(P1.x+(P2.x-P1.x)*t,P1.y+(P2.y-P1.y)*t);
    var c2 =  new P(P2.x+(P3.x-P2.x)*t,P2.y+(P3.y-P2.y)*t);
    return new P(c1.x+(c2.x-c1.x)*t,c1.y+(c2.y-c1.y)*t);  
}
function getQCurveBounds(ax, ay, bx, by, cx, cy){
    var  P1 = new P(ax,ay);
    var  P2 = new P(bx,by);
    var  P3 = new P(cx,cy);
    var tx =  (P1.x - P2.x) / (P1.x - 2*P2.x + P3.x);
    var ty =  (P1.y - P2.y) / (P1.y - 2*P2.y + P3.y);
    var Ex = pointOnCurve(P1,P2,P3,tx);
    var xMin = Ex?Math.min(P1.x,P3.x,Ex.x):Math.min(P1.x,P3.x);
    var xMax = Ex?Math.max(P1.x,P3.x,Ex.x):Math.max(P1.x,P3.x);
    var Ey = pointOnCurve(P1,P2,P3,ty);
    var yMin = Ey?Math.min(P1.y,P3.y,Ey.y):Math.min(P1.y,P3.y);
    var yMax = Ey?Math.max(P1.y,P3.y,Ey.y):Math.max(P1.y,P3.y);
    return {x:xMin, y:yMin, width:xMax-xMin, height:yMax-yMin};
}