Finding points within overlapping spheres

Question

I have the coordinates for the centers and the radii of multiple spherical surfaces (hollow). These spheres may be of different radii, and some will overlap. Whenever they overlap, I want to eliminate the points along the surface of any sphere that is within another sphere or overlapped, so that I only get the "outside" view, so to speak.

How would I go about finding/eliminating these points of overlap? Is there an existing algorithm for finding these points?

Thanks in advance, and let me know if I can clarify the question better!

Edit 1:

The input will be a LAMMPS output file. The important section is below. The first column is the atom id, in order for atoms to be distinguishable. The next 3 are x,y,z coordinates. Radius is given by user input.

ATOMS_id     x       y       z  
________    ____    ____    ____

 1             0       0       0
 2          1.76    1.76       0
 3          1.76       0    1.76
 4             0    1.76    1.76
 5          3.52       0       0
 6          3.52    1.76    1.76
 7             0    3.52       0
 8          1.76    3.52    1.76
 9          3.52    3.52       0
10             0       0    3.52
11          1.76    1.76    3.52
12          3.52       0    3.52
13             0    3.52    3.52
14          3.52    3.52    3.52

Using the above points and a radius of 1.6, this is the output of my current code (that only generates images).

The main problem is that my code (which uses the sphere(n) and surf() functions) draws all parts of the sphere, regardless of whether the points overlap. I want to essentially only get the coordinates that make up the outer surface of the above image, without the interior parts.

The easier case would be for just two spheres, as above.

Answer 1

I've managed to come up with some proof-of-concept algorithm for the 2-sphere case based on these two sources: src1, src2.

%% // Init
clear variables; close all force; clc;
%% // Generate spheres
[X,Y,Z] = sphere(40);
P{1} = unique([X(:),Y(:),Z(:)],'rows');
P{2} = bsxfun(@plus,P{1},[0.75,0,0]);
%% // Generate triangulations
DT{1} = delaunayTriangulation(P{1});
DT{2} = delaunayTriangulation(P{2});
%% // Find points within the other triangulation
isIn1 = ~isnan(tsearchn(P{1}, DT{1}.ConnectivityList, P{2})); 
isIn2 = ~isnan(tsearchn(P{2}, DT{2}.ConnectivityList, P{1})); 
%% // Plotting
newP = [P{1}(~isIn2,:);P{2}(~isIn1,:)];
%// Before:
figure();
surf(X,Y,Z); hold on; surf(X+0.75,Y,Z);
xlabel('x'); ylabel('y'); zlabel('z');
ylim([0,1]);
%// After:
figure();
scatter3(newP(:,1),newP(:,2),newP(:,3));
ylim([0,1]);

These are the results:

• Before:

• After:

There are still a few errant points inside the joint volume, but I would argue that the situation is much better than at the beginning.

Note: This FEX submission may be of use to you.

Answer 2

You can just find points with distance inferior to radius relatively to eah sphere center and after mesh triangularisation eliminate triangle with points inside another sphere.