Описание проблемы
У меня есть следующая проблема: у меня есть круг с определенным числом (ноль или более) точек на нем. Эти позиции фиксированы. Теперь я должен расположить еще один набор точек на круге, например, все точки вместе равномерно распределены по кругу, насколько это возможно.
Цель
Теперь моя цель - разработать алгоритм, содержащий список углов (представляющих неподвижные точки) и значение int (представляющее количество дополнительных точек) и снова возвращать список углов (содержащих только углы, в которых дополнительные пункты должны лежать).
Точки не должны быть действительно равномерно распределены (все одинаковое расстояние друг от друга), а скорее равномерно, насколько это возможно. Идеальное решение может не существовать большую часть времени, поскольку определенные точки фиксированы.
Диапазон всех углов лежит между -pi и + pi.
Примеры
Некоторые примеры того, что я пытаюсь архивировать:
fixed_points = [-pi, -pi/2, pi/2]
v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
fill_circle(fixed_points, 1)
# should return: [0]
fill_circle(fixed_points, 2)
# should return: [-pi/6, pi/6]
или
fixed_points = [-pi, -pi*3/4, -pi/4]
v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
fill_circle(fixed_points, 6)
В этом последнем примере нужно вернуть что-то вроде: одна точка должна установить прямо между -pi * 3/4 и -pi/4, то есть: -pi/2 и распределить остальные 5 точек между -pi/4 и + pi (помните, что это круг, поэтому в этом случае -pi = + pi):
v v x v x x x x x
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
Предыдущая попытка
Я начал с рекурсивного алгоритма, который сначала ищет самый большой интервал между двумя точками и устанавливает новую точку прямо между ними. Однако он не дает удовлетворительные результаты. Рассмотрим, например, эту конфигурацию с двумя точками, которые необходимо вставить:
v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
first step: insert right in the middle of largest interval
v v x v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
second step: insert right in the middle of largest interval
-> all intervals are evenly large, so one of them will be taken
v x v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
Не очень хорошее решение, так как оно могло быть гораздо лучше распределено (см. выше: -pi/6 и + pi/6).
Извините за длинный вопрос, надеюсь, вы понимаете, что я хочу архивировать.
Мне не нужен полный рабочий алгоритм, а правильная идея его разработки. Может быть, какой-нибудь псевдокод, если хотите. Был бы очень благодарен за некоторые намеки, чтобы подтолкнуть меня в правильном направлении. Спасибо заранее!
Обновление: завершенный алгоритм:
Спасибо всем за ваши ответы! Мне показалось, что мне просто нужна была не жадная версия моего уже существующего алгоритма. Мне очень понравилась идея haydenmuhls, чтобы немного упростить проблему, инкапсулируя класс интервалов/сегментов:
class Segment:
def __init__(self, angle, prev_angle, wrap_around):
self.angle = angle
self.length = abs(angle - prev_angle + \
(2*math.pi if wrap_around else 0))
self.num_points = 0
def sub_length(self):
return self.length / (self.num_points + 1)
def next_sub_length(self):
return self.length / (self.num_points + 2)
def add_point(self):
self.num_points += 1
Это делает алгоритм невероятно простым и понятным:
def distribute(angles, n):
# No points given? Evenly distribute them around the circle
if len(angles) == 0:
return [2*math.pi / n * i - math.pi for i in xrange(n)]
# Sort the angles and split the circle into segments
s, pi, ret = sorted(angles), math.pi, []
segments = [Segment(s[i], s[i-1], i == 0) for i in xrange(len(s))]
# Calculate the length of all subsegments if the point
# would be added; take the largest to add the point to
for _ in xrange(n):
max(segments, key = lambda x: x.next_sub_length()).add_point()
# Split all segments and return angles of the points
for seg in segments:
for k in xrange(seg.num_points):
a = seg.angle - seg.sub_length() * (k + 1)
# Make sure all returned values are between -pi and +pi
ret.append(a - 2*pi if a > pi else a + 2*pi if a < -pi else a)
return ret
