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

Question

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

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

Answer 1

Ниже приведен алгоритм типа Брезенхема, который рисует 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 теоретической линии. Для этого я начинаю с переменной ошибки 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 вызов должен быть добавлен после окончания цикла.

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

Answer 2

Для неграмотных на 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;
        }
    }
}

Answer 3

Цифровая прямая, соединяющая дробные координаты, может отличаться от прямой, соединяющей целочисленные координаты. В качестве примера рассмотрим изображение ниже, на котором показаны 4-связные цифровые прямые между точками (1, 1) – (6, 3), (1, 0,6) – (6, 2,6) и (1, 1,4). - (6, 3,4).

пример изображения

Хотя все начальные и конечные точки лежат на пикселях (1, 1) и (6, 4), цифровые прямые 4-связные линии различны.

Приведенный ниже код вычисляет 4-связную цифровую прямую между дробной начальной и конечной точкой. На самом деле код работает и для n измерений и вычисляет 2n-связную цифровую прямую.

      import numpy as np

def points_on_line(start, end):

    idx = np.round(np.array(start)).astype(int)
    end_idx = np.round(np.array(end)).astype(int)
    points = [idx]

    if np.all(idx == end_idx):
        return points

    diff = np.array(end, dtype=float) - np.array(start, dtype=float)
    direction = (diff / np.abs(diff)).astype(int)
    coord = np.array(start, dtype=float)

    while np.any(idx != end_idx):
        # compute how far we need to go to reach the side of the pixel at idx
        t = (idx + direction / 2 - coord) / diff
        i = np.argmin(t)
        coord += t[i] * diff
        idx = idx.copy()
        idx[i] += direction[i]
        points.append(idx)

    return points