問題タブ [planar-graph]

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

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

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

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

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

平面グラフ生成用のアルゴリズムを構築しようとしています。私はこの主題に関する多くの資料を読みましたが、ここにいくつかの結果があります:

ここでは、平面グラフを作成する関数をいくつか書きました...

プログラムを開始すると、次のように多数の平面グラフが生成されます。

これらのコードはすべて機能しますが、テスト中にグラフ (レベル) 24、36、... が平面ではないことがわかりました。

オイラーの公式について知っているので、オイラーの公式で頂点/エッジを生成しようとしましたが、ご覧のとおり、実際には機能していません。

Javaでエッジが交差することを許可せずに、ポイント間にできるだけ多くの直線エッジを持つグラフを作成しようとしています。基本的に、ランダムな量のポイントで平面グラフを作成しようとしています。すでにエッジがあるグラフが与えられたときに平面グラフを検出する方法をある程度理解していますが、ランダムなノードから平面グラフを実際に作成する方法について混乱しています。頭に浮かぶ唯一の方法は、グラフをランダムに作成してからテストすることですが、これは非常に非効率的です。

ありがとう

頂点間にエッジを追加するプログラムを作成しました。目標は、交差せずにできるだけ多くのエッジを追加することです (つまり、平面グラフ)。複雑さは何ですか？

試行: 深さ優先検索を使用したので、n がノードで m がエッジである O(n+m) だと思います。

また、エッジの数を n の関数としてプロットすると、どのように見えるでしょうか?

(* 前回誰も答えなかったので、質問を再投稿します *)

交差しない線のセットがあり、そのうちのいくつかは頂点で接続されています。特定の点を囲む最小の多角形が存在する場合、それを見つけようとしています。したがって、下の画像では、すべての線分のリストから、赤い点が指定されているため、青い線分のみを取得したいと考えています。私は Python を使用していますが、おそらく他の言語のアルゴリズムを適応させることができます。この問題が何と呼ばれているのかわかりません。

グラフを平面グラフにするアルゴリズムがあることを知りたいですか? Google で検索しましたが、役立つ情報が見つかりませんでした