Довольно старый вопрос, но я постараюсь предоставить конечному решению визуальные тесты на 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()