Jump to content
  • Advertisement
Sign in to follow this  
IsaacShui

A circle optimization problem

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

In 2D space, given a radius rc of a circle C, several points p1, p2, ..., pn (n<=10), and another circle D ( the radius of D is rd, and center is Cd) Find the center of C (denoted as Cc) such that C can include the most points. However, Cc must be in D and be the point most closest to Cd of the solutions. The solution of Cc can not be the best but the algorithm must be efficient, because the algorithm executes on-the-fly. Thank you in advance.

Share this post


Link to post
Share on other sites
Advertisement
Do you have any simplifying assumptions or other information about the relative distances/magnitudes? If the pointes tend to be tightly grouped relative to the radii of the circles near the center of D, then the algorithm for that situation might be different than if the points tend to be randomly distributed in an area of greater magnitude than the radii of C and D. Also, what are rough relative sizes of C and D?

Share this post


Link to post
Share on other sites
Either this is a trick question or you need to come up with better requirements.

The answer is trivial. CC is simply CD and rC is the distance to the farthest point. This solution satisfies all your requirements: it is efficient, C includes all the points, CC can be no closer to CD and is in D.

Share this post


Link to post
Share on other sites
Tricky question, really. I don't think there are any simple ideal solution (the only one i can think of is voronoi-like partitioning of plane into areas by number of points included)

And seems that to make good non-ideal it's needed to know more about distribution of your points. Maybe simple average position will do the job, maybe not.

Quote:
Original post by JohnBolton
Either this is a trick question or you need to come up with better requirements.

The answer is trivial. CC is simply CD and rC is the distance to the farthest point. This solution satisfies all your requirements: it is efficient, C includes all the points, CC can be no closer to CD and is in D.

if i undestood him right,
rC is given and you can not set it.

Share this post


Link to post
Share on other sites
Maybe overlay a grid over the circle then at each grid point within the circle find the point with the lowest sum of the squared distances. Start with a relatively large grid then subdivide, i.e. check +/- half the grid spacing. It won't find you the global minimum, but might get you to a reasonable local minimum. Seems like an AI problem and often with AI you just want reasonable rather than absolute optimumal to simplify the problem.

Share this post


Link to post
Share on other sites
#define N 1000

I would try just testing N random locations of the center and picking the best found.

Adjust N to make the algorithm run within your constrains. If this doesn't give you good enough results, think harder...

Share this post


Link to post
Share on other sites
Sorry wasn't logged in..

The set below was a bit messed up :)

S = { Cc | Cc in D and Pn in C }, where Pn = {P0..PN}, N<=10 N>M
where M is some pre-chosen value.

The real solution is then simply the Cc in S thats closest to Cd

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!