일반적인 컴퓨터 이미지는 픽셀의 행렬로 이루어져 있으며, 각 픽셀은 특정 색의 작은 정사각형이다. 픽셀 행렬의 축에 완전히 평행하지 않은 선을 그리면 결함이 생기기 쉽다. 원은 그런 결함이 특히 두드러지는 대표적인 예이다.

2\mathbf{R}+1 by 2\mathbf{R}+1개의 픽셀로 이루어진 그림을 생각하자. 픽셀의 행과 열은 -\mathbf{R}부터 \mathbf{R}까지 번호가 매겨져 있으며, 가운데 픽셀은 (행 0, 열 0)에 있다. 처음에는 모든 픽셀이 흰색이다. 그 다음, 그림의 중심에 중심을 두고 반지름이 \mathbf{R}인 원을 아래 의사코드로 검은색으로 그릴 수 있다. 여기서 set_pixel_to_black(x, y)는 행 x, 열 y의 픽셀을 검은색으로 만든다.

draw_circle_perimeter(R):
  for x between -R and R, inclusive {
    y = round(sqrt(R * R - x * x))   # round to nearest integer, breaking ties towards zero
    set_pixel_to_black(x, y)
    set_pixel_to_black(x, -y)
    set_pixel_to_black(y, x)
    set_pixel_to_black(-y, x)
  }

이 코드에 의해 어떤 픽셀은 여러 번 검은색으로 설정될 수 있다. 하지만 이 연산은 멱등(idempotent)이다. 즉, 이미 검은색인 픽셀에 대해 set_pixel_to_black를 호출해도 아무것도 바뀌지 않는다.

다음은 (처음이 모두 흰색인 그림에서) 채워진 원을 그리는 함수의 의사코드이다.

draw_circle_filled(R):
  for x between -R and R, inclusive {
    for y between -R and R, inclusive {
      if round(sqrt(x * x + y * y)) <= R:
        set_pixel_to_black(x, y)
    }
  }

마지막으로, 다음은 채워진 원을 잘못 그리는 함수의 의사코드이다:

draw_circle_filled_wrong(R):
  for r between 0 and R, inclusive {
    draw_circle_perimeter(r)
  }

\mathbf{R}이 주어질 때, draw_circle_filled(\mathbf{R})를 호출한 그림과 draw_circle_filled_wrong(\mathbf{R})를 호출한 그림 사이에서 색이 서로 다른 픽셀의 개수를 구하라.

#10436 upload 1 done 1 how_to_reg 1

Pixelated Circle timer 10s memory 1024MB

#10436

Pixelated Circle 10s 1024MB