How to select the most amount of scattered points contained in a radius?

Question

Setting up the Example

I've tried looking everywhere for a solution to problem before asking it here. My issue is that I am not very good with math or statistics in order to understand that any given algorithm would be helpful to the solution.

In my example, I have what looks like a scatter plot. There are just a bunch of points randomly placed on a Cartesian coordinate plane. I want to be able to draw a circle with a specific radius on this plane. The circle must contain the maximum amount of points possible.

What steps should I take to calculate the most optimal point to draw this circle?

I am looking for...

I would love a set of steps that I must take in order to figure out where on the graph I should start drawing (the center point of the circle). If you have code, I am pretty good at deciphering languages that I don't necessarily know, but I will be writing this in Lua (I do not have access to the C part unfortunately).

I really want to understand how the solution works, so I'd be grateful for any sources or explanations. Just for your information, performance is extremely important, but I am looking for any solution at this point.

Bonus :)

Since I am writing this, I thought I might as well ask about other advanced features that I would like my code to perform. But I can always figure these out later when I actually get my foot in the door.

• Points that are further from center of the circle are closer to full weight more, than points closer. The weight can simply be a linear function, where if the radius was 10, being 1 away from the center is only 10% of the full weight, and being 2 away from the center, is only 20% of the full weight. Being exactly 10 away from the center will give you 100% weight.

• Time is introduced and the center of the circle is also a dot on the graph (this dot is not part of the other dots and should not be calculated with them). The center of the circle moves at a constant speed, and you must choose a point close enough to the center because there is a decay over time on all the weights of all the dots. So the faster you draw the circle the better. (This is highly theoretical and I am unsure of what the decay would even be like).

Thank you so much for just reading this and considering my question! I can provide addition details or answer any question you might have.

Answer 1

There is a possibly faster way of finding the best circle that requires more mathematics, and extends to the first of your two exact points.

Take a grid that covers the area you are interested in and put 1 in this grid where you have drawn a point and 0 where you have not. You now need to work out a score for each point in the grid. You can do this by multiplying the value of each point in the grid by a weighting which depends on how far that point is from the point you are scoring, and then summing up the result. This covers your basic question (where the weight is 1 for points within the circle and 0 otherwise) and your first advanced point, where the weighting changes more gradually.

Looking at the problem in this way, you have a 2-dimensional filter which you need to apply to the grid. After you have applied it, you just need to find the highest scoring point in the result. Doing this the obvious way will be pretty slow, but it turns out that you can speed this sort of thing up using the Fast Fourier Transform, and you can get math libraries to compute this.

If you're not practiced at math or stats you're going to need a good explanation of this - better than I can produce, I'm afraid. It's done a lot, but I haven't found an explanation I really like. You could look at http://www.analog.com/static/imported-files/tech_docs/dsp_book_Ch24.pdf, which is also referenced in http://archive.gamedev.net/archive/reference/programming/features/imageproc/page2.html.

Answer 2

It would take a lot of computation/data, but you could check EVERY point to see if the points are in there. Not really mathematical, but it works... not very quickly either.

I don't know what engine you're using to test your code, but I am using LOVE2D. I highly recommend it, if not for game making for visualizing your solutions. You may use something else, this is just a personal preference. If you have a question on any of the LOVE functions, just visit the wiki on the love2d website.

function love.load() 
    points = { { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) }, { math.random( 0, love.graphics.getWidth() ), math.random( 0, love.graphics.getHeight() ) } }

    circles = {}
    for i = 0, love.graphics.getWidth() do
        for ii = 0, love.graphics.getHeight() do
            table.insert( circles, { hits = check_points( i, ii, 20, points ), x = i, y = ii } )
        end
    end
    circs = { { circles[1].hits, circles[1].x, circles[1].y } }
    largest = circs[1][1]

    for i = 1, #circles do
        if circles[i].hits >= largest then
            if circles[i].hits > largest then 
                circs = nil
                circs = {}
                table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
                largest = circs[1][1]
            elseif circles[i].hits == largest then
                local distance = math.sqrt( ( circles[i].x - circs[#circs][2] ) ^ 2 + ( circles[i].y - circs[#circs ][3] ) ^ 2 )
                if distance > 40 then
                    table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
                    largest = circs[1][1]
                end 
            end
        end
    end
end

function love.draw() 
    love.graphics.setColor( 255, 0, 0 )
    for i = 1, #circs do
        love.graphics.circle( 'fill', circs[i][2], circs[i][3], 20 )
    end
    love.graphics.setColor( 255, 255, 255 )
    for i = 1, #points do
        love.graphics.circle( 'fill', points[i][1], points[i][2], 1 )
    end
end

function check_points( x, y, r, ... )
    local hits = 0
    local p = ...
    for i = 1, #p do
        local distance = math.sqrt( ( x - p[i][1] ) ^ 2 + ( y - p[i][2] ) ^ 2 )
        if distance <= r then
            hits = hits + 1
        end
    end
    return hits
end

If anybody has a better, more time-friendly solution, I would like to know. I looked into some things, but nothing really worked.

Note that this one gets all the possible groupings, not circles. If you want to get all the circles, remove the

elseif circles[i].hits == largest then
    local distance = math.sqrt( ( circles[i].x - circs[#circs][2] ) ^ 2 + ( circles[i].y - circs[#circs ][3] ) ^ 2 )
    if distance > 40 then
        table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
        largest = circs[1][1]
    end 
end

and replace it with

else
    table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
    largest = circs[1][1]
end

If you wanted to get just the first or the last, you could take out the whole

if circles[i].hits >= largest then
    if circles[i].hits > largest then 
        circs = nil
        circs = {}
        table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
        largest = circs[1][1]
    elseif circles[i].hits == largest then
        local distance = math.sqrt( ( circles[i].x - circs[#circs][2] ) ^ 2 + ( circles[i].y - circs[#circs ][3] ) ^ 2 )
        if distance > 40 then
            table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
            largest = circs[1][1]
       end 
   end
end

and replace it with simply

if circles[i].hits >= largest then 
    circs = nil
    circs = {}
    table.insert( circs, { circles[i].hits, circles[i].x, circles[i].y } )
    largest = circs[1][1]
end

Greater than or equal to would get you the last one, greater that would get you the first one. There's much more you could build upon, such as making it choose the circle in the middle instead of the left, or something like that. But again, this is not really an algorithm and more of a 'sweep and check' sort of thing. It always gets the optimal solution, though...

You could also change the for-loop to iterate in .5 or .25 or something. The smaller you get, the more precise you'll get, but also the more time it will take.