Рисунок почти прямой линии

Question

Я получил эти массивы, представляющие квадратную бумагу, или, может быть, пиксели, если хотите. Для согласованности в этом потоке пусть «1» представляет собой черную ячейку, «0» представляет собой белую ячейку.

Теперь я хочу нарисовать (черную) прямую линию от точки А до точки В. Я не могу просто использовать ваниль http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm, потому что мне нужно очернить каждую ячейку, которая была бы удалена, если бы это был лист квадрат бумаги и вы нарисовали линию от центра квадрата а в центре квадрата В.

Таким образом, они должны работать следующим образом:

+—+—+—+ +—+—+—+ 
|A| | | |█| | | 
+—+—+—+ +—+—+—+ 
| | | | |█|█| | 
+—+—+—+ +—+—+—+ 
| | | | → | |█|█| 
+—+—+—+ +—+—+—+ 
| | |B| | | |█| 
+—+—+—+ +—+—+—+ 

+—+—+—+ +—+—+—+ 
|A| | | |█| | | 
+—+—+—+ +—+—+—+ 
| | | | → | |█| | 
+—+—+—+ +—+—+—+ 
| | |B| | | |█| 
+—+—+—+ +—+—+—+ 

+—+—+—+ +—+—+—+ 
|A| | | → |█|█| | 
+—+—+—+ +—+—+—+ 
| | |B| | |█|█| 
+—+—+—+ +—+—+—+ 

вы можете себе представить, эти эскизы, чтобы быть более квадратично например, или фактически набросать это на лист квадратной бумаги! Это может прояснить ситуацию.

И, как всегда, не стесняйтесь публиковать все, что может помочь. Благодаря!

---

(А) Раствор

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

X 0 1 2  X 0 1 2 
Y +—+—+—+ → Y +—+—+—+ 
0 |A| | | → 0 |█| | | 
    +—+—+—+ → +—+—+—+ 
1 | | | | → 1 |█|█| | 
    +—+—+—+ → +—+—+—+ 
2 | | | | → 2 | |█|█| 
    +—+—+—+ → +—+—+—+ 
3 | | |B| → 3 | | |█| 
    +—+—+—+ → +—+—+—+ 

Существо (0,0) =: (а1, а2), В является (2,3) = (b1, b2), поэтому ожидаемый набор точек {(0,0) , (0,1), (1,1), (1,2), (2,2), (2,3)}

Сначала мы оформляем прямую, которая будет нарисована на реальной бумаге.

Therefore first define constant m which holds our slope: 

    (b2 - a2) 
m = ————————— 
    (b1 - a1) 

For arbitrary (A, B), the straight is now defined by: 
g: y = (x - a1) · m + a2 

and inverted: 
ǵ: x = (y - a2)/m + a1 

Note that for m = 0, the whole thing does fail. But a straight-to-the-right line does not only sound like a straightforward thing. 

в этом примере, стрит

m = 3/2 
g: y = x * 3/2 
ǵ: x = y * 2/3 

