Рисование круга без расчета с плавающей запятой

Ответ 1

Из второго метода эта страница:

для каждого пикселя, оцените x ² + y ² и посмотрим, он находится в диапазоне от R ² -R + 1 до R ² + R включительно. Если это так, покрасьте на экране, а если нет, не делайте этого.

Дополнительные сведения и пояснения, приведенные на вышеупомянутой странице, но суть в том, что вы ищете пиксели, которые являются расстоянием между R-0.5 и R + 0.5 от начала координат, поэтому квадрат расстояния равен x ² + y ² а квадрат пороговых расстояний R ² -R + 0,25 и R ² + R + 0,25.

Для других методов Google "нарисует круг, используя только целочисленную арифметику".

Ответ 2

Алгоритмы Брешенхема, вероятно, являются ожидаемым ответом и могут быть получены без "сложной теории". Начните с точки (x,y) по кругу: (R,0) и сохраните значение d=x^2+y^2-R^2, изначально 0. D - это квадрат расстояния от текущей точки до круга. Мы увеличиваем Y и уменьшаем X по мере необходимости, чтобы сохранить D минимальным:

// Discretize 1/8 circle:
x = R ; y = 0 ; d = 0
while x >= y
  print (x,y)
  // increment Y, D must be updated by (Y+1)^2 - Y^2 = 2*Y+1
  d += (2*y+1) ; y++
  // now if we decrement X, D will be updated by -2*X+1
  // do it only if it keeps D closer to 0
  if d >= 0
    d += (-2*x+1) ; x--

Ответ 3

Честно говоря, не достаточно алгоритм окружности Midpoint? Просто отразите его во всех квадрантах. И во что бы то ни стало - если вы не пытаетесь получить работу в качестве тестера оконных приложений, Bresenham Line Algorithm не является сложной теорией.

Ответ 4

Довольно старый вопрос, но я постараюсь предоставить конечное решение визуальными тестами на python в качестве альтернативы алгоритму Брешенема - лучшим и самым коротким решением для этой задачи. Я думаю, что эта идея также может иметь место и, возможно, проще понять, но нуждается в большем количестве кода. Возможно, кто-то может оказаться в этом решении.

Идея основана на следующих фактах:

• Каждая точка на круге лежит на том же расстоянии, что и круглая центральная точка
• Круг содержит 4 квадранта, который начинается и заканчивается в точках (r, 0), (2r, r), (r, 2r) и (0, r), если r - радиус, а центральная точка - в (r, r).
• Круг является продолжением фигуры, и каждая точка может иметь 8 соседних точек. Если двигаться по кругу в одном направлении, нам интересны только три точки - 3 лежат в противоположном направлении, а 2 слишком далеко от центра. Например, для точки (r, 0) с направлением к (2r, r) интересными точками будут (r + 1, 1), (r, 1) и (r + 1, 0)

import matplotlib.pyplot as plt
from itertools import chain

def get_distance(x1, y1, x2, y2):
    """
        Calculates squared distance between (x1, y1) and (x2, y2) points
    """
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);

def get_next_point(x, y, dx, dy, cx, cy, r):
    """
        Returns the next circle point base on base point (x, y), 
        direction (dx, dy), circle central point (cx, cy) and radius r
    """
    r2 = r * r

    # three possible points
    x1, y1 = x + dx, y + dy
    x2, y2 = x, y + dy
    x3, y3 = x + dx, y

    # calculate difference between possible point distances 
    # with central point and squared radius
    dif1 = abs(get_distance(x1, y1, cx, cy) - r2)
    dif2 = abs(get_distance(x2, y2, cx, cy) - r2)
    dif3 = abs(get_distance(x3, y3, cx, cy) - r2)

    # choosing the point with minimum distance difference
    diff_min = min(dif1, dif2, dif3)

    if diff_min == dif1:
        return x1, y1
    elif diff_min == dif2:
        return x2, y2
    else:
        return x3, y3

def get_quadrant(bx, by, dx, dy, cx, cy, r):
    """
        Returns circle quadrant starting from base point (bx, by), 
        direction (dx, dy), circle central point (cx, cy) and radius r
    """
    x = bx
    y = by

    # maximum or minimum quadrant point (x, y) values
    max_x = bx + dx * r
    max_y = by + dy * r

    # choosing only quadrant points
    while (dx * (x - max_x) <= 0) and (dy * (y - max_y) <= 0):
        x, y = get_next_point(x, y, dx, dy, cx, cy, r)
        yield x, y

def get_circle(r, cx, cy):
    """
        Returns circle points (list) with radius r and center point (cx, cy)
    """
     north_east_quadrant = get_quadrant(cx, cy - r, 1, 1, cx, cy, r)
     south_east_quadrant = get_quadrant(cx + r, cy, -1, 1, cx, cy, r)
     south_west_quadrant = get_quadrant(cx, cy + r, -1, -1, cx, cy, r)
     north_west_quadrant = get_quadrant(cy - r, cy, 1, -1, cx, cy, r)

    return chain(north_east_quadrant, south_east_quadrant,
                 south_west_quadrant, north_west_quadrant)

# testing

r = 500

circle_points = get_circle(r, r, r)

for x, y in circle_points:
    plt.plot([x], [y], marker='o', markersize=3, color="red")

plt.show()

Ответ 5

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

Ответ 6

Здесь будет мой ответ (никаких исследований, это не на месте)...

Настройте два вложенных цикла, которые в совокупности обходятся по квадрату, определенному {-R, -R, 2R, 2R}. Для каждого пикселя вычислите (i ^ 2 + j ^ 2), где я и j - ваши переменные цикла. Если это находится в пределах некоторого допуска к R ^ 2, тогда цветьте этот пиксель черным, если не оставите этот пиксель отдельно.

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

Ответ 7

Вы можете легко вычислить x в x ^ 2 = r ^ 2- y ^ 2, используя приближение Тейлора первого порядка

sqrt (u ^ 2 + a) = u + a/2u

Это программа для этого в Mathematica (короткая, но, возможно, не хорошая)

 rad=87; (* Example *)
 Calcy[r_,x_]:= ( 
     y2 = rad^2 - x^2;
     u = Ordering[Table[ Abs[n^2-y2], {n,1,y2}]] [[1]]; (* get the nearest perfect square*)
     Return[ u-(u^2-y2)/(2 u) ]; (* return Taylor approx *)
 )

 lista = Flatten[Table[{h Calcy[rad, x], j x}, {x, 0, rad}, {h, {-1, 1}}, {j, {-1, 1}}], 2];
 ListPlot[Union[lista, Map[Reverse, lista]], AspectRatio -> 1];

Это результат

Не так уж плохо ИМХО... Я ничего не знаю о графических алгоритмах...

Ответ 8

Кто-нибудь подумал, что они могут искать боковой ответ, такой как "с компасом и карандашом" или "использовать внутреннюю часть рулона sellotape в качестве шаблона".

Каждый предполагает, что все проблемы должны быть решены с помощью компьютера.