5

それぞれがポイントのリストとして表される多数のポリゴンがあります。ポリゴンのリストを調べて、交差したエッジがなくなるまですべての交差したエッジを交差解除する高速アルゴリズムを探しています。

現在のバージョンの疑似コード:

While True:
    For each pair of polygons:
         for edge1 in first_polygon:
             for edge2 in second_polygon:
                 if edges_cross(edge1,edge2): # Uses a line segment intersection test
                     uncross_edges(first_polygon,second_polygon,edge1,edge2)
    If no edges have been uncrossed:
        break

これは、while ループを再帰に置き換えることでかなり改善できます。ただし、パフォーマンスの点ではまだかなり悪いです。

以下は、もつれを解く*の簡単な例です。実際には多数のポリゴンがあり、ポリゴンごとにかなりの数のポイント (約 10 ～ 500) があります。赤い線は、交差していない 2 つのエッジを示しています。結果は常に一連の平面グラフである必要がありますが、有効な結果が複数あるのか、1 つだけなのかは不明です。

編集:今回は、最初に線を追加してから点を追加し、もう少し複雑な形状を使用しました。ポイントが固定されているふりをします。

例

4

2 に答える 2

1

まず、あなたが望むものを説明しましょう（私がそれを正しく理解した場合）。2つのポリゴンがあり、そのうちの1つには、もう1つのポリゴンのエッジ(a, b)と交差するエッジがあるとし(s, r)ます。これらのポリゴンも時計回りの方向を向いているため、の次の頂点bとの次の頂点がわかりますr。エッジが交差しているので、両方を削除し、4つの新しいエッジを追加します。追加する新しいものは次のとおりです。 (a, r)、(r, next(b)); (s, b)、(b, next(r))。したがって、ここでも2つのポリゴンがあります。これを次の図に示します。最初に2つのエッジ（各ポリゴンから1つ）のみを削除することで、すべての交差が解決されたことに注意してください。

ここに画像の説明を入力してください

反復ごとの簡単な実装を高速化することO(n^2)は完全に簡単ではなく、ポリゴンごとに500ポイントは、心配する必要のある非常に少量です。今回改善する必要があると判断した場合、私の最初の提案は、Bentley-Otmannアルゴリズムを何らかのスマートな方法で使用することです。スマートな方法では、アルゴリズムを実行し、交差点を見つけたら、上記の手順を実行して交差点を削除し、アルゴリズムをガイドするイベントを更新します。うまくいけば、この状況でアルゴリズムを役に立たなくすることなく、処理されるイベントを更新できますが、その証拠はありません。

于 2013-01-04T05:03:03.570 に答える
0

頂点が正確に指定されたポイントのコレクションである埋め込み平面ポリゴンになりたいようです。ポイントの望ましい「順序」は、ポリゴンの境界を一周し、頂点を出現順に列挙することによって得られるものです。

一般に、ポイントの特定のコレクションには、このプロパティを持つ複数の埋め込みポリゴンがあります。例として、次の点のリストを検討してください。

(-1,-1), (0,0), (1,0), (1,1), (0,1)

このリストは、あなたの基準を満たすポリゴンを定義します (私が正しく理解している場合)。ただし、このリストの次の順序も同様です。

(-1,-1), (1,0), (0,0), (1,1), (0,1)

これが機能するアルゴリズムの1つです（高速についてはわかりません）。

まず、ポイントを x 座標 (たとえば、クイック ソートを使用) で昇順に並べ替えます (このリストを L と呼びます)。

次に、凸包を見つけます (たとえば、quickhull を使用)。凸包の境界には、ソートされたリスト L の左端と右端の点が含まれます (これらを L[1] および L[n] と呼びます)。S を L[1] と L[n] の間の境界上の点のサブセットとします。

必要なリストは、L に表示される順序 (凸包の境界に表示される順序でもあります) の S で、その後に L に表示される順序とは逆の順序で他の要素 LS が続きます。

通常、最初の 2 つの操作には O(n log n) (最悪の場合 O(n^2)) の時間がかかります。最後は時間がかかります O(n)。取得したポリゴンは、凸包の下部境界 (たとえば、左から右) になり、その上の残りのポイントは右から左に「ジグザグ」になります。

于 2013-01-04T03:25:43.597 に答える