Distribute points on a circle as evenly as possible

Вы никогда не говорили, что "насколько равномерно распределены" точно измеряется. Полное среднеквадратичное отклонение размера интервала от размеров идеально разнесенных интервалов или что-то еще?

Если вы посмотрите на любой конкретный открытый интервал в начале, я считаю оптимальным решением, которое помещает k точки в этом интервале всегда будут располагать их равномерно. Следовательно, проблема сводится к выбору точек отсечки для минимального размера интервала, чтобы получить определенное количество промежуточных точек. Когда закончите, если у вас недостаточно очков для распределения, отбросьте по одной точке с каждого интервала от наибольшего к наименьшему и повторяйте, пока не получите что-то разумное.

Я не уверен, как лучше выбрать отсечки.

Предположим, что интервалы между точками равны a_1 ... a_n. Затем, если мы разделим каждый сегмент на части минимального размера d, мы сможем уместить в сегменте floor (a_i / d) - 1 точек. Это означает, что сумма (пол (a / d) для a in interval_lengths) должна быть больше или равна n + s , где n - количество точек, которые мы хотим добавить, а s - количество уже имеющихся точек. Мы хотим выбрать d как можно больше, вероятно, лучше всего выполнить двоичный поиск лучшего d.

После того, как мы выбрали d, просто проходите через каждый сегмент, добавляя точки через каждые d градусов, пока в сегменте не останется менее 2 d градусов.

Править все, что вам нужно, это найти d такое, что sum (floor (a / d) для a in interval_lengths) == n + s , затем назначьте floor (a_i / d) - 1 сегменту i каждые a_i / (floor ( a_i / d) - 1) градусов. Бинарный поиск быстро это найдет.

Дальнейшее редактирование

Вот код для поиска d

def get_d(n, a, lo=0, hi=None):
    s = len(a)
    lo = 360./(s + n)
    hi = 2. * lo
    d = (lo + hi)/2
    c = sum(floor(x/d) for x in a)
    while c != (n + s):
        if c < (n + s):
            hi = mid
        else:
            lo = mid
        d = (lo + hi)/2
        c = sum(floor(x/d) for x in a)
    return d

Сначала мы переопределяем термин следующим образом: Найдите такое распределение N точек, чтобы длина минимального расстояния между любой из двух точек и M заранее заданной была максимальной. Итак, ваша задача - найти этот максимум минимальной длины. Назовите это L У вас есть длина M существующих сегментов, предположим, что они хранятся в списке s . Итак, если эта длина равна L , прежде всего

min(s) > L

, а максимальное количество дополнительных точек составляет

 f(L) = sum(ls/L -1 for ls in s)

. Таким образом, вы можете найти оптимальное L, используя двоичный поиск, взяв начальный минимум L = 0 и максимум L = min ( s) и проверка условия, если sum (ls / L -1 for ls in s)> = N. Тогда для каждого отрезка s [i] вы можете просто равномерно разместить s [i] / L -1 точек. Считаю это оптимальным решением.

Обновлено Ошибка в мин (с)> L . Это было достаточно хорошо для нового определения термина, но ошибочно для оригинала.Я изменил это условие на max (s)> L . Также добавлен пропуск сегментов меньше L при бинарном поиске. Вот полный обновленный код:

from math import pi,floor
def distribute(angles,n):
    s = [angles[i] - angles[i-1] for i in xrange(len(angles))]
    s = [ls if ls > 0 else 2*pi+ls for ls in s]
    Lmin, Lmax = 0., max(s)
    while Lmax - Lmin >1e-9:
        L = (Lmax + Lmin)/2
        if sum(max(floor(ls/L) -1,0) for ls in s ) < n: Lmax = L
        else : Lmin = L
    L= Lmin
    p = []
    for i in xrange(len(s)):
        u = floor(s[i]/L) -1
        if u <= 0:continue
        d = s[i]/(u+1)
        for j in xrange(u):
            p.append(angles[i-1]+d*(j+1))
    return p[:n]
