Distribute points on a circle as evenly as possible

Question

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 don't 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 achieve:

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 doesn't 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 achieve.

I don't 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

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.