Алгоритм — рисовать заполненный круг пикселями от центра в C ++?
Я хочу нарисовать круг за линией (например, по часовой стрелке), пиксель за пикселем от центра круга. Но избегайте перерисовки пикселей (это медленно).
Представьте, что это похоже на «радар», который обновляется только один раз за ход.
Нет ОЗУ для хранения массива всех заполненных пикселей (максимум точек предыдущей линии) и нет графических процессоров или библиотек высокого уровня (рисование с помощью функции DrawPoint (x, y)).
У меня есть функции для рисования линии и точки:
void DrawLineFromCenterXYToAngle(int centerX, int centerY, float angle)
{
.... instead of angle it is possible to find points of the circle and iterate it
.... find line points by Bresenham's line algorithm
{
DrawPoint(int x, int y);
}
}
void DrawPoint(int x, int y)
{
PixelDraw_Slow(x,y)=GetColor_VerySlow(x,y);
}
Теперь я перебираю угол и очень медленно получаю круг, потому что пиксели в центре перерисовываются много раз. И нужна оптимизация.
Форма может быть не идеальным кругом, если это сделает его быстрее.
Решение
Есть алгоритм рисования Брезенхэма для кругов.
int r = 200, ymax, x, y, yp, xp, d;
ymax = r / sqrt(2);
x = r; /* start at the bottom of the first octant */
/* d measures whether the midpoint of two pixel locations
is inside or outside the ideal circle. positive means outside */
d = -1*r; /* to be precise, this should be r^2 - (r - 0.5)^2 */
xp = r; yp = -1; /* these hold the old values across iterations */
for(y=0; y<=ymax; y++) {
plot_8_ways(x,y);
if (d > 0) { /* midpoint is outside circle, go NW */
x--;
d += (2*yp - 2*xp + 3);
}
else { /* midpoint is inside circle, go N */
d += (2*yp + 1);
}
yp = y;
xp = x;
}
Другие решения
Нет ОЗУ для хранения массива всех заполненных пикселей (максимум точек предыдущей линии) и нет графических процессоров или библиотек высокого уровня (рисование с помощью функции DrawPoint (x, y)).
Если вы можете сохранить одну линию точек, то у вас будет достаточно памяти, чтобы отслеживать все заполненные пиксели, если вы представляете ее эффективно.
Предполагая, что ваша радиолокационная развертка начинается с позиции 12 часов или 6 часов (не имеет значения, будет ли она двигаться по часовой стрелке или против часовой стрелки), тогда в любой момент во время рендеринга круга вертикальная линия будет пересекаться только блок заполненных пикселей один раз (т.е. введите один раз и выйдите один раз). Таким образом, вы можете отслеживать их, просто сохраняя координаты вертикального минимума и максимального заполненного пикселя y для каждого столбца пикселей. Если вы начинаете с позиции 3 часа или 9 часов, то вы можете сохранить мин и макс х для каждой строки.
Вы можете просто сделать это с парой массивов:
int minY[X_RANGE];
int maxY[X_RANGE];
X_RANGE — максимальное количество столбцов пикселей. Это должно быть столько же, сколько ваш круг, а не весь экран, потому что вы можете сместить его, основываясь на левом Х ограничивающего прямоугольника круга. Аналогично, Y_RANGE — это максимальное количество строк.
Когда вы начнете рендеринг, инициализируйте массивы для представления пустых столбцов:
void InitColumnArrays()
{
for(int x = 0; x < X_RANGE; x++)
{
minY[x] = Y_RANGE - 1;
maxY[x] = 0;
}
}
Затем, когда вы визуализируете пиксель, просто проверьте, был ли он уже отрендерен, проверив массив:
void DrawPointCheckingRanges(int x, int y)
{
// TODO: range check values
// check if point has already been drawn and draw it and extend ranges if not:
if((y < minY[x]) || (y > maxY[x]))
{
DrawPoint(x + offsetX, y + offsetX);
if(y < minY[x])
minY[x] = y;
if(y > maxY[x])
maxY[x] = y;
}
}
offsetX и offsetY являются необязательными смещениями, как описано выше.
Вы можете использовать это в сочетании с алгоритмом рисования круга Брезенхэма из другого ответа, который даст вам эффективные конечные точки для ваших линий.
Приведенный выше код предполагает, что DrawPoint работает медленнее по сравнению с этими проверками границ и чтением и записью массива.