2D画像でランダムに選択されたピクセルのセットKがあります。画像内の他のすべてのピクセルについて、セット K 内のどのピクセルがそれに最も近いかを調べる必要があります (距離の標準的な sqrt(dx^2 + dy^2) 測定を使用して)。各ピクセルに対して複数のソリューションが存在する可能性があることは承知しています。明らかに、セット内のすべてのピクセルに対して力ずくで実行できますが、効率的ではないため、これは避けたいと思います。他に良い提案はありますか？
乾杯。
32762 次
8 に答える
40
平方根を気にする必要がないことを忘れないでください。
最も近いもの（実際の距離ではなく）を見つけたいだけの場合はdx^2 + dy^2、 を使用するだけで、各アイテムの距離の二乗が得られます。これは同様に便利です。
このピクセルのリストをラップするデータ構造がない場合は、それらすべてに対してテストする必要があります。
ある程度の柔軟性があれば、作業負荷を軽減するための良い方法がたくさんあります。Quadtree を作成するか、並べ替えられたピクセルのリスト (x で並べ替え、y で並べ替え) を保持して、検索をより迅速に絞り込みます。
于 2009-12-14T14:15:39.563 に答える
21
ボロノイ図を作成することについては、jk と Ewan に同意する必要があります。これにより、スペースがポリゴンに分割されます。K のすべての点には、それに最も近いすべての点を表す多角形があります。ポイントのクエリを取得したら、それがどのポリゴンにあるかを見つける必要があります。この問題はPoint Locationと呼ばれ、台形図を作成することで解決できます。
jk は、 O(n log n) の計算ステップと O(n) のスペースを必要と
するフォーチュンのアルゴリズムを使用したボロノイ図の作成に既にリンクされています。この Web サイトでは、台形マップの作成方法とクエリの方法を紹介しています。そこにもいくつかの境界があります:
予想される作成時間: O(n log n)
予想されるスペースの複雑さ: O(n)
しかし、最も重要なことは、予想されるクエリ時間: O(log n) です。これは、kD ツリーの O(√n) よりも (理論的には) 優れています。
私のソース（上記のリンク以外）は次のとおりです。計算幾何学：アルゴリズムとアプリケーション、第6章と第7章。
そこには、2 つのデータ構造に関する詳細情報 (詳細な証明を含む) があります。Google ブックス バージョンには必要なものの一部しかありませんが、他のリンクは目的に十分なはずです。そのようなことに興味があるなら、その本を買ってください (良い本です)。
于 2009-12-14T16:21:38.420 に答える
7
ボロノイ図の作成は、計算幾何学の一分野です。Delaunay Triangulationsの作成には、同様の考慮事項が含まれます。次のDelaunay アルゴリズムのいずれかをニーズに合わせて調整できる場合があります。
- フリップアルゴリズム
- 増分
- 分割統治
- スイープライン
于 2009-12-14T14:24:18.207 に答える
7
ポイントを KD ツリーに配置します。この後、最近傍を見つけるのは非常に高速です。詳細については、ウィキペディアのこの記事を参照してください。
于 2009-12-14T14:24:52.137 に答える
6
これを最近傍探索と呼びます。ドナルド・クヌースはこれを郵便局問題と呼んだ。
解決策は多数あります: 線形検索、局所性に敏感なハッシング、ベクトル近似ファイル、および空間分割。
それらをグーグルで検索すると役立つはずです。
于 2009-12-14T14:15:37.677 に答える
5
あなたがしようとしているのは、ボロノイ図を作成することです。これは、平面スイープを使用してO（n log n）で実行できます。
于 2009-12-14T14:16:43.057 に答える
4
別のヒント: 距離は常に各座標差以上であり、常にそれらの合計以下です。
d >= dx, d >= dy, d <= dx + dy.
これにより、並べ替えをより効率的に行うことができます。
于 2009-12-14T14:16:32.483 に答える
2
このグラフィックがピクセルで埋め尽くされている密度によっては、元のピクセルから外に向かって検索する方がよい場合があります。
グラフィック端末エミュレーション用にこのようなものをプログラムしました。私が最終的にやったのは、中心点から成長する四角形のらせんの形で検索パターンをプログラムし、それが何かに当たるまで成長させることでした. これは、古い CPU でも十分に高速でした。
于 2009-12-14T14:16:01.767 に答える