voronoi图与一条线的交点

Question

是否有一种计算有效的方法来确定直线与矩形平面区域中给定Voronoi镶嵌的所有边缘的交点？

感谢

Answer 1

一旦你有你的第一个交叉点，其余的是容易的。

准备边的数据库：对于每个边，列出它所属的多边形，或者说它是外边（仅属于一个多边形）。在你的图片中，矩形的下边将包含4个不同多边形的4条边。

画出你的线条，找到你的第一个交点（图片中的[0,0.25]，不是圆圈）。假设它是多边形A.然后下一个交点（图片中圈出的最低点）也属于A.您可以通过A的边缘列表查找相关边缘。

现在您已经找到A的第二个边，找出它属于哪个多边形。然后使用二分查找找出该线相交的另一个多边形的哪个边。等到你退出你的矩形。