Нарисовать обводку эллипса

#алгоритм #графика #любой_язык

Как можно точно и быстро нарисовать обводку эллипса в канонической форме заданной
толщины? При этом используя только треугольники или отдельные пиксели. 

Сам-то эллипс можно, например, с помощью алгоритма Брезенхема или Midpoint circle,
а для обводки так сразу ничего не нашёл. Может быть, можно как-нибудь применить параметрические
уравнения обводки (двух её границ):



Здесь (x0, y0) точка на эллипсе, h — толщина обводки (больше 0 — внешняя, меньше
— внутренняя).

Обновление

Обводка эллипса — это область чёрного цвета на этом рисунке.



var a_canvas = document.getElementById("a");
var ctx = a_canvas.getContext("2d");

ctx.lineWidth = 20;
ctx.beginPath();
ctx.ellipse(100, 100, 50, 70, 0, 0, 2 * Math.PI);
ctx.closePath();
ctx.stroke();




  
  






    

Ответы

Ответ 1

Жирный эллипс - дело нехитрое. Берем неявно заданное уравнение эллипса:

F= x^2/a^2 + y^2/b^2 + z^2/c^2 = R^2


Для этого уравнения берем вектор нормали:

N{2x/a^2; 2y/b^2; 2z/c^2;}


Нормируем N, путем деления на длину.    

В каждой точке X нашей области, где сидит наш эллипс, проверяем, что:

F( X + e*N) * F(X - e*N) < 0


e - половина толщины обводки
X - координаты текущей точки

Если условие выполняется, рисуем черный пиксел


Ответ 2

Придумал такой алгоритм. Можно построить две кривые — границы обводки, и всё, что
между ними, закрасить. Эти кривые — эквидистанты, они равноудалены от эллипса. 

Для построения кривых можно использовать Midpoint-алгоритм, подобно тому, как это
делается для эллипса и круга. Правда, оптимизировать его аналогичным образом мне не
удалось. Уравнение сразу двух кривых в форме f(x,y) = 0 я взял отсюда (теорема 3).
 Точки, где производная равна единице, можно найти, подставив точку эллипса, где производная
единица, в уравнения в вопросе. Дополнительно, для внутренней эквидистанты, нужно найти
точки пересечения функции и OY и начинать алгоритм не с (a-h, 0), а с одной из точек,
как только две точки пересечения совпадут.

Можно строить эквидистанты только для эллипсов с a >= b, иначе поворачивать построенные
кривые.

В этом коде строятся только границы обводки:



const CHANNELS_PER_PIXEL = 4;

function calcFunc(x, y, a, b, h) {
    var a1 = a * a + b * b - x * x - y * y + h * h;
    var a2 = a * a * b * b - b * b * x * x - a * a * y * y + h * h * (a * a + b * b);
    var a3 = h * h * a * a * b * b;

    var a312 = a3 / a1 / a2;
    return 1 - 4 * a2 / a1 / a1 - 4 * a1 * a3 / a2 / a2 + 18 * a312 - 27 * a312 * a312;
}

function drawOutline(x0, y0, a, b, h, canvas) {
    var imageWidth = canvas.width;
    var imageHeight = canvas.height;
    var context = canvas.getContext('2d');
    var imageData = context.getImageData(0, 0, imageWidth, imageHeight);
    var pixelData = imageData.data;
    var makePixelIndexer = function (width) {
        return function (i, j) {
            var index = CHANNELS_PER_PIXEL * (j * width + i);
            return index;
        };
    };
    var pixelIndexer = makePixelIndexer(imageWidth);
    var drawPixel = function (x, y, col) {
        var r = (col >> 16) & 255;
        var g = (col >> 8) & 255;
        var b = col & 255;

        var idx = pixelIndexer(x, y);
        pixelData[idx] = r;
        pixelData[idx + 1] = g;
        pixelData[idx + 2] = b;
        pixelData[idx + 3] = 255;
    };
    var swap = false;
    if(b > a){
        swap = true;
        var t = a;
        a = b;
        b = t;
    }
    var draw4Pix = function(x, y, col){
        if(swap) {
            drawPixel(x0 - y, y0 - x, col);
            drawPixel(x0 - y, y0 + x, col);
            drawPixel(x0 + y, y0 - x, col);
            drawPixel(x0 + y, y0 + x, col);
        } else {
            drawPixel(x0 - x, y0 - y, col);
            drawPixel(x0 - x, y0 + y, col);
            drawPixel(x0 + x, y0 - y, col);
            drawPixel(x0 + x, y0 + y, col);
        }
    };

    var x = a + h;
    var y = 0;

    var lastX = a * a / Math.sqrt(a * a + b * b) + h / Math.sqrt(2);
    var prevX;
    while (true) {
        draw4Pix(x, y, 0xFF0000);
        y++;
        if (calcFunc(x - 0.5, y + 1, a, b, h) > 0) {
            x--;
        }
        if (x < lastX) {
            draw4Pix(x, y, 0xFF0000);
            prevX = x;
            break;
        }
    }
    if(prevX != 0) {
        x = 0;
        y = b + h;

        while (true) {
            draw4Pix(x, y, 0xFF0000);
            x++;
            if (calcFunc(x + 0.5, y - 1, a, b, h) > 0) {
                y--;
            }
            if (x >= prevX) {
                draw4Pix(x, y, 0xFF0000);
                break;
            }
        }
    }
    if(h < a && h < b){
        lastX = a * a / Math.sqrt(a * a + b * b) - h / Math.sqrt(2);
        var root = (Math.sqrt(a*a - b*b) * Math.sqrt(b*b - h*h))/b;
        if(h > b*b / a){
            x = Math.ceil(root);
        } else {
            x = a - h;
        }
        y = 0;
        if(x > lastX) {
            while (true) {
                draw4Pix(x, y, 0x0000FF);
                y++;
                if (calcFunc(x - 0.5, y + 1, a, b, h) < 0) {
                    x--;
                }
                if (x < lastX) {
                    draw4Pix(x, y, 0x0000FF);
                    prevX = x;
                    break;
                }
            }
        } else {
            prevX = Math.floor(root);
            draw4Pix(x, y);
        }

        if (prevX != 0) {
            x = 0;
            y = b - h;

            while (true) {
                draw4Pix(x, y, 0x0000FF);
                x++;
                if (calcFunc(x + 0.5, y - 1, a, b, -h) < 0) {
                    y--;
                }
                if (x >= prevX) {
                    draw4Pix(x, y, 0x0000FF);
                    break;
                }
            }
        }
    }
    context.putImageData(imageData, 0, 0);
}

function ellipseAndOutline(x0, y0, a, b, h, drawEllipse, canv){
    drawOutline(x0, y0, a, b, h, canv);
    if(drawEllipse) {
        var ctx = canv.getContext('2d');
        ctx.beginPath();
        ctx.lineWidth = 1;
        ctx.ellipse(x0, y0, a, b, 0, 0, Math.PI * 2);
        ctx.closePath();
        ctx.stroke();
    }
}

document.getElementById('btn').onclick = function () {
    var canv = document.getElementById('canv');
    var ctx = canv.getContext('2d');
    ctx.clearRect(0, 0, canv.width, canv.height);
    ellipseAndOutline(
        canv.width / 2, canv.height / 2,
        parseInt(document.getElementById('aInp').value),
        parseInt(document.getElementById('bInp').value),
        parseInt(document.getElementById('hInp').value),
        document.getElementById('drawEllCh').checked,
        canv);
}






    a 
    b 
    h 
    эллипс