voronoi圖與一條線的交點

Question

是否有一種計算有效的方法來確定直線與矩形平面區域中給定Voronoi鑲嵌的所有邊緣的交點？

感謝

Answer 1

一旦你有你的第一個交叉點，其餘的是容易的。

準備邊的數據庫：對於每個邊，列出它所屬的多邊形，或者說它是外邊（僅屬於一個多邊形）。在你的圖片中，矩形的下邊將包含4個不同多邊形的4條邊。

畫出你的線條，找到你的第一個交點（圖片中的[0,0.25]，不是圓圈）。假設它是多邊形A.然後下一個交點（圖片中圈出的最低點）也屬於A.您可以通過A的邊緣列表查找相關邊緣。

現在您已經找到A的第二個邊，找出它屬於哪個多邊形。然後使用二分查找找出該線相交的另一個多邊形的哪個邊。等到你退出你的矩形。