Distribute points on a circle as evenly as possible

Question

Hi SO community!

Problem statement

I have the following problem: I have a circle with a certain number (zero or more) of points on it. These positions are fixed. Now I have to position another set of points on the circle, such as all points together are as evenly distributed around the circle as possible.

Goal

My goal is now to develop a algorithm taking a list of angles (representing the fixed points) and an int value (representing how many additional points should be placed) and returning a list of angles again (containing only the angles where the additional points should lie).

The points dont have to be really evenly distributed (all same distance from each other), but rather as evenly as it is just possible. A perfect solution may not exist most of the time, as certain points are fixed.

The range of all angles lie in between -pi and +pi.

Examples

Some examples of what I am trying to archieve:

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]

or:

fixed_points = [-pi, -pi*3/4, -pi/4]

 v    v         v
 |---------|---------|---------|---------|
-pi     -pi/2        0        pi/2       pi

fill_circle(fixed_points, 6)

This last example should return something like: One point is to set right in between -pi*3/4 and -pi/4, that is: -pi/2 and distribute the other 5 points between -pi/4 and +pi (remember it is a circle, so in this case -pi = +pi):

 v    v    x    v   x   x    x   x    x
 |---------|---------|---------|---------|
-pi     -pi/2        0        pi/2       pi

Previous try

I started with a recursive algorithm that first searches for the largest interval between two points and sets the new point right in between. However it doesnt give satisfying results. Consider for example this configuration, with two points needed to be inserted:

 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

Not a very nice solution, as it could have been much better distributed (see above: -pi/6 and +pi/6).

Sorry for the long question, I hope you understand what I want to archieve.

I dont need a complete working algorithm, but rather the right idea for developing one. Maybe some pseudocode if you like. Would be very grateful for some hints to push me in the right direction. Thanks in advance!

Update: Completed algorithm:

Thank you all for your answers! It showed up I basically just needed a non-greedy version of my already existing algorithm. I really liked haydenmuhls idea to simplify the problem a little bit by encapsulating an interval/segment class:

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

This makes the actual algorithm incredibly easy and readable:

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

Answer 1

Suppose you have M points already given, and N more need to be added. If all points were evenly spaced, then you would have gaps of 2*pi/(N+M) between them. So, if you cut at your M points to give M segments of angle, you can certainly place points into a segment (evenly spaced from each other) until the space is less than or equal to 2*pi/(N+M).

So, if the length of a segment is L, then you should place floor(L*(N+M)/(2*pi)) - 1 points into it.

Now you're going to have some points left over. Rank the segments by the spacing that you would have between points if one more point was added. Actually add the point to the segment with lowest rank. Re-insert that one into your sorted list and do this again, until you run out of points.

Since at every time you're placing a point into a segment where the result will be points as widely spaced as possible, and space between points is not dependent on the order in which you added them, you will end up with the optimal spacing.

(Edit: where "optimal" means "maximal minimum distance between points", i.e. avoiding the worst-case scenario of points on top of each other as best as possible.)

(Edit: I hope it's clear that the idea is to decide how many points go into each segment, and then only at the very end, after the numbers have all been decided, do you space them out equally within each segment.)

Answer 2

Assume the intervals between the points are a_1 ... a_n. Then if we divide up each segment into pieces of minimum size d, we can fit floor(a_i/d) - 1 points in the segment. This means that sum(floor(a/d) for a in interval_lengths) must be larger than or equal to n + s where n is the number of points we want to add, and s is the number of points already there. We want to choose d as large as possible, it is probably best to just do a binary search for the best d.

Once we have chosen d, just step through each segment adding points every d degrees until there are less than 2 d degrees left in the segment

Edit all you need is to find d such that sum(floor(a/d) for a in interval_lengths) == n + s, then assign floor(a_i/d) - 1 to segment i every a_i/(floor(a_i/d) - 1) degrees. Binary search will find this quickly.

Further Edit

Here is code to find 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

Answer 3

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.

Answer 4

You never did say what "how evenly spaced" is measured precisely. Total root-mean-square variance of interval size from perfectly-spaced interval sizes, or something else?

If you look at any particular open interval at the beginning, I believe an optimal solution that places k points in that interval will always space them evenly. Therefore, the problem reduces to choosing cutoff points for what the minimum interval size is, to get a certain number of interstitial points. When done, if you have not enough points to distribute, drop one point from each interval from largest to smallest and repeat until you get something sane.

I'm not sure of the best way to choose the cutoffs, though.

Answer 5

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]

Answer 6

I have a function called "condition" which takes two arguments - a numerator (const) and a denominator (pass-by-ref). It either "grows" or "shrinks" the value of the demoniator until an integer number of "denominators" fit into the numerator, i.e. so that numerator/denominator is an integer.

whether the denominator is grown or shrunk depends on which one will cause it to change by a smaller amount.

Set numerator to 2*pi and denominator to anythink kind of close to the spacing you want, and you should have pretty close to even distribution.

8note that I also have a function "compare" which comapre two doubles for equality within a certain tolerance.

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

then the condition function is

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;
  }
}

hope it helps, i know this little algo has come in very handy for me a number of times

Answer 7

First we redefine term as follows: Find such distribution of N points, that the length of minimal distance between any of two point of these and M predefined is maximal. So your task is to find this maximum of minimal length. Call it L You have M lengths of existing segments, assume they are stored in list s. So if this length is L first of all

min(s) > L

and maximum amount of additional points is

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

So you can find optimal L using the binary search taking starting minimum L = 0 and maximum L = min(s) and checking condition if sum(ls/L -1 for ls in s) >= N. Then for each segment s[i] you can just place s[i]/L -1 of points evenly of it. I think this is optimal solution.

Updated There was flaw in min(s) > L. It was good enough for redefined term, but mistake for the original. I have changed this condition to max(s) > L. Also added skipping of segments smaller than L in binary search. Here is full updated code:

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

Answer 8

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.

Answer 9

You could use an Interval object. An interval is an arc of the circle between two of the original, immovable points.

The following is just pseudo-code. Don't expect it to run anywhere.

class Interval {

  private length;
  private point_count;

  constructor(length) {
    this.length = length;
    this.point_count = 0;
  }

  public add_point() {
    this.point_count++;
  }

  public length() {
    return this.length;
  }

  // The current length of each sub-interval
  public sub_length() {
    return this.length / (this.point_count + 1);
  }

  // The sub-interval length if you were to add another point
  public next_sub_length() { 
    return this.length / (this.point_count + 2);
  }

  public point_count() {
    return this.point_count;
  }
}

Create a list of these objects corresponding to the intervals between points on your circle. Each time you add a point, select the interval with the largest next_sub_length(). When you're done, it won't be hard to reconstruct the new circle.

This should give you the spacing with the the largest possible minimum interval. That is, if you score a solution by the length of its smallest interval, this will give you the highest score possible. I think that's what you've been shooting for.

Edit: Just realized that you specifically asked about this in Python. I'm quite a Python n00b, but you should be able to convert this to a Python object easily enough, though you won't need the getters, since everything in Python is public.