Determining that a sphere is completely covered by other spheres located around it

Question

Problem:. Based on the list of spheres, find all the empty spaces completely covered by the spheres.

Details: This is the problem I'm working on, in which I am trying to identify the cavities located in the protein. I am given a list of atoms that make up the coordinates of the protein ((x, y, z) and radius). Then I run my algorithm to find all the empty spaces that lie within the boundaries of the protein, checking whether it is possible to place the probe (of a given radius) in place without colliding with other areas. There are two types of empty spaces, voids, and cavities. Hollow spaces are spaces that can lead to or outside of the protein. Cavities are empty spaces that are completely covered by protein atoms. Here is an image of the protein sample we are working with.

It can be viewed in three dimensions here .

There is a cavity located near the center of the protein, the tunnel that you see through the protein will be considered a void space, because it is not completely closed by atoms.

Example:. Given a list of 26 atoms, these atoms are evenly distributed from (0,0,0) to (1,1,1) in a three-dimensional grid. Each atom has a radius of 0.25 and is placed either on 0, 0.5, or on any axis. At the point there is no atom (0.5, 0.5, 0.5). If we drew a three-dimensional figure of these atoms, it would be a cubic shape with a missing center. A cavity would be designated in (0,5,0,5,0,5) with a radius of 0.25. It can be assumed that this cavity is surrounded by proteins on all sides.

Image example:

Note that the above is only a two-dimensional representation of a cube and a protein. This is actually 3D.

How could one define void spaces against cavities for a much larger and irregularly shaped group of atoms?

I was thinking of implementing a recursive algorithm that checks every direction to see if it can reach the maximum and minimum boundaries of the chart, but I'm not sure if this is the right way to do this.

Additionally: Is there another algorithm that says that the cavity in the example is actually a void space, because there are very small “paths” for reaching the protein outside? The cavity must be completely closed by atoms for existence. Any void spaces that have a path (in any direction, not necessarily straight) to the outside of the protein will not be considered cavities.

Answer 1

Cool question. Here is the algorithm that should do the trick:

Designations:

• Let us call our moving sphere S
• Write diam(X) for the diameter of the sphere X
• Write dist(X,Y) for the distance from X to Y ; this is the same as the distance from center X to center Y minus the sum of the radii.

Algorithm:

• For any two non-retractable spheres A and B check if S pass directly between the centers of A and B (i.e. diam(S) <= dist(A,B) ?).
• If so, then for each other sphere C check if S can touch all three spheres A , B and C at the same time if there were no other spheres. If S can touch all 3 at the same time, draw a triangle between the centers of A , B and C
  • This can be verified in several ways. One fairly simple way: the possible positions of the center S when touching both A and B form a circle. You want to know if this circle on it has less than diam(S) + diam(C) far from the center of C This is simple geometry.
• Now the problem boils down to the question: have the triangles divided the initial position of the center S from infinity? You can answer one connected component at a time. In fact, you can even answer this “edge-connected” component at a time when the component is connected at the edges, if any two non-vertex points can be connected by a path that does not go through any vertices. You can calculate these components with a simple graph search.
• For a given component associated with edges, you need to decide whether the component separates the center of S from infinity. There are several ways to do this:
  • Calculate the 2% "nofollow"> component homology, select efficient generators, and for each ask whether your point and infinity are on the same side of the loop or not, which can be checked using the orientation class.
  • Or just start drawing the component:
    • Start with a triangle that you can reach from S , and draw all the faces that can be reached from there. It's a little subtle, but the algorithm simply "runs anywhere, queues edges, intersects each edge on the face, forming the smallest angle with that edge, and stops when there are no edges on the left." Keep in mind that the opposite side of the same triangle can be the person forming the smallest angle.
    • Do the same from infinity. Have you crossed any colored triangles? If so, your realm can escape. If not, this is not possible.

Why does it work

Step 3 is true because if you do not press a single sphere C while “rolling” along the edge between A and B , you can reach either side of this edge. In other words, any position that stops you from going to infinity should include S touching at least three spheres.

Please note that there are some subtleties arising from "exceptional" situations, for example, when S touches four spheres at once. You can avoid these subtleties by re-triangulating your form before performing steps 3 and 4.