2

ランダムに生成された多数の交差する線から作成されたすべてのポリゴンを識別する必要がある JavaScript コードを作成しています。次のスクリーンショットは、私が話していることをよりよく説明しています。

ここで、各ポリゴンの面積を計算し、最大面積を返す必要があります。私が取っているアプローチは、すべての交点 (赤い点で示されている) を識別し、それらが属するポリゴンの頂点として扱うことです。各頂点/交差点がどのポリゴンに属しているかをどうにかして識別できれば、各ポリゴンの頂点を時計回りに配置すると、靴紐の定理を適用して各ポリゴンの面積を見つけるのは簡単です。

しかし、私は完全に迷っており、これを達成するためにさまざまな (失敗した) 方法を試しました。各ポリゴンの時計回りに配置された頂点のリストをコンパイルする最良の方法は何ですか? 私は、特定の交差点ごとにどのセグメントが関連付けられているかを取得することに取り組んでいます。これは正しい方向への一歩だと思いますが、そこからどこへ行くべきかわかりません。これにはベクトル作業が必要ですか?

4

2 に答える 2

1

ひとつの可能性が考えられます。ここでは、各頂点にラベルを付けました。


(ソース: i.imm.io )

関連する線とその交点がわかっていれば、特定の点で交差するすべての線分を見つけることができると思います。では、特定のポイント、たとえばKと有向セグメント から始めましょうIK。これで、その端からつながる 4 つの有向セグメント、、KI、ができました。ライン上ではなく、最も近くにある 2 つのみに関心があります。で同じことができますが、に焦点を当てましょう。KJKLKMKIKMKJ

(点で交差する線が 3 本以上ある場合でも、線に最も近い 2 本を見つけることができます。通常、1 本は最初のセグメントと正の角度を形成し、もう 1 本は負の角度を形成します。)

が正の角度であることに気付き、IKMを含むセグメントを調べ、Mで最小の正の角度を持つものKMを選択しMFます。、これで 1 つの多角形、六角形が完成します。FFGGHHIIKMFGH

の元のセグメントに戻りIK、他の最小角度 を見てIKJ、同様のプロセスを実行して三角形 を見つけますIKJ。を含むすべてのポリゴンが見つかりましたIK。

それからもちろん、他のセグメントごとにこれを繰り返します。重複を削除するか、パスが重複していることがわかっている場合はパスの分析を継続しないようにする必要があります。(各角度は最大で 1 つのポリゴンに含まれるため、既に記録されている角度が表示されている場合はスキップできます。)

ポリゴンが凸状でない場合、これは機能しませんが、長方形を切り取った線から作成されている場合、それらは常に凸状になると確信しています。

実際にこれをコーディングしようとしたことはありませんが、うまくいくと確信しています。

于 2013-09-04T03:31:28.310 に答える
0

私が考えることができる2つの方法は、おそらく最も効率的ではありませんが、役立つはずです:

  1. 任意の点から他の点まで架空の線を引くことで、任意の点を含む多角形を構成する点のセットを把握できます。画像内のどの線とも交差しない線を引くものが頂点です。気になる凸多角形。この方法の問題は、すべてのポリゴンを確実に取得するための特に優れた方法を思いつかないことです (最大のおそらくランダム/定期的なサンプリングで十分であることに関心があるだけなので?)

  2. 考えられる各多角形について、その多角形内にある線分 (多角形の 2 つのエッジを二等分する線分) があるかどうかを確認し、その多角形がセットから削除されているかどうかを確認します。最後に、あなたが気にかけているものだけを残す必要があります。ただし、この方法は非常に遅いです。私の説明が不明確な場合は、説明を助けるためにいくつかの写真で更新できます.

お役に立てれば！

于 2013-09-04T02:43:23.157 に答える