Постановка задачи
У меня следующая проблема: у меня есть круг с определенным числом (ноль или более) точек на нем.Эти позиции фиксированы.Теперь мне нужно расположить другой набор точек на окружности, например, чтобы все точки были равномерно распределены по кругу.
Цель
Моя цель сейчас состоит в том, чтобы разработать алгоритм,список углов (представляющих фиксированные точки) и значение 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