立即在頂點左邊的邊緣

Question

我想知道如何通過使用幾何學知道「立即在頂點左邊的邊緣」？

這是顯示問題的image。

例如，我怎麼能知道邊e5直接離開頂點e4。 或者直接離開頂點v14的邊是e9。

Answer 1

您可以保留segment tree結構中的邊 - 按Y座標排序。因此，可以找到邊緣（快速），即來自頂點的左射線將相交，並選擇最近的交點。