0

次の問題を解決する最善の方法を見つけるのに苦労しています。それらを解決する複数の方法を試しましたが、常にいくつかのコーナーケースに遭遇しています。

問題は次のとおりです。

  1. 閉じた多角形を形成するList座標 (x 点と y 点) があります。このリストは、点が時計回りに並べられた多角形を形成することが保証されています。
  2. Set上の座標からの座標 (x 点と y 点)が与えられますList。
  3. 上記のすべてのポイントを使用して形成される線の始点と終点を把握する必要がありますSet。

私が抱えている問題は、「最適な」開始点と終了点を見つける方法がわからないことです。多くのシナリオでは、( のインデックスを使用してList) 最初と最後のポイントを選択して開始点と終了点を形成できますが、必要以上に長い線になる可能性があります。

たとえば、次の多角形があるとします: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 0 そして、Set線分に含まれる必要がある次の座標: 0, 7, 3.

最小インデックスと最大インデックスが見つかると、 が得られるのでindex(0)、有効なラインであるindex(7)ライン を形成できます0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7が、必要以上に長くなります。最適な線分は です7 -> 0 -> 1 -> 2 -> 3。

Set最適な (すべての点を含む最短の) 線分を効率的に見つけるにはどうすればよいですか?

コンテキストについて: 私は、JTS ジオメトリを使用して形状を描画するアプリケーションに取り組んでいます。描画された形状は、ベジエ曲線を使用して平滑化され、「湾曲したエッジ」になります。(点をドロップして) 形状を描画した後、ユーザーは形状を編集できます。Set影響を受ける領域のみを「滑らかにする」ことができるように、変更されたポイント (上記のフォーム) を使用して開始点と終了点を把握したいと考えています。

4

2 に答える 2

1

したがって、 があり、Setこのセットをインデックスの順に に移動する必要がありますList。

変換ISet=[Index(i, List) for i in Set]

次の並べ替えISet

の連続するアイテムISetのペアとペア (最後、最初) は、そのペアの距離を計算します。

最大距離でペアに罰金を科しました。それなら、最高の始まりと終わりはそのペアです。

于 2016-05-27T14:07:40.700 に答える
1

セットを並べ替えられたリストに変換し、このリストをそのコピーと連結します。ここで、すべての要素がポリゴン頂点の数 N で追加されます。次に、この二重リストで最長の空のラン (近隣差) を見つけます。次に、必要な長さのサブリストを取得し、それを連続範囲に変換します (ただし、N を法とする要素を取ります)

(0,3,7) + (0+8,3+8,7+8) = (0,3,7,8,11,15)

最大差は 7-3 であるため、最良のケースのサブリストは 7 から始まります。

 (7%8 .. 11%8) = (7,0,1,2,3)
于 2016-05-27T14:20:55.640 に答える