I'm in need of an algorithm to find the best spot for a circle with a fixed radius r to cover as many points as possible on a 2D grid, preferably O(n).

Currently I tried 2 different approaches:

  1. The averaging Method
  2. The 'Heat-Map' Method

On the averaging Method I calc the center of all points and then I check how many points are in range (r) of that center, if the number is as high as the given points it returns the spot, else the furthest point is removed from the list and the steps repeat.

+: Very fast -: Often inaccurate

On the Heat-Map method I generate possible circle center points around all points. If a point is already created I increase it's count by 1. The point with the highest count and lowest total distance to the points in range (r) is the center.

+: Perfect center (depending on scale) -: Slow (depending on scale)

About scale: map is huge 10000x10000, a circle with radius 400 would contain thousands of possible centers, so I scale all points to the same system with roundings. The higher the scale, the less points and faster algorithm but more inaccurate center. But still more accurate than 1. Method.

Do you guys know any other algorithms/ways/Tipps/Performance Boosters?

Edit: maybe minimum enclosing circle + removing furthest Point Till MEC.radius <= Radius...

Edit2: or connect all points with lines and check for most intersections, just came to my mind

Edit: Here's an image with Algorithm #2 enter image description here

Another Image of Algorithm #2 enter image description here

  • \$\begingroup\$ Do you need it to be the best? It's not really possible to do it in less than O(N²) in that case I think \$\endgroup\$
    – Bálint
    Apr 10 '19 at 10:25
  • \$\begingroup\$ Sadly I'm a perfectionist 😥 but there are only like 5 - 15 points at Max to check, so n² works too I think \$\endgroup\$
    – LuaNoob
    Apr 10 '19 at 10:27
  • \$\begingroup\$ Are these points dense (ie. every intersection of grid lines has a point we want to cover) or can they be sparse, with some grid intersections empty? Can you show us a diagram of a typical distribution and your desired circle output for that case? \$\endgroup\$
    – DMGregory
    Apr 10 '19 at 11:09
  • \$\begingroup\$ Sure, I draw something when I'm back home. \$\endgroup\$
    – LuaNoob
    Apr 10 '19 at 11:12
  • \$\begingroup\$ This also looks like a theoretical computer science question that can be answered without game-specific expertise, so you may find more relevant knowledge on the dedicated StackExchange for that topic instead. \$\endgroup\$
    – DMGregory
    Apr 10 '19 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.