How to find point closest to multiple circles?
12 views (last 30 days)
Show older comments
Hi!
I want to solve the following problem using Matlab:
In the xy-plane, I have multiple circles, defined by their midpoint and their radius. Some of the circles overlap, others dont.
Now, I want to find a point A in the xy-plane that is closest to all circles.
So in other words: I want to find the point A for which the sum of distances to a point (it does not matter which) on each of the circles is minimal.
Does anyone know how to do this?
Edit:
To clarify my question: the circles can also be completely inside another circle. I added two images of two example situations. In both situations, I want to find point A.
Thanks!
Bas
4 Comments
Image Analyst
on 31 Jan 2019
I have the same question as Jan. And your latest comment did not answer his or my questions.
What does distance of your point to a circle mean?
- Distance to the center?
- Or the perimeter points?
If it's the center, maybe just averaging the centers will be where you want it. If it's to the perimeter points, then be aware that the radii will affect the answer since there will be more perimeter points on a larger circle, so their distances will give a greater sum than for a small circle.
Accepted Answer
Matt J
on 31 Jan 2019
Edited: Matt J
on 31 Jan 2019
Let C be a 1x2xN matrix of the circle centers and R an 1x1xN vector of their radii. It is a low-dimensional, non-smooth minimization problem so, I would use fminsearch:
rownorm=@(z) sqrt( sum(z.^2,2) );
fun=@(A) sum( rownorm( (A-C) - (A-C).*R./rownorm(A-C)) , 3 ); %edited
A = fminsearch(fun,A0(:).');
Luckily, it is only a 2D problem, so you can come up with a decent initial guess A0 using a brute force grid search, e.g.,
[X,Y]=ndgrid(linspace(-1,1,100)); %adjust grid limits depending on C and R
Agrid=[X(:),Y(:)];
[~,gridmin]=min( fun(Agrid) );
A0=Agrid(gridmin,:);
10 Comments
Matt J
on 31 Jan 2019
You're welcome. Please Accept-click the answer, though, to certify that it addresses the problem.
fun is the thing you are trying to minimize. It computes the sum of the distances from A to your circles.
More Answers (2)
Jim Riggs
on 31 Jan 2019
Personally, I would use a numerical searcing algorithm.
Overlay a grid on the problem space, then compute the distance function (sum of distance to all circles) from each grid point.
Select the minimum value, then refine the grid and search from the minimum point.
Continue until the desired numerical precision is schieved.
Distance function is the sum of distance from Point P, to each circle. If P is outside the circle, then the distance to that circle is the distance from P to the circle center, minus the circle radius, but if P is inside the circle (Distance from P to the center is less than the radius) then the distance to the circle is the radius minus the distance from P to the center.
2 Comments
Jan
on 31 Jan 2019
The grid search will fail for a set of concentric circles, because you will get a circle as solution, not a single point.
Jan
on 31 Jan 2019
Edited: Jan
on 31 Jan 2019
A simple grid search with loops - just for demonstration:
% Define circles:
nCircle = 10;
Center = rand(nCircle, 2);
Radius = rand(nCircle, 1) / 5;
% To show that result is not unique:
% nCircle = 3;
% Center = repmat(0.5, nCircle, 2);
% Radius = [0.5, 1, 1.5];
% Get distances on a 50x50 grid:
nGrid = 50;
gridv = linspace(0, 1, nGrid);
Dist = zeros(nGrid, nGrid);
axes('NextPlot', 'add');
view(3)
for ix = 1:nGrid
x = gridv(ix);
for iy = 1:nGrid
y = gridv(iy);
D = 0;
for iC = 1:nCircle
D = D + abs(sqrt((x - C(iC, 1))^2 + (y - C(iC, 2))^2) - R(iC));
end
Dist(ix, iy) = D;
end
end
% Draw sum of distances:
surf(gridv, gridv, Dist.' - min(Dist(:)), 'FaceAlpha', 0.5);
% Draw the circles
v = linspace(0, 2*pi, 50);
for iC = 1:nCircle
line(C(iC, 1) + sin(v) * R(iC), C(iC, 2) + cos(v) * R(iC));
end
Grafics for 3 concentric circles:
See Also
Categories
Find more on 2-D and 3-D Plots in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!