Мы будем кормить эти функции с «значениями строк» ​​(точно между 2 целыми числами х и х + 1, широко известной как «х и на половину ") в нашей ограничительной рамке. Итак, сначала мы будем идти между a1 и b1 (фуражная г), то между а2 и b2 (фуражная ǵ):

g(0.5) = 1/2 * 3/2 = 0.75 // 1 < g(0.5) + 0.5 < 2 
g(1.5) = 3/2 * 3/2 = 2.25 // 2 < g(1.5) + 0.5 < 3 

ǵ(0.5) = 1/2 * 2/3 = 0.33 // 0 < ǵ(0.5) + 0.5 < 1 
ǵ(1.5) = 3/2 * 2/3 = 1 // 1 < ǵ(1.5) + 0.5 < 2 
ǵ(2.5) = 5/2 * 2/3 = 1.66 // 2 < ǵ(2.5) + 0.5 < 3 

1. Первое означает, что прямая пересекает первую вертикальную линию выше (показано как «ниже») первая горизонтальная линия. Очки для черных: (0,1), (1,1).
2. Второй означает, что прямой пересекает вторую вертикальную линию над второй горизонтальной линией. Точки чернеют: (1,2), (2,2).
3. Третий означает, что прямой пересекает первую горизонтальную линию после (показанную как «справа») 0-ю вертикальную линию. Очки для черных: (0,0), (0,1).
4. Четвертое означает, что прямой пересекает вторую горизонтальную линию после первой вертикальной линии. Точки чернеют: (1,1), (1,2).
5. Пятое означает, что прямой пересекает третью горизонтальную линию после второй вертикальной линии. Точки чернеют: (2,2), (2,3).

Все точки: {(0,1), (1,1), (1,2), (2,2), (0,0), (0,1), (1,1), (1,2), (2,2), (2,3)}

Без дублирует: {(0,0), (0,1), (1,1), (1,2), (2,2), (2,3)} (что точно так, как ожидалось)

• Итак, для линии, которая пересекает y't h вертикальной линии над x'-го горизонтальной, мы рисуем (x-1, y) и (x, y) черные.
• Хотя для линии, пересекающей x-ю горизонтальную линию после y-го вертикального, мы рисуем (x, y-1) и (x, y).
• (не обязательно здесь) И для линии, которая пересекает x'-го горизонтального прямо на y-й вертикальной, рисуем для m> 0 (x-1, y-1) и (x, y). Если m < 0, это сделало бы для (x-1, y) и (x, y-1)

Ощущается, что это так.

Любые мысли? Прокомментируйте, пожалуйста!

~ LDer ~

Answer 1

Давайте предположим, что мы работаем с этим примером:

+—+—+—+ +—+—+—+ 
|A| | | |█| | | 
+—+—+—+ +—+—+—+ 
| | | | |█|█| | 
+—+—+—+ +—+—+—+ 
| | | | → | |█|█| 
+—+—+—+ +—+—+—+ 
| | |B| | | |█| 
+—+—+—+ +—+—+—+ 

Это прямоугольник 3x4.

Нам необходимо определить две функции:
y(x) = 4 * (1 - x/3)
x(y) = 3 * (1 - y/4).

Теперь перейдем к ним все целые x и y внутри нашего прямоугольника.
На каждом шаге мы рисуем черный пиксель с координатами
[x; ceil(y(x)) - 1] и [ceil(x(y)) - 1; y - 1]:

y(0) == 4  # paint 0;3 
y(1) == 2.(6) # paint 1;2 
y(2) == 1.(3) # paint 2;1 

x(0) == 3  # paint 2;-1 (-1 is not a valid pixel coordinate, 
       # so we may just throw away this, as there are no pixels below y=0) 
x(1) == 2.25 # paint 2;0 
x(2) == 1.5 # paint 1;1 
x(3) == 0.75 # paint 0;2 

Оба x(y) и y(x) функции, давая вам второй координаты точки по диагонали, и когда мы передаем целые значения для них мы находим пересечения нашей диагонали с сеткой.
y -функция даст нам все пиксели, которые соответствуют каждой вертикальной линии, и x -функция, которые находятся ниже каждой горизонтали (вот почему y - 1). Единственная проблема будет заключаться в пересечении углов, ее можно решить еще одним условным.

Answer 2

Инициализация Дайте вершины ваших "квадратов" координаты (x,y). Для каждого квадрата, v1 вверху слева, v2 справа вверху, v3 внизу справа и v4 внизу слева. Вычислите уравнение вашей линии y = a*x + b.

Алгоритм

For each square do 
    for each vertex of the square do 
     calculate valueOfVertex = y - a*x - b 
    if two valueOfVertex have an opposite sign 
    then cellColor == 1 
    else cellcolor == 0 

Вывод должен быть то, что вы ожидаете. Единственная проблема может быть, если один valueOfVertex = 0 и все остальные являются строгими положительными или отрицательными. Но с ним легко справиться.

Пояснение Если линия пересекает квадрат (или пиксель), вы можете найти две вершины, которые не находятся на одной стороне линии. Таким образом, одна лежит в положительной полуплоскости, другая - в отрицательной полуплоскости.

Улучшение Некоторые простые трюки помешают вам проверить каждый квадрат ограничивающей рамки. Если вы найдете квадрат, который находится полностью в полуплоскости, вы можете отбросить некоторые квадраты. В ваших примерах, если тестируемый квадрат выше линии, вы можете отбросить все квадраты, которые находятся выше и справа.