沃罗诺伊图与直线的交点

Question

3

是否有一种计算效率高的方法来确定直线与给定 Voronoi 分割中矩形平面区域内所有边的交点？

谢谢。

enter image description here

- branden_burger

请参考MathOverflow上的答案，这些答案表明，在某些“计算效率”解释下，答案是否定的。 - Joseph O'Rourke

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- n. m. · Accepted Answer

一旦你有了第一个交点，其余的就容易了。

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

画出你的线，在第一个交点处找到它（在你的图片中是 [0, 0.25]，未被圈出来）。假设它属于多边形 A。那么第二个交点（在你的图片中最低的被圈出来的）也属于 A。通过在 A 的边界列表上进行二进制搜索，你可以找到相关的边。

现在你已经找到了 A 的第二条边，接下来要找出它属于哪个其他多边形。然后使用二分查找找到线与那个多边形的另一条边相交的位置。一直这样找，直到退出矩形。