How to find point closest to multiple circles?
11 次查看(过去 30 天)
显示 更早的评论
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 个评论
Image Analyst
2019-1-31
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.
采纳的回答
Matt J
2019-1-31
编辑:Matt J
2019-1-31
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 个评论
Matt J
2019-1-31
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.
更多回答(2 个)
Jim Riggs
2019-1-31
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 个评论
Jan
2019-1-31
The grid search will fail for a set of concentric circles, because you will get a circle as solution, not a single point.
Jan
2019-1-31
编辑:Jan
2019-1-31
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:
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!