sorting - 同じ頂点を共有する一連の線を時計回りに並べ替える方法

Question

三角測量を二重接続エッジ リスト構造に格納しようとしていますが、1 つのステップで立ち往生しています。

私の質問:すべて同じテールを共有するハーフエッジのリストを時計回りに並べ替えるにはどうすればよいですか?

このデータ構造に慣れていない人へ: 1 つの頂点を共有するすべての線のリストを時計回りに並べ替えるにはどうすればよいですか?

ありがとうございました！

Answer 1

頂点に対して時計回りを意味すると仮定すると、実際には接線で並べ替えたいだけです。特定の言語を指定していないため、ライン内のポイントを参照する何らかの方法があると仮定すると、Python では次のようになります。

vertices = [[(1,2),(3,4)]...] # Some vertices assuming (1,2) is common vertex
sorting = lambda vector: math.atan(vector[1][1] / vector[1][0])
sorted_list = sorted(vertices, key=sorting)

反時計回りに切り替えたい場合は、reverse パラメータもあります。