python - PyGameでグラフのアウトラインをポリゴンとして取得する

Question

これは不可能（または少なくとも非常に複雑）だと感じていますが、現在、次のようなグラフが生成されています（ひどいペイントスキルを失礼します）。

ここで、アウトラインのポリゴンを作成できるようにしたいと思います。すべてのノードの座標はありますが、交差点はありません。私がこれまでに管理できる最善の方法は、ギフトラッピングアルゴリズムです。これは、他の何よりもポリゴンの大まかな輪郭を提供します。

誰かが私がこれについてどうやって行くことができるかについて何か考えを持っていますか？

（私は現在PyGameを使用しています）

Answer 1

交差点が発生する場所を把握し、そこに新しいノードを作成する必要があります。

次に、外側のポリゴン上にあるエッジを見つけます。無限遠からエッジに当たるまでランダムな光線を実行することをお勧めします。

次に、左手を境界に、右手を外側に保ちながら、その端に沿って歩くことを想像してみてください。歩き始めます。

ノードにぶつかると、エッジを越えないように向きを変えます。つまり、反時計回りの順序で次のエッジをトラバースし始めます。（これの簡単な実装は、atan2（）を使用して、方向でそれらをソートすることです。）

それはすべて基本的な高校の代数と三角法ですが、これがこの種の何かをプログラミングするのが初めての場合は少し難しいかもしれません。しかし、あなたはたくさん学ぶでしょう。