Intersection of multiple lines and circle

I have 30 points with x and y coordinates in a matrix which I plotted using scatter function.

I have 22 circles with x and y coordinates and their respective radius in another matrix which I plotted.

I plotted all possible paths between each point to all other points.

i want to point out the paths which intersect the circles and delete them.

How do I do that ?

Following is the code.

[location_set]=xlsread('data.xlsx','Locations','B2:C31'); %read locations from a file

stopsLon = location_set(:,1); % x coordinates of all locations

stopsLat=location_set(:,2); % y coordinates of all locations

nStops=30 %number of locations

idxs = nchoosek(1:nStops,2) %generate all trips / all pairs of stops

%create a graph where stops are nodes and trips are edges

G = graph(idxs(:,1),idxs(:,2));

figure

hGraph = plot(G,'XData',stopsLon,'YData',stopsLat,'LineStyle','r','NodeLabel',{})

axis equal

hold on

scatter(xdata,ydata, 'filled')

scatter(167.2313144,-112.331426,'g','filled')

hold off

storm_set = xlsread('data.xlsx','Storms','A3:C22');

x_circle=storm_set(:,1);

y_circle=storm_set(:,2);

radius_circle=storm_set(:,3);

centress = [x_circle y_circle];

axis equal

viscircles(centress,radius_circle)

title('Delivery Points and Circular Storms')

G = graph(idxs(:,1),idxs(:,2));

figure

hGraph = plot(G,'XData',stopsLon,'YData',stopsLat,'LineStyle','r','NodeLabel',{})

hold off

Answer 1

[Uday Pradhan]

Hi Tamim,

Since the number of location points and circles is low, we can design a brute – force algorithm for this problem. The code below is self – explanatory.

clear all; 
sLon = location_set(:,1); % x coordinates of all locations
sLat= location_set(:,2);
circles = storm_set; 
f = figure; 
hold on; 
 %scatter plots of cirlces and location  
scatter(circles(:,1),circles(:,2),circles(:,3),'filled','markerfacecolor','b');
%you can scale the third argument to see the circles plotted if they are small initially
scatter(sLon,sLat,'filled','markerfacecolor','k'); 
combs = nchoosek(1:30,2); %list of all combination between locations 
  
c = {}; 
for i = 1:435 % no of lines to be plotted (location points),size of combs
    %store the handles to each line plotted in a cell array 
    c{i} = plot([location_set(combs(i,1),1) location_set(combs(i,2),1)], ...
        [location_set(combs(i,1),2) location_set(combs(i,2),2)],'r-'); 
    %plot each line between every possible combination of location points
end 
hold off; 
for i = 1 : size(c,2) %for each line check if it intersects a circle
    if isvalid(c{i}) %since a line may intersect multiple circles, we may encounter handles to deleted lines.
        for j = 1:30 
            %determine if it intersects any one circle out of the 30 
            res = isIntersecting(c{i},circles(j,1),circles(j,2),circles(j,3));
            if res == true
                delete(c{i});  % if yes,delete the intersecting line and break out of this loop
                break;
            end
        end
    end
end
function result = isIntersecting(hObject,centreX,centreY,radius) 
        %used the distance between the line and the centre to determine if 
        %the circle and line intersect 
        a1 = hObject.XData; 
        a2 = hObject.YData; 
        x1 = a1(1,1); 
        y1 = a2(1,1); 
        x2 = a1(1,2); 
        y2 = a2(1,2); 
        a = y1 - y2; 
        b = x2 - x1; 
        c = y1 * (x2 - x1) + x1 * (y2 - y1); 
        dist = abs(a * centreX + b * centreY + c) / sqrt(a^2 + b^2); 
        if dist > radius 
            result = false; 
        else  
            result = true; 
        end 
end 

Hope this helps.