Locations of the Intersections between the circles

I have plotted many circles under two sets;

N=viscircles(xya,repmat(1000,size(xya,1),1),'color','b'); hold on

W=viscircles(dya,repmat(1000,size(dya,1),1,'color','r')

I want to find the locations of the intersections between the circles in N with circles in W.

Answer 1

[Walter Roberson]

The output of viscircles is a hggroup object. It has two children, accessible with the Children property; each child is a Line object.

The first of the children by default has Linewidth 3, and the second of the children by default has Linewidth 2. The coordinates associated with the two children are the same: what is happening is that two lines are being created, one thinnner than the other and on top of the second thicker one. The fraction of the thicker one that shows up outside where the thinner one is drawn, is acting as the edge color. That is, instead of drawing an inner edge, a center, and an outer edge, it draws a thinner circle on top of a thicker circle knowing that the edges of the thicker circle will peek out.

You can extract the coordinates associated with the lines, so for example,

N.Children(1).XData  %and YData

You might have noticed that the situation does not describe having one (or two) circles for each circle that is drawn. Instead, the XData and YData describe all of the circles together, with NaN between the independent circles.

Now, you could extract the coordinates from the XData and break it up at the NaN and find the intersections.... but it is considerably easier to ignore the return values from viscircle() and instead go back to the coordinates you pass in, xya, dya, and the information about the radii. Then you have a more straight-forward "intersection of circles" situation

xya_radius = 1000; dya_radius = 1000;
dists = pdist2(xya, dya) - repmat(xya_radius,size(xya,1),1) - repmat(dya_radius,1, size(dya,1));

Now if dists(J,K) is negative then xya(J,:) intersects with dya(K,:). Take triu() or triu() to avoid processing the same pair twice, and proceed to calculate the intersection points (though be careful about cases the circles just touch.) https://math.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect

[Salem]

Thank you Walter, I think I will go with the second method. But how can the negative sign of dists(J,K) helps me to find the intersection locations?

[Walter Roberson]

Suppose that you have two circles, one of radius 3 and the other of radius 5. Suppose that their centers are 10 units apart

v   A   v  ^     B     ^
    0   3  5    10    15

Edges of A are marked with v and edges of B are marked with ^

distance 10 minus radius 3 for A minus radius 5 for B, gives 2, the distance between A and B

If B were to be moved 2 units closer to A, distance 8, then 8-3-5=0 and the circles touch

If B were to be moved 1 unit more closer to A, distance 7, then 7-3-5=-1 and the edge of A is within the edge of B

v   A  ^v   B     ^
    0  23   7    12

So in order to detect whether A and B intersect (not just touch) then distance - radiusA - radiusB < 0 tells you they do intersect (or, alternately, that A is completely inside B, which is possible in the case of different radius.)

It does not tell you the points of intersection: it tells you the pairs to pay attention to -- that instead of computing the points of intersection of each circle to each other circle and then weed through the list, instead determine quickly with distance which ones are intersecting and only bother to calculate the actual intersection points for those.

[Salem]

I got what you mean.Thank you so much. It is clear now. But I struggled constructing code to find the intersections locations using your link.

[Walter Roberson]

I refer to the link I posted earlier https://math.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect where several people show the exact formulas for finding the intersection points between two circles (assuming that they do intersect) . See for example https://math.stackexchange.com/q/1033561 by Salix Alba

[Salem]

I have tried that and it didnt work for me.

[Walter Roberson]

Did it give you the wrong output, or did you get an error message in your implementation ?

What code did you use?

[Salem]

Thank you for following up, I really appreciate it.

what I got is this message when I try to find the d values;

Arrays have incompatible sizes for this operation.

I guess it is because the number of circles in each set is not the same.

By the way Im new to MATLAB, I guess you can tell that. Im having a bad time with this issue.

[Walter Roberson]

Please post your code.

If you use

all_d = pdist2(xya, dya);
dists2 = all_d - repmat(xya_radius,size(xya,1),1) - repmat(dya_radius,1, size(dya,1));
mask = tril(dists2 <= 0);

ind = find(mask);
[idx_x, idx_d] = ind2sub(size(mask), ind);
d = all_d(ind);

then d(K) is the distances between the centres of xya(idx_x(K),:) and dya(idx_y(K),:) . It will reflect only the points where two circles at least touch.

[Salem]

d=sqrt((Nx1-Wx2)^2- (Ny1-Wy2)^2)

This is the code I used.

for the mask = tril(dists2 <= 0); it gives me all zeros while Im getting some negative values in dists2.

[Walter Roberson]

Remember to vectorize:

d = sqrt((Nx1-Wx2).^2- (Ny1-Wy2).^2)

I guess it is because the number of circles in each set is not the same.

Oh, but the number in the two sets is the same after you narrow down according to the idx_x, idx_d code that I showed earlier.

Please attach a .mat with xya and dya values, for testing purposes. Is the radius of the circles still 1000 in each case?

[Salem]

Again I really appreaciate your help.

Yes the radius in each case still same (1000). I have attached the two files.

[Walter Roberson]

load xya
load dya

xya_radius = 1000; dya_radius = 1000;

all_d = pdist2(xya, dya);
dists2 = all_d - repmat(xya_radius,size(xya,1),1) - repmat(dya_radius,1, size(dya,1));
mask = (dists2 <= 0);

ind = find(mask);
[idx_x, idx_d] = ind2sub(size(mask), ind);

d = all_d(ind);
sel_xya = xya(idx_x,:);
sel_dya = dya(idx_d,:);

Afterwards:

sel_xya and sel_dya are matrices containing information only about circles that intersect. The information is in corresponding pairs: sel_xya(K,:) intersects with sel_dya(K,:) so you can proceed by rows. d(K) is the distance between the centers sel_xya(K,:) and sel_dya(K,:)

[Salem]

Thank you so much, I really appreciate it.