我喜欢为二阶有限元网格创建插值函数。对于有直边的元素，一切都很好，但我的一些元素可能有弯曲的边缘，如图所示：
如果查询点位于弯曲元素内，我正在寻找有关如何有效且稳健地进行测试的参考资料。插值本身不是问题。一种通用的方法是在，坐标中找到全局元素到其在，坐标中的母元素的映射，然后映射查询点并查看映射的查询点是否在母元素内有直边。这似乎很过分，我想知道您是否可以指出其他选择。
更新： 这是用于一般插值，用于绘制函数等。查询点可以是“随机的”。即使有一个非常好的算法来找到离查询点最近的元素，也需要检查它是否在元素中。如果不是这种情况，则需要找到并测试一个新的潜在元素。这意味着每个查询点至少需要完成一个查询。如果可以使用元素是否弯曲的信息，则可以减少昂贵的测试。如果元件不弯曲，则可以使用廉价的线性测试。
我认为一般情况下你不能比映射到参考元素并在那里测试做得更好。如果您的映射有点特殊，您可能能够开发出一种比通常方法更有效的测试，但我在实践中还没有见过。
我要问你的一个问题是，你在做什么需要大量检查一个点在哪个元素中？
如果您的元素是二次的，您可以在函数中找到三角形的三个二次边的隐式方程，形式为,,（下面有更多关于如何做到这一点的参考资料）。三大功能,和测量到弯曲边缘的（定向）距离，二次三角形内的点的特征是和和.
如何从 Bézier 控制网格中找到隐式形式在 [1] 的第 4.4 节中进行了说明（它在计算机图形学中用于在图形处理器上显示二次曲线）。现在，如果您有大量二次三角形（网格）并且想要找出哪个包含特定点，则同一篇论文提出了一种空间分解数据结构，可以显着加快处理速度（第 5 节）。
还有另一个关于“隐式”过程的参考资料 [2]。
请注意，如果您有许多点查询要做，这种技术很有趣（否则预处理阶段/转换可能会令人望而却步）
[1] http://research.microsoft.com/en-us/um/people/hoppe/proj/ravg/
[2] GOLDMAN R.、SEDERBERG T. 和 ANDERSON D. 1984 年。矢量消除：平面参数有理多项式曲线的隐式化、反演和相交技术。CAGD 1, 327-356。
您可以调整一种传统的 Point-in-Polygon 算法来满足您的需求。特别是，您可以概括“光线投射”方法。这个想法是这样的：从你的点向任何方向投射光线。计算光线与元素边界相交的次数（注意，对于弯曲的边缘，每边可能 > 1）。如果交叉点的数量为奇数，则该点在元素内部。如果交叉点的数量是偶数（或零），则该点在元素之外。
计数对极端情况有点敏感（字面意思是角：你必须小心不要重复计算元素角处的交叉点），但只要你注意这一点，编写一个合理有效的实现并不难这个的。对于您所描绘的二次元素，您将求解直线和抛物线之间的交点，这很容易做到（求解二次方程）。一旦有了方程的 0 或 2 个解，您就可以检查相交是否出现在包含元素边缘的抛物线段上。
我以前从未对弯曲元素做过此操作，但我看不出该方法不起作用的任何原因。原则上，将其推广到 3D 应该可行，但计算交叉点可能会更加困难。
这是我遇到此问题时用作参考的维基百科页面的链接。 https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm