🗒️ 🧛🏻 🌜 分割統治法を使用してボロノイ図を作成します。ロイドのリラクゼーション 🍥 🚣🏼 💾

最近、ボロノイ図に完全に専念した記事がhabrahabrで公開されました。この記事では、著者はO（n * log（n））のボロノイ図を作成するために使用されるFortuneアルゴリズムについて詳しく説明しています。このアルゴリズムの説明がRuNetに繰り返し登場している一方で、他のアルゴリズムについては何も言われていないことに注意してください（同じ漸近性）。この記事では、この誤解を修正し、以前に公開された資料への優れた追加資料でもあります。

以下では、 O（n * log（n））のボロノイ図を作成する分割統治アルゴリズムについて説明し ます。また、私の実際の経験に基づいて、これが適用できる本当にクールなことについて説明します。一般的に、 分割統治アルゴリズムは一種のプログラミングの古典であり（すべてのプログラマーがこの方法を使用したソートについて聞いたと思います）、それらは並列で読みやすい（もちろん、アルゴリズムの主要な概念を知っている場合）。

ボロノイ図を作成するための「分割統治」アルゴリズムの説明

ポイントの初期セットは、座標（put、x）の1つでソートされ、2つのほぼ等しいセットに分割されます。結果の各セットは再び2つに分割され、各セットに2つ以下のポイントが残るまでこれが行われます。そのようなパーティションlog（n）しか存在しないことは簡単にわかります。さらに、取得された各セットについて、ボロノイ図が構築され、その後、逆の分割順序で、これらの図が1つに結合されます。結果のボロノイ図が最終結果になります。

記述されたアルゴリズムがO（n * log（n））の次数の複雑さを持つためには、 O（N）の背後にある2つのボロノイ図を結合するプロセスを実行する必要があります。 2点のセットの場合、ボロノイ図はこれらの2点で形成されるセグメントの中央の垂直線になります。

すべてのポイントがX座標でソートされ、元のセットが2つに分割され、それぞれに対してボロノイ図が作成されるとします。これらのセットと図の結合を次のように実行します。

⦁1 .サブセットごとに凸包を見つけます（各セットの凸包の構築は同じ「分割して征服」できることに注意してください。つまり、ボロノイ図の結合の各ステップで、これらのセットの凸包をO （N） ）。

⦁2 .元のセットの2つの凸包があるので、これらのセットの「上部および下部」境界を見つけます。つまり、2つの与えられた凸包を1つ（自然に凸）に結合する2つのセグメントを見つける必要があります。したがって、ステップ1の条件を満たし、ステップ3の初期化値も取得します。このステップは、先ほど書いたようにO（N）で実行できます。

⦁3 . ステップ2で得られたセグメントからanyを選択し、それをL （ Qで示す残りの部分）で示し、その中央を通る無限の光線を垂直に発射します。この光線が元のセットのみに進入し、初期セットのボロノイ図のセルとの交点を見つけると想像してください（光線は前方に伸びている、つまり方向を持っていると考えられています）。光線は、光線を放出するセグメントの端が中心であるボロノイセルとのみ交差します。この光線と対応するボロノイセルの交点を見つけ、それらの中から前に交差するものを選択する必要があります。この点をMで表し、交差したセルを覚えてVを表します。次に、以下を実行します：交差していないボロノイセルの中心であるセグメントLの端を残しますが、交差したセルの中心であったものを残します-更新：ボロノイセルの辺の1つを交差すると、セグメントLの新しい端がこの交差したセルに隣接するボロノイセルの中心。特別なセットS （2つのボロノイ図の境界が格納されています）では、セルの側面との交点まで延びる光線の部分を追加する必要があります。セグメントLの両端の値がセグメントQの両端の値と等しくなるまで、 手順3を繰り返します。その結果、集合Sには連続した壊れた光線が含まれます。ここで提示された多くの事実の証明（たとえば、集合Sの光線の連続性）は[1]にあります。

⦁4 .連続した壊れた光線である集合Sを取得しました。この光線は、2つのセットのボロノイ図を接続する境界です。最終結果を得るには、左のセットのボロノイ図の受信した光線の右にあるこれらのセグメントを「ワイプ」し、右のセットのボロノイ図の左にあるセグメントをワイプする必要があります。これをすばやく行うことは問題ではありません。セルを光線と交差させると、最初に光線が入射し、特定の瞬間にセルが終了することは明らかです。これらのイベントを「キャッチ」し、使用しているダイアグラムのセット（左または右）に応じて、光線で交差したボロノイセルのエッジの左または右チェーンを削除し、 そこにセットSから必要な部分を追加します。

上記のアルゴリズムは、適切な説明なしでは理解するのが困難です（写真はここで撮影されました）。

まあ、出版物のこのサブセクションを終了するのは、ポイントが同じX座標を持っている場合、それらをY座標で並べ替えて、均等かつ一貫して分割する価値があるという事実です。

ボロノイ図表アプリケーション-ロイドの緩和

ロイドの緩和は、ボロノイ図の構築が積極的に使用される驚くべき「スティッキー」アルゴリズムの1つです。アルゴリズム自体について説明します。

⦁1 .ボロノイセルを形成して、最初のポイントセットのボロノイ図を作成します。

⦁2 .各ボロノイセルの「重心」を見つけます（ボロノイセルの頂点の座標をその数で割ったもの）。

⦁3 .各ボロノイセルの中心を、計算された「重心」の位置に移動します。

⦁4 .この手順をN回繰り返します：せん断距離がゼロに近づくまで。

最後に何が得られますか？結果は、次の2つの短いビデオで見ることができます。

きれいに見えますが、少し役に立たない！？それからほど遠い！私の実務経験では、ロイドのリラクゼーションは3Dモデリングで使用されました。いわゆる「メッシュリマッピング」です。つまり、グリッドが与えられ（通常は安価な中国製スキャナーで処理された後）、タスクは結果として生じる三角形の「ハッシュ」を美しく鮮やかなものに変えます：多少正確な計算ができるものに（「グリッドの曲率」の計算、三角測量のポイントの近似）無限に滑らかな表面などのグリッド）、元の「スキャナー」グリッドからあまり逸脱しないようにしようとします（さらに、この精度はユーザーによって設定され、この種の「リメッシュ」は適応と呼ばれます。均一なリメッシュ（均一）-ここでは、設定されるのは偏差ではなく、三角形の望ましいエッジの長さです）。私は少し話し始め、 「美しい」メッシュという言葉の意味を説明するのを忘れました。グリッドの構造が主に正三角形で構成され、そのようなグリッドの各頂点の価数が6である場合（頂点が内部、つまり360. / 6. = 60度-正三角形の角度の程度）または4（頂点が開いたエッジにある場合、つまり、与えられた頂点3を持つ三角形）。さて、このようなグリッドを取得するための重要な手順の1つは、ボロノイ図を作成し、 ロイドの緩和を使用することです。実際、私たちはこの精神で何かを手に入れます（写真は大きいです！）：

私がコーディングした「リメッシュ」作業の結果の写真

宛先：