3

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

谢谢

在此处输入图像描述

4

1 回答 1

2

一旦你有了第一个交点,剩下的就很容易了。

准备一个边数据库:对于每条边,列出它所属的两个多边形,或者说它是外边(因此只属于一个多边形)。在您的图片中,矩形的下侧将包含 4 个不同多边形的 4 条边。

画出你的线,找到你的第一个交点(图片中的[0, 0.25],没有圈出)。假设它是多边形 A。那么下一个交点(图中圈出的最低点)也属于 A。您可以通过 A 的边列表通过二分搜索找到相关边。

现在你已经找到了 A 的第二条边,找出它属于哪个多边形。然后使用二分搜索来查找该线与该其他多边形的哪一条边相交。依此类推,直到您退出矩形。

于 2013-05-03T20:38:07.550 回答