Add and Removing Elements on the Circumference of a Circle

Question

I am trying to spawn entities on the circumference of a circle.

These entities may be removed at any time, including all of them being removed.

Periodically I would like to add an element on the circle at the furthest distance from all other entities, but I cannot figure out the math.

The basics is to add an entity at the midpoint between the two neighbors that have the greatest distance between them.

My pseudo code is -

positions = []
radius = 40
max_angle = 0
if positions.size() == 0:
  positions.append( {x: radius, y: 0} )
elif positions.size() == 1:
  positions.append( {x: -positions[0].x, y: -positions[0].y })
elif positions.size() > 1:
  for i in [0 to positions.size()]:
    p1 = positions[i]
    p2 = positions[i + 1 % positions.size()]
    angle = atan2(p2.y - p1.y, p2.x - p1.x)
    if angle > max_angle:
      temp = {x: cos(angle/2) * radius, y: sin(angle/2) * radius}
  positions.append(temp)

Everything breaks down in my for loop when trying to calculate the third point. This is because the angle after 2 iterations is 0, and results in a bad spawn.

My knowledge of geometry is not really good enough for me to figure out what I should be doing here.

I have some work arounds which would involve adding static points on the circle, or redistributing points along the circle on a new spawn, but it would be pretty cool if I could get this function able to automatically find the correct mid point.

Any help or direction is appreciated.

Answer 1

Firstly, atan2(p2.y - p1.y, p2.x - p1.x) isn't what you want, as that just gives the direction between the two points, not the distance, so comparing atan2(p2.y,p2.x) and atan2(p1.y,p1.x) is closer to what you want.

That still leaves an annoying edge case at the discontinuity when the atan2 jumps between -pi and pi, so I'd suggest calculating the biggest gap in a different way. You don't need the actual size of the gaps, you just need to compare relative sizes, so you could just use the direct square of the distance between the points instead of an angle: (p2.y-p1.y) * (p2.y-p1.y) + (p2.x-p1.x) * (p2.x-p1.x). This is faster to calculate, and completely avoids the discontinuity.

Even simpler would be a dot product: dot(p1,p2) = p1.x * p2.x + p1.y * p2.y, although in that case you need to reverse the comparison order: the dot product gets bigger when the points get closer together.

BTW, these solutions only work for points on the circumference - if you were wanting to compare general angles between points at varying distances from the center, you could use the dot product, but would have to normalize by dividing by distances from the center.