二维插值算法
我有两个形状，它们是通道的横截面。我想计算两个定义点之间的中间点的横截面。 在这种情况下使用的最简单（相对简单？）的算法是什么？
PS：我遇到过一些算法，比如自然邻域和泊松，看起来很复杂。我正在寻找一个简单的解决方案，可以快速实施。
编辑：我从标题中删除了“最简单”一词，因为它可能会产生误导
I have two shapes which are cross sections of a channel. I want to calculate the cross section of an intermediate point between the two defined points.
What's the simplest (relatively simple?) algorithm to use in this situation?
P.S.: I came across several algorithms like natural neighbor and poisson, which seemed complex. I'm looking for a simple solution, which could be implemented quickly.
EDIT: I removed the word "Simplest" from the title since it might be misleading
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这很简单：
更简单：
我想第二个建议可能太简单了，但我敢打赌没有人提出更简单的建议！
编辑以下OP的评论：（太多的重新评论）
好吧，你确实要求一个简单的方法！我不确定第一种方法是否存在与您相同的问题。如果横截面不是太奇怪（如果它们是凸多边形，则可能是最好的）并且您没有做任何奇怪的事情，例如将一个横截面的左侧映射到另一个横截面的右侧（从而迫使大量交叉线）那么该方法应该产生某种合理的横截面。在您建议使用三角形和矩形的情况下，假设三角形位于其底部，一个顶点位于顶部。将该点映射到矩形的左上角，然后沿着连接相应点的两个横截面的边界沿相同方向（顺时针或逆时针）前进。我没有看到任何交叉线，并且在两个横截面之间的任何距离处都看到了明确的形状。
This is simple:
Simpler still:
This second suggestion might be too simple I suppose, but I bet no-one suggests a simpler one !
EDIT following OP's comment: (too much for a re-comment)
Well, you did ask for a simple method ! I'm not sure I see the same problem with the first method as you do. If the cross sections are not too weird (probably best if they are convex polygons) and you don't do anything strange such as map the left side of one cross-section to the right side of the other (thereby forcing lots of crossing lines) then the method should produce some kind of sensible cross section. In the case you suggest of a triangle and a rectangle, suppose the triangle is sitting on its base, one vertex at the top. Map that point to, say, the top left corner of the rectangle, then proceed in the same direction (clockwise or anti-clockwise) around the boundaries of both cross-sections joining corresponding points. I don't see any crossing lines, and I see a well-defined shape at any distance between the two cross-sections.
请注意，高性能马克的答案存在一些含糊之处，您可能需要解决这些问题，并将定义他的方法的输出质量。最重要的是，当你在两个横截面上画
n个点时，你确定它们之间是什么样的对应关系，也就是说，如果你按照High Performance Mark建议的方式这样做，那么标记点的顺序变得很重要。我建议同时旋转（正交）平面穿过两个横截面，然后在一个横截面上与该平面相交的一组点只需与在另一个横截面上与该平面相交的一组点相匹配。假设，这些集合中的点的数量没有限制，但它确实降低了原始情况下对应问题的复杂性。
Note there are some ambiguities about High Performance Mark's answers you will probably need to address and will define the quality of the output of his method. The most important one is, when you draw the
npoints on both cross-sections, what sort of correspondence do you determine between them, that is if you do it that way High Performance Mark suggested, then the order of labeling the points becomes important.I suggest rotating (orthogonal) plane simultaneously through both cross sections, then the set of points which intersect that plane on one cross section just need to be matched to the set of points that intersect that plane on the other cross section. Hypothetically, there is no limit on the number of points in these sets, but it certainly reduces the complexity of the correspondence problem in the original situation.
这是解决这个问题的另一种尝试，我认为这是一个更好的尝试。
给定两个横截面
C_1、C_2将每个
C_i放入坐标系(x,y)< 的全局参考系中/code> 这样它们的相对位置就有意义了。将每个C_i分成上下曲线U_i和L_i。这个想法是，您需要将曲线U_1连续变形为U_2，将L_1变形为L_2。 （请注意，如果您愿意，您可以扩展此方法以将每个C_i分割为m曲线。）执行此操作的方法如下。对于每个
T_i = U_i或L_i采样n点，并确定插值多项式P{T_i}(x)。正如下面有人适当指出的那样，插值多项式很容易受到振荡的影响，尤其是在端点处。可以使用更稳健的最小二乘拟合多项式来代替插值多项式。然后将多项式P{U_1}(x) = a_0 + a_1 * x + ... + a_n * x^n变形为P{U_2}(x) = b_0 + b_1 * x + ... + b_n * x^nasQ{P{U_1},P{U_2}}(x, t) = ( t * a_0 + (1 - t ) b_0 ) + ... + (t * a_n + (1-t) * b_n ) * x^n其中变形Q是在0<=t<; 上定义的。 =1其中t定义变形所在的点（即在t=0处，我们位于U_2处，并且位于 < code>t=1 我们位于U_1处，并且在每隔一个t处我们处于两者的某种连续变形。）Q{P{L_1},P{L_2}}(x, t)的情况完全相同。这两种变形在两个横截面之间构造了一个连续的表示，您可以在任何t处进行采样。请注意，这一切实际上是对两个横截面的插值多项式的系数进行线性插值。另请注意，在分割横截面时，您可能应该施加约束，即它们必须在匹配的端点处分割，否则变形中可能会出现“孔”。
我希望这是清楚的。
编辑：解决了插值多项式中的振荡问题。
Here is another try at the problem, which I think is a much better attempt.
Given the two cross-sections
C_1,C_2Place each
C_iinto a global reference frame with coordinate system(x,y)so that the way they are relatively situated makes sense. Split eachC_iinto an upper and lower curveU_iandL_i. The idea is going to be that you will want to continuously deform curveU_1toU_2andL_1toL_2. (Note you can extend this method to split eachC_iintomcurves if you wish.)The way to do this is as follows. For each
T_i = U_i, or L_isamplenpoints, and determine the interpolating polynomialP{T_i}(x). As some one duly noted below, interpolating polynomials are susceptible to oscillation especially at the endpoints. Instead of the interpolating polynomial, one may instead use the least squares fit polynomial which would be much more robust. Then define the deformation of the polynomialP{U_1}(x) = a_0 + a_1 * x + ... + a_n * x^ntoP{U_2}(x) = b_0 + b_1 * x + ... + b_n * x^nasQ{P{U_1},P{U_2}}(x, t) = ( t * a_0 + (1 - t ) b_0 ) + ... + (t * a_n + (1-t) * b_n ) * x^nwhere the deformationQis defined over0<=t<=1wheretdefines at which point the deformation is at (i.e. att=0we are atU_2and att=1we are atU_1and at every othertwe are at some continuous deformation of the two.)The exact same follows for
Q{P{L_1},P{L_2}}(x, t). These two deformations construct you a continuous representation between the two cross-sections which you can sample at anyt.Note all this is really doing is linearly interpolation the coefficients of the interpolation polynomials of the two pieces of both cross-sections. Note also when spliting the cross-sections you should probably put the constraint that they must be split at end points that match up otherwise you may have "holes" in your deformation.
I hope thats clear.
edit: addressed the issue of oscillation in interpolating polynomials.