1

多くの直線を含む 2D 図面があります。これらの行はすべて数学的に知られています。そして、それらは他のものから独立しています。

各線の始点と終点を知っていると考えることができ、それらを交差させてすべての交点を見つけることができます。(詳しくは、Autocad に入っていますが、コードでしか作業できません。したがって、Autocad ソリューションよりもアルゴリズムが必要ですが、Autocad ソリューションも歓迎されます)。

問題は、ポイント (どこでも) が与えられた場合、それを含む小さなポリゴンを見つけたいということです。その多角形は、最も近い線によって形成されます。

詳細：

宣言されたポリゴンはありません。ただの線。任意の行数、任意のサイズ、任意の位置。そして所定のポイント。

これらの線は、1 つの多角形を形成する場合もあれば、多数の場合もあれば、まったく形成されない場合もあります。したがって、ポリゴンがどのように見えるかについての規則はありません。面の数に制限はなく、規則性はありません。(多角形を形成する点は、線を交差させることによって見つけられます。線は有限であり、交差しなければ多角形を形成しません。)

私の答えは、特定のポイントを含む可能な限り最小のポリゴンです。

4

2 に答える 2

2

わかりました、私はこれについてしばらく熟考してきました。そして、機能すると思われるバックトラッキングアルゴリズムを作成しました。アイデアは、反時計回りに多角形を構築しようとすることです。そして、見つけた最初のポリゴンが最小になるように問題を設定します。そうすれば、それらすべてを見つける必要はありません。

アルゴリズム：

  1. 線分を目標点に近い順に並べ替えます。
    • 今後、行をループする必要があるときはいつでも、このソートされた順序でループします
    • ターゲット ポイントからの距離を計算するときは、線分を無限線として扱います。 点/線距離
  2. 「反時計回り」方向の線に沿って2 番目の交点 を使用して、最も近い線分で手順 3 を実行します。
    • 「反時計回り」とは、ターゲット ポイントが線の左側に来る方向を意味します。
    • 注: 最初の交点は、目標点を回避した後に到達する場所になることを願っています。

  3. 新たに発見されたラインで...

    A. 作成中の形状の一部ではない他のすべての線をループし、この線との交点を見つけます
    B. 交点をターゲット ポイントに対して反時計回りに並べ替えます。
    反時計回りの並べ替え

  4. 現在の行で反時計回りに次の交点を見つけます。これがこの線でチェックしている最初の点である場合、「次の」点は、この線に到達した交点の後の点です。

    A. そのような点がない場合 (これは、現在の行のすべての点を既に確認したことを意味する可能性があります)、現在の候補解は実行不可能です...

    • 前の行に戻り、その行の次のポイントで手順 4を繰り返します。
    • 前のラインがない場合 (つまり、シェイプを開始したラインにいる場合)、バックトラックして次に近いラインでステップ 2を実行し、新しいシェイプを開始します。

    B. 交点を形成する線の左側 (反時計回り) にターゲット ポイントがない場合、それが形成するポリゴンはターゲット ポイントを囲みません。 次のポイントを含む現在の行に対して手順 4 を繰り返します。
    C. 交点を形成する線が最初の線である場合、解決策が見つかりました
    D. 上記のいずれにも当てはまらない場合は、交点を形成する線に対してステップ 3を実行します。

最適化:

  1. 3 行未満の場合、解決策はありません。仕事をしないでください。
  2. 交点が見つかったらキャッシュして、再計算する必要がないようにすることもできます。
    • これを行う場合は、2D 配列を使用することをお勧めします
  3. 解決策の一部ではないことがわかっている場合は、行を捨てることをお勧めします。
    • 例: ターゲット ポイントに最も近いラインを既に試したが、解決策につながらなかった場合、他のライン上の交点を見つけるときにそのラインを含めても意味がありません。

備考：

  • このアルゴリズムは、再帰的に実装するのが最も簡単です。
  • ターゲット ポイントがいずれかの線上にある場合の対処方法を決定する必要があります
于 2013-05-22T15:31:42.597 に答える
1

次のアルゴリズムが機能すると思います。

  1. 3 行未満の場合は終了します。解決策はありません。
  2. 目標点に最も近いラインを決定します。この行は、ソリューションの一部であることが保証されています。
  3. P1 を L1 上のターゲット ポイントの垂直投影とします。
  4. P1 に最も近く、その反対側にある L1 との他の線の 2 つの交点を見つけます。これらの 2 つのポイントは、ソリューションの一部であることが保証されています。
    • これらの点を P2 と P3 と呼び、線を L2 と L3 と呼びましょう。
    • そのような点がなければ、解決策はありません。
  5. L2 と L3 のそれぞれで、P2 と P3 にそれぞれ最も近く、L1 のターゲット ポイントと同じ側にある最も近いポイントを見つけます。
  6. 次のようになるまで、手順 4 と 5 を繰り返します。
    • 両方向から出ている線は同じ線
    • 両方の方向から来る交点は同じ点です
    • 条件に一致する検索ポイントはありません。これは、解決策がないことを意味します。
于 2013-05-10T22:05:38.207 に答える