Rasterized solution in Clear category for Counting Tiles by PositronicLlama
"""
Use the midpoint circle algorithm (also known as Bresenham's circle algorithm)
to rasterize a circle and compute the perimiter and internal area.
"""
import math
def rasterize_octant(radius):
"""
Rasterize one octant of a circle with given radius centered at (-.5, -.5).
"""
# This is an inefficient version using sqrt.
# Could be optimized using iterative error term, as in:
#
y = 0
x = radius
xi = int(math.ceil(x) - 1)
while y <= x:
yield(xi, y)
x2 = x * x - 2 * y - 1
if x2 < 0:
break
new_x = math.sqrt(x * x - 2 * y - 1)
new_xi = int(math.ceil(new_x) - 1)
if new_xi != xi and new_xi >= y:
yield(new_xi, y)
x = new_x
xi = new_xi
y += 1
def checkio(radius):
"""
Measure the internal area and perimiter of a circle with the given radius.
"""
# The general process is:
# 1) Iterate over one octant of the circle (indicated by 'X' below)
# 2) If we continued past the x=y line, we would alsoi terate over the
# symmetrical points indicated by '.'
# 3) The quad perimiter can be determined by counting the enumerated points
# 4) The quad area is double the area under the octant curve, minus the
# double counted region (indicated by '+'s below):
# 6 . . . .
# 5 | | | . .
# 4 + + + + X X
# 3 + + + + + X X
# 2 + + + + + - X
# 1 + + + + + - X
# 0 + + + + + - X
# 0 1 2 3 4 5 6
ox, oy = None, None
oct_area = 0
for c, (x, y) in enumerate(rasterize_octant(radius), 1):
oct_area += x
if y == oy:
oct_area -= ox
ox, oy = x, y
if x == y:
# 8 times the octant area, minus four for the double counted endpoints.
perimiter = 8 * (c - 1) + 4
# 4 times double the octant area, minus (x + 1)^2 - 1.
area = 4 * (2 * oct_area - x * x - 2 * x)
else:
# This case should never happen, but in case it does,
# handle the last vertex being off the x=y line.
perimiter = 8 * c
area = 4 * (2 * oct_area - x * x + 1)
return [area, perimiter]
if __name__ == '__main__':
assert checkio(2) == [4, 12], "First, N=2"
assert checkio(3) == [16, 20], "Second, N=3"
assert checkio(2.1) == [4, 20], "Third, N=2.1"
assert checkio(2.5) == [12, 20], "Fourth, N=2.5"
Dec. 15, 2012
Forum
Price
Global Activity
ClassRoom Manager
Leaderboard
Coding games
Python programming for beginners