print distribute((0, pi/4),1)
print distribute((-pi,-pi/2,pi/2),2

One idea, write angles as list (in degrees):
    [30, 80, 120, 260, 310]
Convert to differences:
    [ 50, 40, 140, 50, 80]
Note that we wrap around 310 + 80 (mod 360) = 30, the first angle
For each point to be added, split the largest difference:
n=1, split 140:
    [50, 40, 70, 70, 50, 80 ]
n=2, split 80:
    [50, 40, 70, 70, 50, 40, 40]
Convert back to angles:
    [30, 80, 120, 190, 260, 310, 350]

Starting with array  [30, 80, 120, 260, 310] and adding n = 5 angles,
the given algorithm (see below) gives [30, 55, 80, 120, 155, 190, 225, 260, 310, 350]
with a root mean square of the differences between angles
   rms(diff) = sqrt[sum(diff * diff)] / n = 11.5974135047,
which appears to be optimal for practical purposes.

I propose that you consider the problem either as :

• A wrapped line - allowing you to determine inter-point distance easily, then re-map to the circle

or

• Consider the angles between points and the centre of the circle rather than arc distance. Again, this simplifies the positioning of new points, and is perhaps the easier candidate for re-mapping to circle-edge points. Find all angles between the already-placed points, then bisect the largest (or similar), and place the new point at the appropriate point on the circle edge.

Предположим, у вас уже есть M очков, и нужно добавить еще N . Если бы все точки были расположены равномерно, то между ними были бы промежутки 2 * pi / (N + M) . Итак, если вы разрежете свои точки M , чтобы получить сегменты угла M , вы, безусловно, можете поместить точки в сегмент (на равном расстоянии друг от друга), пока расстояние не станет меньше или равно 2 * пи / (N + M) .

Итак, если длина сегмента составляет L , тогда вы должны поместить этаж (L * (N + M) / (2 * pi)) - 1 точек в Это.

Теперь у вас останутся некоторые баллы. Ранжируйте сегменты по интервалу, который у вас был бы между точками, если бы была добавлена ​​еще одна точка. Фактически добавьте точку в сегмент с самым низким рейтингом. Снова вставьте его в отсортированный список и делайте это снова, пока у вас не закончатся баллы.

Поскольку каждый раз, когда вы помещаете точку в сегмент, результатом будут точки, расположенные как можно дальше друг от друга, а расстояние между точками не зависит от порядка, в котором вы их добавляли, вы получите оптимальный интервал.

(Правка: где «оптимальный» означает «максимальное минимальное расстояние между точками», то есть как можно лучше избегать наихудшего сценария, когда точки располагаются друг над другом.)

(Редактировать: Я надеюсь, что ясно, что идея состоит в том, чтобы решить, сколько точек входит в каждый сегмент, и затем только в самом конце, после того, как все числа будут определены, вы распределяете их поровну внутри каждого сегмента.)

У меня есть функция под названием «условие», которая принимает два аргумента - числитель (константа) и знаменатель (передача по ссылке). Он либо «увеличивает», либо «сжимает» значение знаменателя до тех пор, пока целое число «знаменателей» не поместится в числитель, то есть так, чтобы числитель / знаменатель был целым числом.

, увеличится или уменьшится знаменатель, зависит от того, какой из них приведет к его меньшему изменению.

Установите числитель на 2 * пи, а знаменатель на любое значение, близкое к желаемому интервалу, и у вас должно получиться довольно близкое к равномерному распределению.

Обратите внимание, что у меня также есть функция «сравнить», которая сравнивает два двойных значения на равенство в пределах определенного допуска.

bool compare( const double num1, const double num2, const double epsilon = 0.0001 )
{
     return abs(num1 - num2) < epsilon;
}

тогда функция условия будет

void condition(const double numerator, double &denominator)
{
  double epsilon = 0.01;
  double mod = fmod( numerator, denominator );
  if( compare(mod, 0) )
    return;
  if( mod > denominator/2 ) // decide whether to grow or shrink
    epsilon *= -1;

  int count = 0;
  while( !compare( fmod( numerator, denominator ), 0, 0.1) )
  {
    denominator += epsilon;
    count++;
    if( count > 10000 ) // a safety net
      return;
  }
}

Надеюсь, это поможет, я знаю, что этот маленький алгоритм мне очень пригодился несколько раз.