私は次の問題の迅速な解決策を探しています：
固定点（たとえば、白い測定線の右上）があり、等間隔の点で構成される曲線（下の曲線）で最も近い点を見つける必要があります。さらに、上の曲線のすべてのポイントに対してこれを実行して、異なる色の曲線間の距離を描画します（3つのレベル：最小[赤]未満、最小と最大[オレンジ]の間、最大[緑]より上）。
私の現在の解決策はトレードオフです。固定小数点を取得し、任意の間隔（たとえば、固定小数点の左右に50単位）を反復処理して、各ペアの距離を計算します。これによりCPUパワーがいくらか節約されますが、選択した間隔の外側の最小距離を逃す可能性があるため、エレガントでも正確でもありません。
より高速なアルゴリズムの提案はありますか？
編集：等間隔とは、すべてのポイントがx軸上で同じ距離にあることを意味します。これは、両方の曲線に当てはまります。また、ポイント間を補間する必要はありません。これには時間がかかりすぎます。
任意の距離ではなく、「範囲外」になるまで繰り返すことができます。
あなたの例では、線の右上にある上の曲線上の点から始めたと仮定します。次に、垂直に下向きにドロップすると、（私の目では）約200umの距離が得られます。
これで、水平距離が200umになるまで、ここのテストポイントから右に移動できます。それを超えると、200um未満の距離を取得することは不可能です。
左に移動すると、150umの最小値が見つかるまで距離が下がり、その後再び上昇し始めます。上のポイントの左側に150umになると、ここでも、見つけた最小値を超えることはできません。
最初に左に行った場合は、右端まで行く必要はなかったので、最適化として、距離が下がる方向に従うか、中央から両方向に同時に作業します。
50ユニットがいくつあるかわからないので、これはあなたが持っているものより遅いか速いかもしれません。ただし、低い値を見逃すリスクは回避されます。
下の曲線上の同じ点のセットに対して多くのテストを行っているので、点が曲線を形成するという事実をまったく無視することで、これをおそらく改善することができます。それらをすべてkdツリーなどに貼り付けて、繰り返し検索します。これは、最近傍探索と呼ばれます。
この問題を最近傍探索の問題として特定すると役立つ場合があります。このリンクには、これに使用されるさまざまなアルゴリズムに関する適切な説明が含まれています。ストレートCではなくC++を使用しても問題がない場合、ANNはこのための優れたライブラリのように見えます。
また、この質問は以前に尋ねられたように見えます。
上の曲線y=t（x）と下の曲線y = b（x）にラベルを付けることができます。最も近い関数x_b=c（x_t）にラベルを付けます。2つの最短経路が互いに交差することはないため、最も近い関数は弱く単調で減少しないことがわかっています。
距離関数d（x_t、x_b）が固定x_tごとに1つの極小値しかないことがわかっている場合（これは、曲線が「十分に滑らか」である場合に発生します）、曲線を「歩く」ことで時間を節約できます。
- start with x_t=0, x_b=0
- while x_t <= x_max
-- find the closest x_b by local search
(increment x_b while the distance is decreasing)
-- add {x_t, x_b} to the result set
-- increment x_t
x_bが十分に滑らかであると期待しているが、それを想定できず、正確な結果が必要な場合は、
カーブを両方向に歩きます。結果が一致する場合、それらは正しいです。同意しない場合は、2つの結果（左端と右端の極大値）の間で完全な検索を実行します。単調性のために最も多くの剪定を可能にするために、そのような順序（バイナリ除算）で「あいまいなブロック」をサンプリングします。
中間点として：
カーブを両方向に歩きます。結果が一致しない場合は、2つから選択してください。固定されたx_tごとに最大2つの極大値を保証できる場合、これにより最適な解が得られます。最適な解が見つからず、両方ともこれよりも悪い他の2つの極小値が隣接する極小値を含む病理学的ケースがまだいくつかあります。解が最適とはほど遠いケースを見つけることはめったにないと思います（滑らかなy = b（x）と仮定）。