0
$\begingroup$

Just wanted to know what is the best algorithm (in terms of speed and accuracy) to determine the intersection of N spheres (in 3D). With intersection I mean the following; in 2D and in the case of two overlapping circles of finite radius R1 and R2, they will have two points P1 and P2 in common in the case that distance between centers C1 and C2 is smaller than R1+R2, so that if we trace lines starting from one of the centers to this two points, we get an isosceles triangle. If we add a new circle at C3 with radius R3, so that d31 (distance between sphere 3 and 1) is smaller thant R1+R3 and d32 smaller than R2 and R3, we will have 2 new points of the same "kind", let's call them P3 and P4. Now if we assume that P1 lies somewhere inside the three circles, the other points P2, P3 and P4 lie "outside". Using C1, C2 and C3, and P2, P3, and P4 we could easily calculate the surrounding line from the intersection between the three spheres. These "outside" points P2, P3 and P4 I call them vertices.

Now let's say we have N spheres and we move in the 3D world, how to fastly calculate these vertices?

  • 0
    you understood perfectly the problem. the only thing is that the number of intersection points of each sphere with the others is not constant, can take any value2011-06-28

1 Answers 1

1

My interpretation of your question: For spheres $S_i \subset \mathbb{R}^3$, find all points (vertices) $v_j$ which lie on the intersection of at least three.

I'm ignoring this inside/outside nomenclature - perhaps it won't be too hard to split up your $v_j$ into inside/outside groups once you have them - feel free to clarify.

The problem (I'm guessing here) is that when the size of your set of spheres $\{S_i\}_{i\le N}$ is large, the number of triples of spheres $N \choose 3$ is really large.

Still, computationally, what can you do? One straightforward optimization would be to split things up into disjoint (or sufficiently disjoint) clusters of spheres, if our $S_i$ are sparse enough in $\mathbb{R}^3$. But we're left with the main piece of work: Iterate over pairs, find the circles of intersection for those who are close enough, see if anyone else lies close enough to hit, and if so we've got a new pair of points to add to our $v_i$.

There's no trickery - we're not trying to figure out if two circles intersect in $\mathbb{R}^3$ - when the centers of a sphere and a circle are close enough, we're guaranteed that intersection.

  • 0
    You gave the best answer2011-07-03