我有一个简单的方形网格，里面有一条曲线（由另一个网格离散）。在这里，一张图片胜过千言万语。我想要实现的是找到，对于圆形（离散）网格的每个单元格，我想获得与其他网格的单元格 T 的交点。在这里，它们用红点标记。
要遵循的正确算法是什么？当然，如果圆形网格的两个连续支撑点在不同的单元格中，那么我可以计算交集，但一般情况下，可能是单元格被切割，而另一个网格的支撑点在那里没有，再看上图。
我从 FEnics 开始，但我认为在这种情况下 deal.II 是要走的路。所以，deal.II“行话”中的任何解释都非常受欢迎。
其他答案和评论已经有很好的建议。在实践中，您可能会发现在粗网格上，大多数单元格与曲线没有交集，并且假设您的曲线包含在域的相对较小部分中，您可以轻松排除单元格与曲线相交的情况使用边界框。为此，您将曲线拆分为中等数量的边界框，每个边界框都覆盖一条线段，或者覆盖一条线段的整体，或者一条线段的一小段，然后将它们与单元格的边界框相交。如果交叉点为空，则您知道曲线不会通过单元格。
将大量单元格边界框与大量线段边界框进行比较是昂贵的。如果您使用边界框的 rtree，则可以提高效率。deal.II 具有边界框和 rtree 的类。
当我在过去遇到这个问题时，在跨不匹配曲面细分的域分解的背景下，我最终基本上使用 Sutherland-Hodgman 算法（多边形到多边形裁剪）将每个多边形相互裁剪，并结合了广泛的-基于界面元素上的 BVH/BSH 的相位剔除。它绝对可以应用于这个问题，但如果你只想要交叉点（并且不关心这些点的拓扑/多边形化），它可能会有点过分。一个棘手的问题是生成的裁剪区域基本上可以是任意多边形，因此您可能会发现您需要进一步的算法机制（即三角剖分/网格划分）才能对结果执行任何类似 FE 的事情（例如插值/重采样/基础）。