Циркуляция 2d массива с использованием алгоритма линии Брезенхэма

Question

Циркуляция 2d массива с использованием алгоритма линии Брезенхэма

В данный момент я пытаюсь нарисовать некоторые наклонные линии, используя алгоритм линий Брезенхэма, который может распространять двумерный массив размером 21×21, в виде линии, расположенной под углом от 0 до 2pi.

линии из Брезенхэма

Таким образом, идея заключается в том, что программа должна выводить значения, через которые проходят строки в сетке.

Итак, пример с 5х5

Angle:0
_ _ _ _ _
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|.|.|.|
|_|_|_|_|_|
|_|_|_|_|_|

Angle: 45
_ _ _ _ _
|_|_|_|_|.|
|_|_|_|.|_|
|_|_|.|_|_|
|_|_|_|_|_|
|_|_|_|_|_|

и так далее..

Проблема здесь в том, что моя программа не выглядит так, как будто … Конечная точка находится в пределах заданной длины радиуса.

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

#include <iostream>
#include <math.h>
using namespace std;
typedef std::pair<int,int> coordinate;

int sign(double x ){ return (x > 0) ? 1 : ((x < 0) ? -1 : 0); }

coordinate endpoint(double angle, int x1 , int y1, int lenght)
{
double radians = (M_PI/180)*angle;

double x2 = x1 + (lenght * cos(radians));
double y2 = y1 + (lenght * sin(radians));

return std::make_pair(round(x2),round(y2));
}

void bresenham(coordinate start, coordinate end)
{
//restriction a.x < b.x  and 0 < H/W < 1
int y =  start.second;
int w = end.first - start.first;
int h = end.second - start.second;
int f = 2*h-w; // current error term

for (int x = start.first; x<= end.first; x++)
{
cout << "mark: " << x << "," << y << endl;
if (f < 0)
{
f = f + 2*h;
}
else
{
y++;
f=f+2*(h-w);
}
}
}int main(int argc, const char * argv[])
{

coordinate start = make_pair(0,0);
for (int i = 0; i <= 45; i++)
{
coordinate end = endpoint(i,0,0,10);
cout << "    endPos: "<< "(" << end.first <<","  << end.second   <<")"    << " Angle: " << i << "       " << endl;
cout << "--------------------------------------------" << endl;
bresenham(start, end);
cout << "--------------------------------------------" << endl;
}

return 0;
}

Вот выход.

    endPos: (10,0) Angle: 0
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
endPos: (10,0) Angle: 1
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
endPos: (10,0) Angle: 2
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
endPos: (10,1) Angle: 3
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 4
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 5
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 6
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 7
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 8
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,2) Angle: 9
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 10
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 11
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 12
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 13
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 14
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,3) Angle: 15
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
endPos: (10,3) Angle: 16
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
endPos: (10,3) Angle: 17
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
endPos: (10,3) Angle: 18
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
endPos: (9,3) Angle: 19
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,3
mark: 9,3
--------------------------------------------
endPos: (9,3) Angle: 20
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,3
mark: 9,3
--------------------------------------------
endPos: (9,4) Angle: 21
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 22
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 23
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 24
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 25
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 26
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,5) Angle: 27
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (9,5) Angle: 28
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (9,5) Angle: 29
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (9,5) Angle: 30
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (9,5) Angle: 31
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (8,5) Angle: 32
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,3
mark: 5,3
mark: 6,4
mark: 7,4
mark: 8,5
--------------------------------------------
endPos: (8,5) Angle: 33
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,3
mark: 5,3
mark: 6,4
mark: 7,4
mark: 8,5
--------------------------------------------
endPos: (8,6) Angle: 34
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 35
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 36
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 37
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 38
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 39
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 40
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,7) Angle: 41
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,4
mark: 6,5
mark: 7,6
mark: 8,7
--------------------------------------------
endPos: (7,7) Angle: 42
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
endPos: (7,7) Angle: 43
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
endPos: (7,7) Angle: 44
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
endPos: (7,7) Angle: 45
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------

Что я делаю неправильно? … Я знаю, что алгоритм Брезенхэма, возможно, придется изменить, чтобы преодолеть уклоны больше 1 и ниже 0.

—Обновление Уточните проблему —

Я пытаюсь перебрать 2d массив по кругу, используя алгоритм линии Брезенхема.

Алгоритм должен начинаться с центра массива 2d и «выбрасывать» луч под углами от 0 до 2pi. Луч должен начинаться от центра и заканчиваться на краю матрицы, надеюсь, это имеет больше смысла ..

 _ _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|.|.|.|.|.|.|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|

_ _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|.|.|
|_|_|_|_|_|_|_|_|.|_|_|
|_|_|_|_|_|_|_|.|_|_|_|
|_|_|_|_|_|_|.|_|_|_|_|
|_|_|_|_|_|.|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|

1

arrays bresenham c++math raster

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

У вас есть Брезенхэм только для первого Октанта (dx>=0,dy>=0,dx>=dy)

поэтому, когда вы используете углы снаружи <0,45> градусов это не будет работать должным образом. У вас есть больше возможностей для решения этой проблемы:
- использовать 8 веток каждая с собственной интерполяцией ( dx>=0, dx<0 combined with dy>=0, dy<0)
- использовать 2 ветви ( |dx|>=|dy|, |dx|<|dy| ) здесь вместо x++,y++,x--,y-- использование x+=sx,y+=sy вместо того, где sx,sy направление шага, предварительно вычисленное перед интерполяцией. (в как м автоматически модифицируемые константы обычно используются, но в C / C ++ вам нужны переменные для этого)
Не забудьте использовать как главная ось интерполяции тот, с большее абсолютное изменение Так что если (|dx|>=|dy|) главная ось x что значит x увеличивается (дек) в каждом for пройти и y только в if заявление…
конечная точка неверна

Как отметил Нико Шертлер, конечные точки ошибочны. Используйте в качестве радиуса большую половину размера вашей матрицы и измените интерполяцию по Брезенхэму, чтобы остановить, когда x или же y выходит из диапазона матрицы …

Другой вариант — установить большую ось на ребро матрицы (зависит от октантов) и вычислить вторую ось с помощью sin или же cos (это 90 градусный треугольник)

0