4

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

Сам-то эллипс можно, например, с помощью алгоритма Брезенхема или 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();
<!DOCTYPE html>
<html>

<body>
  <canvas id="a" width="200" height="200">
  </canvas>
</body>

</html>

3
  • Попробуйте найти ответ тут math.stackexchange.com или перевести вопрос на английский и там задать. Тут больше по-программированию вопросы, на такой узкий математический вопрос врядли ответят.
    – nick_n_a
    15 мар 2018 в 10:11
  • Не понятно, вы хотите нарисовать один эллипс внутри другого? Наверное у этих эллипсов должны совпадать фокусы? 16 мар 2018 в 3:26
  • @АндрейNOP нет, я же написал: обводку эллипса, то есть границу эллипса заданной толщины. И границы обводки, очевидно, не эллипсы (судя хотя бы по параметрическим уравнениям) 16 мар 2018 в 3:38

2 ответа 2

2

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

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 - координаты текущей точки

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

9
  • Мне не очень понятно. Во-первых, меня интересуют двумерные случаи и эллипсы в канонической форме. Ваше уравнение эллипса этому не соответствует. Во-вторых, что значит «область, где сидит наш эллипс» ? И как вы получили последнее неравенство? 16 мар 2018 в 4:30
  • 1
    Ну, выбросьте из уравнения координату Z, будет двумерный. Из уравнения в канонической форме можно получить неявное, так как оно - самое общее. Последнее неравенство - это условие "если точка находится между двух эквидистант к нашему эллипсу". Эквидистанта - геометрическое место точек, отстоящих на равное расстояние от заданной кривой. Область, где сидит наш эллипс - это прямоугольник с центром, совпадающим с точкой пересечения полуосей эллипса и с размерами, равными этим полуосям+2*e
    – gbg
    16 мар 2018 в 4:34
  • Каноническое уравнение и так неявное, там a и b в квадрате и нет R... Но это не очень существенно, можно и так. В какой точке нужно считать нормированный вектор N в последнем неравенстве? 16 мар 2018 в 4:51
  • @pocketgulag в точке X конечно же! А точка X - бегает по прямоугольнику. Если у вас научная статья, можете сослаться на мою статью с этим алгоритмом, дам выходные данные.
    – gbg
    16 мар 2018 в 4:53
  • 2
    Производная неправильно вычислена. Делить надо на a^2 и b^2, а не умножать. И потом, чем ближе характеристическое произведение F()*F() к 0, тем ближе к границе находимся. Можно сгладить, если надо.
    – gbg
    16 мар 2018 в 5:47
0

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

Для построения кривых можно использовать 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);
}
<!DOCTYPE html>
<html>
<head>
</head>
<body>
<form id="paramFrm">
    a <input type="text" id="aInp" size="4" value="50">
    b <input type="text" size="4" id="bInp" value="50">
    h <input type="text" size="4" id="hInp" value="10">
    эллипс <input type="checkbox" id="drawEllCh"> <input type="button" id="btn" value="->">
</form>
<canvas id="canv" width="400" height="400">
</canvas>
</body>
</html>

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.