Software Development

I've been trying to solve this problem for a very long time now. I finally found the solution and this is one of those times where once you have the answer, you feel pretty stupid. That's a good thing... sorta. It means the answer was extremely simple. On the flip side, it means you missed something obvious.

Ok, here's the problem at hand. Say you have X random points on the circumference of a circle. What I want to do is take X evenly distributed points on the same circumference of the circle, but make sure that the total distance between each of the new points and old points is at a minimum.

Another way to state this is by how much do I need to rotate the evenly spaced points so that the total angular difference between each point and its respective original point is the least possible.

The main purpose was to create evenly spaced points where I move the original points the least possible. I tried all sorts of things. I tried averaging the angles, averaging the (x,y) coordinates of the points, etc. None of them worked. Some looked like they gave close results. To test my answers, I ran an algorithm that basically checked 1000 different angles and picked the one with the least distance.

So what was the answer? Ends up being easy as pie. But a little background on the setup.

1. First, we draw our X points.
2. Then we draw another X points that are evenly spaced starting at angle 0. So divide 360 by X and that's the angle that each of these points will be separated by.
3. Calculate the difference in angle between each pair of points (ie. between point 1 in the original list and point 1 in the evenly spaced list, same for point 2, etc.). Don't adjust for anything. Keep the difference negative if it ends up being negative.
4. Sort the list of differences.

Step #4 is the critical point and is where the solution comes from. In order to understand this, there is a little trick that explains why this solution works. Note that by sorting the points by difference, they are no longer in the original order that they appeared. This is why it wasn't intuitive. But now that I HAVE thought of it, it's so simple I feel stupid.

Suppose you have four points that have negative differences and four points that have positive differences. Now suppose you move the evenly distanced points counterclockwise by 10 degrees. What will happen to the total angular difference?

The answer is NOTHING, except in ONE SPECIAL CASE.

Why nothing? Because in 4 pairs of points, those points will get closer to each other (the points in the pairs that is), while in the other 4 pairs, they will get further away from each other thus canceling each other out.

Here's a simple example. Suppose pair A has a difference of -30 degrees and pair B has a difference of +40 degrees. Then if we move the evenly spaced points by 10 degrees, we now have differences of -20 and +50 degrees. The total difference is still 70 degrees in both cases. Nothing has changed.

But there is ONE case where this is not true. It's where there are more points on one side than the other. Where there are more pairs with negative differences than positive or vice versa. (Also, if there is a negative difference that is less than 10 degrees. That would flip it to the other side and cause the same scenario just described.)

So if we have 2 point pairs that have negative difference and 1 point pair that has positive difference, then moving the evenly spaced points by 10 degrees will mean that TWO point pairs will get closer to each other while only one will get further apart thus causing a decrease in total difference.

A diff = -40 degrees
B diff = -20 degrees
C diff = +50 degrees

Total difference = 40+20+50 = 110 degrees.

Now we move the evenly spaced points clockwise by 10 degrees.

A diff = -30 degrees
B diff = -10 degrees
C diff = +60 degrees

Total difference = 30+10+60 = 100 degrees.

We've now reduced the total angular difference by 10 degrees.

So the key is to rotate the evenly spaced points until there are as many negative differences as there are positive differences and that's easy to do.

Once our differences are sorted, all you do is take the center difference in the sorted list and that's your angular offset for the evenly spaced points. If there are an even number of points, then you take the two center differences and average them and that's your offset.

So that's it. Just sort the angular differences of each pair of points and take the center one. That's your rotational offset.

So simple it hurts.

Here's a picture of what I'm doing. The inside points are the random points. The outside points are the evenly spaced points. The green dot near the center is the average of all the (x,y) coordinates of all the random points. Thought that might be a clue to what direction to rotate, but ended up being a red herring. That angle is represented by the blue line. The pink line represents the above algorithm and you'll see that the back end always ends up being directly between the first and last point. The gray points were calculated using the 1000 offsets.

[click on image for larger version]


edit: Wanted to add that this algorithm works for linear points as well, not just angular values.