プログラマーの場合、選択したゲームエンジンまたはライブラリに目的の機能がない場合があります。 この後、あなたがこの問題を解決する前に書かれたコードを探してインターネット全体を検索しなければならなかった恐ろしい瞬間が続きました（私はあなた、StackOverflowのユーザーについて話している）。 もちろん、それで何も問題はありません（私は自分でこれを行います）が、ジオメトリやシャッフルなどの理論的な問題になっても、非常に頻繁に自分でそれを行うことができます。 私は常にすべてがどのように機能するかを理解しようとする人々の一人であり、その場で解決策を再発明することによって自分で解決するよりも本当に良い理解方法がありますか？
タスクの例を設定します
この記事では、問題を解決するアルゴリズムを独自に導出するのに非常に効果的であると思われるいくつかの段階について説明します。 それらを特定の何かに適用するために、問題の例を考えます。単純なポリゴンの凸状のパーティションです。 複雑で科学的に聞こえますが、実際はそれほど難しくありません。
単純なポリゴンとは、それ自体と交差せず、穴のないポリゴンです。 凸多角形とは、すべての角度が180°未満の多角形です。 もちろん、凸多角形は単純な多角形であり、単純な多角形は複雑な多角形（最も一般的なクラスの多角形）ですが、その逆は必ずしも当てはまりません。
凸面、単純および複雑なポリゴン。
凸面ポリゴンの非常に優れた機能は、2つの任意の凸面ポリゴン間の衝突チェックが非常に単純である（記事ではこれについては説明しません）が、2つの任意の複合体、または単純なポリゴン間での衝突チェックは非常に困難です ここで、凸状のパーティションが作用します。単純なポリゴンをいくつかの小さな凸状のポリゴンに分割できる場合、その衝突はパーティションの少なくとも1つのポリゴンとの衝突に似ています。 したがって、タスクの例は次のようになります。単純な多角形を記述するポイントの配列を持ち、凸多角形を記述する配列の配列を返し、元の多角形を「合計して」返します。
理想的には、私たちのアルゴリズムはそのような操作を実行できるはずです。
作業内容を学ぶ
アルゴリズムを開発する場合、最も重要なことは、解決したい問題、つまりアルゴリズムが最初にすべきことを特定することです。 これはばかげて聞こえるかもしれませんが、より重要なのは、アルゴリズムがどのように機能するかではなく、入力で受け取るものと出力で受け取るもの（必要に応じてデータ構造を含む）です。 多くの場合、使用しなければならないデータ構造を知ることは、推論を定式化するのに役立ちます。 たとえば、並べ替えアルゴリズムを作成する場合、入力で配列を受け取る可能性がありますが、出力はどうなりますか？新しい配列、何もない、または適切な並べ替え（元の配列自体を直接変更する）
曲線のアルゴリズムについての私の以前の記事を読んでください。これは、入力データと出力データの特性評価が非常に難しいアルゴリズムの良い例です。 実際、入力アルゴリズムは浮動小数点数と整数の関数を受け取り、関数はパラメトリックカーブと整数-サンプリングステップ数を表します。 アルゴリズムは、出力で浮動小数点数の別の関数、つまり、記事の対象となる「曲線」関数を返す必要があり、本質的には元の曲線のより一般的なバージョンです。
上記のタスク例では、アルゴリズムは入力でポイントの配列を受け取り、出力でポイントの配列を返します。 入力は単純なポリゴンの頂点になり、出力は元のポリゴンの凸パーティション内のすべての凸ポリゴンの頂点になります。
まず第一に-脳と紙。
紙と鉛筆（リスクを取るのが好きならペン）から始めることは、タスクを知覚するための最良の方法の1つであり、これはアルゴリズムの作成だけでなく（プログラミングだけでなく）適用されます。 もちろん、プログラミングも例外ではありません。始めから始めましょう。
まず、直感的なアプローチを開発するために、ほとんどの場合、実際に何をしているのかを考えずに自分で解決できる単純なケースのスケッチ（または作業内容に応じて記録）から始める価値があります。 この作業の過程またはその後で、あなたはそれについての考え方を分析し、段階に分けて整理する必要があります。 アイデアは、あなたがそれを望むかどうかに関係なく、アルゴリズムを実行しているということです。あなたの脳はコンピュータであり、人間に知られている最も強力なコンピュータです。 非常に強力なので、彼は自分の作品を見て理解することができます。 非常に強力なため、作成しようとしているアルゴリズムを既に実行していますが、何らかの理由でまだ理解していません（まだ理解していないためです！）。 ただし、アルゴリズムを段階的にたどって、その仕組みを理解することができます。 この理論をテストするために、問題の例に戻って単純なポリゴンを使用してみましょう。
このような多角形を自分で描いて、この時点で読み取りを停止して、この多角形を小さな図形に分割して、180°を超える内角が決してないようにすることをお勧めします。 上記の図で決定を示しましたが、誰もが異なる考え方をしているため、最終的には他の形状を得ることができます。 そして、これは絶対に正常です。実際、単純な多角形の凸状パーティションは一意ではありません！
これらのパーティションは両方とも凸型です。
既知の宇宙で最も強力なコンピューターを使用して、実際にそれを知らずに計算幾何学アルゴリズムを数秒で適用した後、アルゴリズムを元に戻して段階に分割できます。 私は繰り返しますが、私たちは皆異なって考えているので、手順は異なる場合があります：私はそれを私の推論に適用し、あなたのものは非常に似ています。
最初に、私は自分自身に質問をしました。なぜこの多角形はまだ凸面ではないのですか？ 答えはすぐに得られました：いくつかの内角が180°以上（つまり、図の矢印で示されているうちの2つ）であるため、定義上、多角形が凸になることはありません。 これを修正するために、2つの小さな角度を取得するためにコーナーをカットする必要があると考えました。これは理想的には180°以内です。 これは、「欠陥」頂点をポリゴンの他の頂点と接続することで実現できます。 欠陥のあるすべての頂点に対してこれを繰り返し、凸型タイルを取得します！
ステップごとの直感的な凸型パーティション。 矢印は「欠陥のある」頂点を示します。
素晴らしい、それはすべて非常に迅速に起こりました。 しかし、実際に何が起こったのでしょうか？ この段階で、自然言語に似た擬似コードでアルゴリズムの種を書くことができます。 これは正確に言語の文ではありませんが、完全にプログラミングされているわけではありません。 脳の中で「プログラマのように考える」インストールを実行するのに十分なプログラミングのように見えます。
「欠陥」トップがありますが
ポリゴンの他の頂点に接続します
さようなら
このことから、上部が「欠陥」であるかどうかを判断する方法が必要であることが明らかになります。 これを行うには、頂点を構成する2つのエッジが180°を超える角度を作るかどうかを確認するのは簡単です。 ただし、別のより深刻な問題があります。どの頂点を欠陥のある頂点に接続するかを選択しますか？ 前回やったことをもう一度考えてみましょう。
この方法で行いました。パーティション内のポリゴンの数を最小限に抑えるために、各ポリゴンにできるだけ多くの頂点を含めるようにしました。 一般的な場合、これは良いアイデアです。なぜなら、長方形に結合する2つの三角形よりも1つの長方形を処理する方が効率的だからです。 これを次のように行います。順番に、各頂点を欠陥のある頂点からチェックし、ポリゴンを非凸頂点に変える頂点が見つかるまで確認し、その後、頂点が残った最後の頂点を選択します。 三角形は常に凸であるため、これは常に可能です。したがって、最悪の場合、三角形が得られます。 これで、擬似コードは次のようになります。
欠陥のあるトップがある間
一方、次の頂点は、欠陥のある頂点と180°以下の角度を形成します
次のピークに行く
この新しい頂点によって形成される角度が180°より大きい場合、停止して前の頂点を選択します
さようなら
欠陥のある頂点を選択した頂点に接続します
さようなら
しかし、このチェックは、いくつかの疑わしい状況につながる可能性があります。欠陥のある頂点の直後の頂点にも欠陥がある場合はどうでしょうか。 検証プロセス中に欠陥ピークに達した場合はどうなりますか？ 2番目の質問は、凸多角形に欠陥のある頂点が存在しないという観察のおかげで解決するようです。角度を分割するときに追加するエッジが「正しい」頂点に変わるように、すぐに停止して選択する必要があります。 最初の質問は直感的に解決できます。問題を手動で解決するとき、左端または右端の欠陥頂点から意図的に開始し、明らかに他の欠陥頂点の間にある頂点からではないため、これは起こりません。 コードでは、これは単純に欠陥のある頂点から調査を開始するという事実に変換されます。欠陥のある頂点には間違いなく正しい隣接点があります。 単純なポリゴンには常に少なくとも1つの「通常の」（つまり、欠陥のない）頂点があるため、これは常に可能です。 それを見つけ、それを使用して、1つの欠陥のある頂点を取り除き、繰り返します。 擬似コードは次のようになります。
欠陥のあるトップがある間
後に「正しい」ピークがあるものを選択します
欠陥のある頂点を持つ次の頂点が180°以下の角度を形成するまで
次のピークに行く
この新しいトップが「間違っている」場合、停止して選択する
それ以外の場合、この新しい頂点によって形成される角度が180°より大きい場合は、停止して前の頂点を選択します
さようなら
欠陥のある頂点を選択した頂点に接続します
さようなら
そして、実行されると、コードは次のようなものを提供します。
アルゴリズムの1つのステップ：欠陥のある頂点を接続する頂点を選択します。
かなりよさそうです！
もう1つの疑問が残っています。ここで、ポリゴンをエッジではなく頂点の配列として保存します。「頂点接続」とはどういう意味ですか？ 多角形の頂点を追加または削除しないので、おそらく頂点の配列を変更できませんか？ それともできますか？
手動で作業するときにこの問題にどのようにアプローチしたかを見てみましょう。エッジを描画した後、凸になった部分にまったく関心がなくなり、残りの頂点のみに焦点を当てます。 ただし、新たに追加されたエッジに引き続き関心があり、検索でそれを構成する頂点を追加します。 これにはかなり明確な解釈があります：多角形を凸と単純の2つの部分に分割するだけで、新しい小さな単純な多角形にアルゴリズムを再適用するときに凸部分を気にしません！
これで「接続」の意味を理解できます。本質的に、これは開始点と終了点の間のすべての頂点からの新しいポリゴンの作成です（つまり、図の緑と赤。結果のより小さい頂点グループに対してアルゴリズムを繰り返し呼び出して、元のポリゴンから。 追加されたエッジを構成する両方の頂点が両方のポリゴンに存在する必要があることに注意してください！
アルゴリズムの完全な反復を完了し、1つの凸部と1つの単純な部分を取得するたびに、凸部を配列に追加する必要があります。これは、アルゴリズムが完了後に返す配列、元のポリゴンの凸成分の配列です。 単純な部分については、ご想像のとおり、再びアルゴリズムを呼び出します。
擬似コードは次のようになります。
関数makeConvex
欠陥のある頂点を選択します。その後、「正しい」頂点があります
次の頂点は180°以下の欠陥角を形成します
次のピークに行く
この新しいトップが「間違っている」場合、停止して選択する
それ以外の場合、この新しい頂点によって形成される角度が180°より大きい場合は、停止して前の頂点を選択します
さようなら
欠陥のある頂点と選択された頂点の間のすべての頂点を、それらの両方を含めて配列に追加します
欠陥のある頂点と選択された頂点の間の元のポリゴンからすべての頂点を削除します。両方は含まれません
新しいポリゴンに対して呼び出されたmakeConvex関数の結果と連結された凸配列を返します
機能の終わり
これで完了です！ 脳と紙を使った作業の段階は完了しています。 この段階の後、すべてのさらなる作業はすでに実装に関連しているので、お任せします！
あとがき
擬似コードはかなり単純なアプローチを提供し、最適化されていないことを忘れないでください。 ポイントは、最も効率的なアルゴリズムを作成することではなく、独自のアルゴリズムを作成する方法を学ぶことです。 より多くのアルゴリズムを考え出すと、おそらくいつか他の誰も考えもしなかったスマートなアルゴリズムの正しいアイデアを思いつくかもしれません。 この記事を読んだ後、オンラインで特定の問題の解決策を探す前に、独自の解決策を作成することを検討する必要があると判断した場合、私は自分の目標を達成したと仮定します。