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
    Why do you need this for? Points of intersection between two spheres can be infinitely in number: intersection of two sphere is void, one point or one circle. The algorithm is just computational. There is no faster way, if the number of points is infinite.2011-06-24
  • 0
    ok, I rephrased the question, hope it gets more clear now2011-06-24
  • 0
    I didn't understand even the 2D version. With 3 circles there are six points of intersection, not four. I'm getting a feeling that in the 2D-case you want as the output the closed path $L$ consisting of line segments, where the centers $C_i$ and points of intersection $P_i$ alternate as end points, and you want $L$ to somehow be the `outer perimeter' in that all the other such line segments are inside the region with boundary formed by $L$. Is this correct? But still, Beni's point stands. In 3D there are no triangles, but cones. And cones don't have vertices, so I don't understand???2011-06-26
  • 0
    Had another idea/question: do you want the vertices to be points of intersection of **three** spheres in 3D, and the build a kind of polyhedron (consisting of tetrahedra as opposed to cones) out of those? Again keeping in mind that you only need the exterior faces of this polyhedral region of the 3D-space?2011-06-27
  • 0
    Hi Jyrki, yes, that is the idea, but there are not three only spheres, but thousands of2011-06-28
  • 0
    @Werner: I thought so, but would each vertex be a point of intersection for 3 spheres? In general more than 3 spheres would not have points of intersection. So altogether there would be $N$ spheres, and we form vertices with points of intersection 3 at a time? I guess what I'm saying is that the problem is not quite well defined to me. May be this is a somewhat known problem in e.g. 3D graphics programming? At best I could come up with some ad hoc algorithm (if that?). More knowledgeable people may hunt your bounty, but need a sharper problem description.2011-06-28
  • 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