3

我在 3 个空间中有两个环，每个环由法线向量、中心坐标和半径表示。如何确定环是否已链接。即一个圆上的一个点位于另一个圆盘上。

这将在一个紧密的循环中实现，所以我关心性能。我觉得应该有一个封闭形式的解决方案。到目前为止，我只想到了迭代解决方案。

有什么帮助吗？

4

4 回答 4

3

算法概要：

  1. 处理圆的平面平行或并发的情况。
  2. 找到圆的平面的交线。
  3. 找到圆与这条线的交点。
  4. 所有与线的圆交点都在两个平面上。我们现在可以进行距离检查以查看圆圈是否相连。

细节：

我假设圆 C1 和 C2 由中心点 (p1, p2)、单位法线轴矢量 (n1, n2) 和半径 (r1, r2) 给出。

如果对于某个标量 k，n1 == k n2，则平面是平行的或并发的。如果它们是并发的，这将成为一个微不足道的二维问题：检查 dist(p1, p2) < r1+r2 是否。

否则，平面相交于直线 L。如果两个圆是相连的，那么它们都必须与 L 相交，因为连接意味着它们相互穿过彼此的定义平面。这为您提供了第一个微不足道的拒绝测试。

L 由点 q 和向量 v 给出。找到 v 很容易：它只是 n1 和 n2 的叉积。q 有点棘手，但我们可以选择最接近线的点

l1(s) = p1 + s (v X n1)
l2(t) = p2 + t (v X n2)

这些线垂直于 v、n1 和 n2，并且位于 C1 和 C2 的平面上。它们的最近接近点必须在 L 上。

您可以参考这篇文章来了解如何找到最近的方法点。

最后，圆相交的唯一方法是它们在 L 上都有点。如果有，则考虑 C1 和 L 的交点，因为它们与 C2 相关。如果 C1 和 L 有两个交点 q11 和 q12 并且其中一个恰好在 C2 内部，则这些圆是相连的。由于 L 在 C2 的平面上，因此这成为平面圆点测试：

IF dist(p1, q11) < r1 THEN
    linked = (dist(p1, q12) > r1)
ELSE
    linked = (dist(p1, q11) < r1)
ENDIF

当然，这个伪代码在处理圆实际相交的情况时有点草率，但是应该如何处理取决于您的应用程序。

于 2012-08-22T19:33:22.530 回答
1

一个相对容易编码的直接解决方案：计算两个平面的交线，然后旋转和平移所有东西（在我的例子中，定义两个圆的六个点），使线成为 Z 轴（x=y= 0)。然后可以分别围绕 Z 旋转平面，使第一个圆 C1 位于 XZ 平面上，C2 位于 YZ 平面上。现在中心和半径很容易找到（在我的情况下，我最初没有它们）。这些旋转不会更改链接/无链接属性，并且可以根据圆与 Z 轴的四个交点的顺序轻松确定链接或缺少链接。（如果任何一个圆圈不与 x=y=0 相交，则没有链接。）（我可能混淆了轴，但我认为这会起作用。）谢谢。

于 2014-04-26T06:02:12.910 回答
1

这是 3D 圆盘交叉问题吗？或者，是圆-圆相交问题吗？

如果是前者，则有一种快速的封闭形式算法。首先，排除圆圈太远的情况： dist(CIR1.c, CIR2.c) > CIR1.r + CIR2.r

处理边缘情况：共面圆。

将圆盘拉伸到其平面中，然后将圆与该平面相交。如果有 1 或 2 个交叉点，则测试它们是否符合pointInDisk(p, CIR)逻辑。报告任何幸存的交叉点。

于 2017-04-09T03:14:26.823 回答
0

计算几何教科书可能有一个很好的解决方案！

但我目前手头没有计算几何教科书。如果我现在要推出自己的产品，基于我自己（非常有限）的直觉，我想我会从 3d 轴对齐的边界框开始。

例如，创建一个“就在圆内”边界框，以及一个“就在圆外”边界框。我相信弄清楚两个轴对齐的框是否重叠是微不足道的（我曾经做过的家庭作业的第 2.1 节讨论了 2D 情况下的一个相关问题 --- 找到一个点最近的矩形： http://juliusdavies. ca/uvic/report.html）。

我怀疑以下断言会成立（但我可能是错的）：

  • 如果内盒重叠，则环肯定是连接的。（我现在认为这是错误的......）

  • 如果外盒不重叠，那么它们肯定没有连接——我非常有信心这个断言成立！:-) :-)

  • 如果外盒重叠，但内盒不重叠，则它们可能是连接的。

这就是我要开始的地方，如果我自己滚动的话。

结论：呃，我希望你对其他答案有更好的运气。:-)

于 2012-08-22T19:49:04.277 回答