1

我有一条std::list线。每行是 2 个CPoint对象的列表,标记一行的起点和终点

std::list<std::list<CPoint>> edges;

然后我有另一行(2 个 CPoints 的列表),我想测试它是否与主列表的任何行相交。我怎样才能做到这一点?可能是循环内的交叉测试以进行迭代。

4

1 回答 1

2

正如您所建议的,一种基本方法是遍历所有线,然后应用线相交算法。渐近地,这可能是最好的;毕竟你的新线很可能与所有其他线相交。

在许多线相交算法中,我们首先应用边界框测试。非常粗略,确保包含被比较的两条线的矩形重叠。如果它们不重叠,则线不能相交,尽管如果它们进行更全面的测试,则需要应用。

边界框测试是看两个框的 x 间隔是否重叠,两个框的 y 间隔是否重叠。有专门为有效的区间交叉点检查而设计的数据结构。查看有关区间树的信息。在许多情况下,这样的结构意味着您将在更少的行上执行边界框测试;在需要应用测试之前丢弃一些行(通过它们的间隔)的数据结构。

于 2013-01-19T11:42:52.300 回答