Алгоритм рисования 4-х связной линии - PullRequest
Новая
       74

Алгоритм рисования 4-х связной линии

11 голосов
/ 04 марта 2011

Я ищу алгоритм (неплохо было бы написать код на Java, но все, что достаточно ясно для перевода на Java), чтобы нарисовать 4-соединенную линию. Кажется, что алгоритм Брезенхэма является наиболее широко используемым, но все понятные реализации, которые я обнаружил, 8-связны. Функция OpenCV cvline , очевидно, имеет версию с 4-мя связями, но исходный код для меня, как для посредственного и почти неграмотного программиста, непроницаем. Различные другие поиски ничего не дали.

Спасибо за любую помощь, которую может оказать любой.

Ответы [ 2 ]

14 голосов
/ 04 марта 2011

Ниже приведен алгоритм типа Брезенхема, который рисует 4-соединенные линии.Код написан на Python, но я думаю, что его легко понять, даже если вы не знаете язык. 

def line(x0, y0, x1, y1, color):
    dx = abs(x1 - x0)    # distance to travel in X
    dy = abs(y1 - y0)    # distance to travel in Y

    if x0 < x1:
        ix = 1           # x will increase at each step
    else:
        ix = -1          # x will decrease at each step

    if y0 < y1:
        iy = 1           # y will increase at each step
    else:
        iy = -1          # y will decrease at each step

    e = 0                # Current error 

    for i in range(dx + dy):
        draw_pixel(x0, y0, color)
        e1 = e + dy
        e2 = e - dx
        if abs(e1) < abs(e2):
            # Error will be smaller moving on X
            x0 += ix
            e = e1
        else:
            # Error will be smaller moving on Y
            y0 += iy
            e = e2

Идея состоит в том, что для рисования линии вы должны увеличивать X и Y с соотношением, которое соответствуетDX / DY теоретической линии.Для этого я начинаю с error variable e, инициализируемого 0 (мы находимся на линии), и на каждом шаге я проверяю, является ли ошибка ниже, если я только увеличиваю X или если я только увеличиваюY (проверка Брезенхэма - выбор между изменением только X или X и Y).

Наивной версией для этой проверки будет добавление 1/dy или 1/dx, но умножение всех приращений на dx*dyпозволяет использовать только целочисленные значения, что улучшает как скорость, так и точность, а также устраняет необходимость в особых случаях для dx==0 или dy==0, что упрощает логику.Конечно, поскольку мы ищем ошибку пропорции, использование масштабированного приращения не влияет на результат.

Независимо от того, является ли линейный квадрант, две возможности приращения всегда будут иметь различный эффект знака ошибки... поэтому мой произвольный выбор заключался в увеличении ошибки для шага X и уменьшении ошибки для шага Y.

Переменные ix и iy являются реальными направлениями, необходимыми для линии (либо+1 или -1) в зависимости от того, являются ли начальные координаты ниже или выше, чем конечные координаты.

Число пикселей, которые нужно нарисовать в 4-соединенной линии, очевидно, равно dx+dy, поэтому я просто делаюповторяйте это много раз, чтобы нарисовать линию, вместо того, чтобы проверять, добрался ли я до конечной точки.Обратите внимание, что этот алгоритм рисует все пиксели, кроме последнего;если вам также нужен этот последний пиксель, то после окончания цикла необходимо добавить дополнительный вызов draw_pixel.

Пример результата вышеописанной реализации можно увидеть на следующем рисунке

enter image description here

6 голосов
/ 24 января 2013

Для Python-неграмотных, вот C-версия кода 6502: 

void drawLine(int x0, int y0, int x1, int y1) {
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int sgnX = x0 < x1 ? 1 : -1;
    int sgnY = y0 < y1 ? 1 : -1;
    int e = 0;
    for (int i=0; i < dx+dy; i++) {
        drawPixel(x0, y0);
        int e1 = e + dy;
        int e2 = e - dx;
        if (abs(e1) < abs(e2)) {
            x0 += sgnX;
            e = e1;
        } else {
            y0 += sgnY;
            e = e2;
        }
    }
}
...