# Algorithm for minimizing distance between points in two sets.

This topic is 3683 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Guys, I have run into the following problem which I can't find a good algorithm for. Suppose I have a circle in 2 dimensions with a radius 1. I place points p1, p2, ..., pN in this circle at random. Each point is represented in polar coordinates as a pair (r, theta), where r can change from [0 to 1] and theta can change from [0 to 2pi). Then I take another circle and place points p1, p2, ..., pN in the circle at random the same way. Now I want to a find rotation angle for 2nd circle, such that the distance between points in both circles was minimal. I can only think of a brute force algorithm. With a small step (something like 2*pi/1000), rotate all points pi, and find the minimal distance between each pi and pi. Any other ideas? Sincerely, Stan

##### Share on other sites
Let me give an example, so it was clear what I am trying to do.

Suppose the first circle contains just one point p1 = (1, pi), and the second circle contains a point p1 = (1, pi/2). Then if I rotated the second circle for pi/2 degrees, points p1 and p1 would align and distance between them would be 0.

Also, the number of points in both circles is the same.

##### Share on other sites
I'm not quite sure what you're trying to achieve here. If the points are randomly distributed, unless I'm mistaken the average distance between pi and p'i tends towards the distance between the center points of the circles as N increases. In other words, for randomly distributed points any orientation is likely as good as any other - what you're doing will only produce meaningful results I think if the points have some pattern to their distribution rather than purely random.

##### Share on other sites
Sounds like http://en.wikipedia.org/wiki/Marriage_problem
The taxi example reads almost exactly like what I understood from your problem (taxis = circle 1, passengers = circle 2, time = polar distance). So one of the solution algorithms there should help you.

##### Share on other sites
Quote:
 Original post by samothSounds like http://en.wikipedia.org/wiki/Marriage_problemThe taxi example reads almost exactly like what I understood from your problem (taxis = circle 1, passengers = circle 2, time = polar distance). So one of the solution algorithms there should help you.

I'm not sure that this is the same problem. My understanding of the problem was that the total distance sum(pi - p'i, 0, N) should be minimized by rotating the points p' by a fixed angle. The assignment problem would find the pairs (pi, p'j) [note the different indices] such that the summed distance between the points in each pair is minimized. My assumption about the original problem may be incorrect however! :)

##### Share on other sites
So are the circles both always located at the origin? If that is the case, then you could take all of the radii, keeping track which corresponds to which point, and sort them. Then find the minimum difference between two radii of the two different circles by simply traversing through the sorted list. Now this minimum radii will also be the minimum distance and you'll just need to figure out the rotation angle, which will be easy knowing the points corresponding to the minimum radii difference.

If the circles are not centered at the same point, I'll have some other ideas ;)

##### Share on other sites
Quote:
 Original post by IsoOctaneSo are the circles both always located at the origin? If that is the case, then you could take all of the radii, keeping track which corresponds to which point, and sort them. Then find the minimum difference between two radii of the two different circles by simply traversing through the sorted list. Now this minimum radii will also be the minimum distance and you'll just need to figure out the rotation angle, which will be easy knowing the points corresponding to the minimum radii difference.If the circles are not centered at the same point, I'll have some other ideas ;)

Unfortunately I don't think this is right either. This just aligns the point from each circle with the longest radius to each other, all of the other points may lie on the opposite side of the circle and thus the total distance of all the points could be greater.

As I said earlier, you can come up with any sort of heuristic you want to rotate the points, but in reality for random point configurations no one orientation is better than any other according to the original metric (as I understand it). If the metric changes, then maybe you have options :)

##### Share on other sites
Quote:
 Unfortunately I don't think this is right either. This just aligns the point from each circle with the longest radius to each other, all of the other points may lie on the opposite side of the circle and thus the total distance of all the points could be greater.As I said earlier, you can come up with any sort of heuristic you want to rotate the points, but in reality for random point configurations no one orientation is better than any other according to the original metric (as I understand it). If the metric changes, then maybe you have options :)

But does it really matter if the points are random or not, the algorithm should work on any *given* set of points, no matter how they were generated? Surely you can't come up with an orientation which would be better for any random set of points, but for a single set of known points you can. I'm not sure my algorithm will work, but I think it certainly does something more than what you suggested ;)

##### Share on other sites
Quote:
 Original post by IsoOctaneBut does it really matter if the points are random or not, the algorithm should work on any *given* set of points, no matter how they were generated? Surely you can't come up with an orientation which would be better for any random set of points, but for a single set of known points you can. I'm not sure my algorithm will work, but I think it certainly does something more than what you suggested ;)

Sure your algorithm does something, but it doesn't do what the OP asked :) It aligns the point in p' with the longest radius to the point in p with the longest radius. This doesn't take any of the other points into account and therefore achieves nothing with regards to minimizing the distance between corresponding points in the 2 sets, which is what the OP asked for. It is very simple to come up with a point configuration in which your algorithm makes the total distance worse.

What I'm saying is that as N increases, the average distance between randomly distributed points will tend towards the distance between the centers of the circles regardless of orientation. The original post is trying to find the global minimum of an almost flat solution space, so any result you produce is going to be practically as good as choosing an orientation at random.

##### Share on other sites

Both circles are located at origin. Both circles have the same radius.

There will be times when points are distributed randomly in each circle, and there will also be cases (more often than randomly distributed) when they are some rotation angle away.

This rotation must be applied to all the points in the second circle (my original problem has rotation symmetry (around axis perpendicular to plane of circle, and going through its origin))

I'll add another example with more points.

Example
-------

Suppose we have N = 4 (4 points).

In the first circle they might place like this:
p1 = (0.95, 0), p2 = (0.87, pi/2), p3 = (1, pi), p4 = (0.78, 3pi/2).
(Notice that they are close to r = 1, and separated by angle pi/2)

And points in the second circle might place like this:
p1 = (1, pi/2 + alpha), p2 = (0.92, pi + alpha), p3 = (0.84, alpha), p4 = (0.99, 3pi/2 + alpha), where alpha is some arbitrary angle.

Now, if I rotated all the points in the second circle by an angle -alpha (minus alpha), then they would be placed at
p1 = (1, pi/2), p2 = (0.92, pi), p3 = (0.84, 0), p4 = (0.99, 3pi/2)

It is easy to see that:
p1 is very close to p3
p2 is very close to p4
p3 is very close to p2 and
p4 is very close to p`1

My goal is to find this angle 'alpha'.

Thanks!

• 12
• 40
• 15
• 10
• 23
×

## Important Information

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!