algorithm - 2D補間のアルゴリズム

Question

チャネルの断面である2つの形状があります。定義された2つのポイント間の中間ポイントの断面を計算したいと思います。この状況で使用する最も単純な（比較的単純な）アルゴリズムは何ですか？

PS：複雑に見えた、自然の隣人やポアソンのようないくつかのアルゴリズムに出くわしました。迅速に実装できるシンプルなソリューションを探しています。

編集：誤解を招く可能性があるため、タイトルから「Simplest」という単語を削除しました

Answer 1

これは簡単です：

1. 各断面に、断面の境界に沿って等間隔でN点を描画します。
2. 断面1のn番目の点から断面2のn番目の点まで直線を描きます。
3. 古い断面間の希望の距離で新しい断面を外します。

さらに簡単：

1. 変更せずに既存の断面の1つを使用します。

この2番目の提案は単純すぎると思いますが、もっと単純な提案をする人はいないでしょう。

OPのコメントに続いて編集:(コメントするには多すぎます）

さて、あなたは簡単な方法を求めました！最初の方法であなたと同じ問題が発生するかどうかはわかりません。断面があまり奇妙ではなく（凸多角形の場合はおそらく最適です）、一方の断面の左側をもう一方の断面の右側にマッピングするなど、奇妙なことを何もしない場合（これにより、多くの交差線が強制されます） ）次に、メソッドはある種の適切な断面を生成する必要があります。三角形と長方形を提案する場合、三角形がその底辺にあり、頂点が1つ上にあると仮定します。その点を、たとえば長方形の左上隅にマッピングしてから、対応する点を結ぶ両方の断面の境界を中心に同じ方向（時計回りまたは反時計回り）に進みます。交差する線は見当たりませんが、

Answer 2

High Performance Markの回答には、おそらく対処する必要があり、彼のメソッドの出力の品質を定義するいくつかのあいまいさがあります。最も重要なのは、n両方の断面にポイントを描画するときに、それらの間でどのような対応を決定するかです。つまり、High Performance Markが提案する方法でそれを行うと、ポイントにラベルを付ける順序が重要になります。

両方の断面で（直交する）平面を同時に回転させることをお勧めします。次に、一方の断面でその平面と交差する点のセットを、もう一方の断面でその平面と交差する点のセットと一致させる必要があります。仮に、これらのセットのポイント数に制限はありませんが、元の状況での対応問題の複雑さを確実に軽減します。

Answer 3

これが問題の別の試みです。これははるかに良い試みだと思います。

2つの断面を考えるとC_1、C_2

それぞれC_iを座標系を使用してグローバル参照フレームに(x,y)配置し、それらが比較的配置されている方法が意味をなすようにします。C_iそれぞれを上下の曲線U_iとに分割しL_iます。U_1カーブをU_2に連続的に変形させたいという考えになりL_1ますL_2。C_i（必要に応じて、このメソッドを拡張して、それぞれをm曲線に分割できることに注意してください。）

これを行う方法は次のとおりです。各T_i = U_i, or 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^n として定義します。ここで、変形がどのポイントにあるかを定義します（つまり、私たちがいるとき、私たちがいるとき、そして他のすべての場所で、2つの連続的な変形があります）。まったく同じことが続きます Q{P{U_1},P{U_2}}(x, t) = ( t * a_0 + (1 - t ) b_0 ) + ... + (t * a_n + (1-t) * b_n ) * x^nQ0<=t<=1tt=0U_2t=1U_1tQ{P{L_1},P{L_2}}(x, t)。これらの2つの変形は、任意のでサンプリングできる2つの断面間の連続表現を構​​築しますt。

これが実際に行っているのは、両方の断面の2つの部分の補間多項式の係数を線形補間することだけであることに注意してください。また、断面を分割するときは、一致する端点で分割する必要があるという制約を設定する必要があります。そうしないと、変形に「穴」が生じる可能性があります。

それがはっきりしていることを願っています。

編集：多項式の補間における振動の問題に対処しました。