确定 N 个球体之间的交点
Just wanted to know what is the best approach (in terms of speed and accuracy) to determine the points of intersection on N spheres (it was asked for two spheres here); wanted to know what would be the best language to do this. More detailed explanation about what I want to do is here.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
据我所知，您正在询问每对 N 3D 球体的相交轨迹。
算对称性，有 N * (N-1) / 2 对。
所以拿每一对。
如果中心之间的距离大于它们的半径之和，则不存在交点。
（编辑：或者，正如@Ben指出的那样，如果距离小于半径差，则也没有交点。）
如果相等，则交点是单个点，很容易在中心之间的线段上找到。
如果小于，则轨迹是圆，而不是点。
要找到该圆的中心及其半径，您需要对两个球体进行平面切片。
这将问题简化为寻找两个圆的交点。
为此，您需要余弦定律。
详细说明：看看维基百科的图表。 a 和 b 是两个球体的半径，c 是中心之间的距离。
使用倒数第二个方程并求解 cos(alpha)。
由此你可以轻松得到sin(alpha)。
那么b sin(alpha)就是圆的半径，
b cos(alpha) 是到其中心的距离。
（注意 - 这不会调用任何三角函数，只调用 sqrt。）
一旦知道交点圆的中心和半径，圆本身就位于与连接线段垂直的平面中球体中心。
除此之外，我不太确定你想要什么。
As near as I can tell, you are asking for the intersection loci of each pair of N 3D spheres.
Counting symmetry, there are N * (N-1) / 2 pairs.
So take each pair.
If the distance between centers is greater than the sum of their radii, there is no intersection.
(Edit: Or, as @Ben points out, if the distance is less than the difference of radii, there is also no intersection.)
If it is equal, the intersection is a single point, easily found on the line segment between centers.
If it is less, the locus is a circle, not a point.
To find the center of that circle and its radius, you're going to need to take a plane slice through the two spheres.
That reduces the problem to finding the intersection of two circles.
For that you need the Law of Cosines.
Elaborated: Look at that Wikipedia diagram. a and b are the radii of the two spheres, and c is the distance between centers.
Use the second-to-last equation and solve for cos(alpha).
From that you can easily get sin(alpha).
Then b sin(alpha) is the radius of the circle,
and b cos(alpha) is the distance to its center.
(Note - this doesn't call any trig functions, only sqrt.)
Once you know the center and radius of the circle of intersection, the circle itself is just in a plane normal to the line segment connecting the sphere centers.
Beyond that, I'm not really sure what you want.
如果我没理解错的话，你想要一组 N 个球体中至少两个球体的所有交集，对吧？
如果是这样，这对于高性能计算来说实际上不是一个容易的问题，至少在您需要准确的解决方案时不是这样。
在计算分子的“缩减表面积”时，这个问题也得到了解决：
http://www. ncbi.nlm.nih.gov/pubmed/8906967
有几篇出版物介绍了如何有效计算这些点和圆，但这并不是一件容易的事。
我相信有一本出版物用 CUDA 计算这些值，但我不记得细节了。谷歌（学术）应该能够在这个方向上帮助你。
但是，根据您想要实现的目标，可以有更简单的解决方案。
那么，也许你可以详细说明你的问题？
If i get you right, you want all intersections of at least two spheres from a group of N spheres, right?
If so, this is acually not an easy problem for high performance computing, at least not if you need an accurate solution.
This problem is also solved when calculating the "Reduced Surface" of molecules:
http://www.ncbi.nlm.nih.gov/pubmed/8906967
There are several publications on how to efficiently calculate these points and circles, but it is not an easy task.
I believe there was a publication to calculating these values with CUDA, but I don't remember the details. Google (Scholar) should be able to help you in this direction.
However, depending on what you want to achieve, there can be easier solutions.
So, perhaps you could detail your question?