我有一条std::list
线。每行是 2 个CPoint
对象的列表,标记一行的起点和终点
std::list<std::list<CPoint>> edges;
然后我有另一行(2 个 CPoints 的列表),我想测试它是否与主列表的任何行相交。我怎样才能做到这一点?可能是循环内的交叉测试以进行迭代。
我有一条std::list
线。每行是 2 个CPoint
对象的列表,标记一行的起点和终点
std::list<std::list<CPoint>> edges;
然后我有另一行(2 个 CPoints 的列表),我想测试它是否与主列表的任何行相交。我怎样才能做到这一点?可能是循环内的交叉测试以进行迭代。
正如您所建议的,一种基本方法是遍历所有线,然后应用线相交算法。渐近地,这可能是最好的;毕竟你的新线很可能与所有其他线相交。
在许多线相交算法中,我们首先应用边界框测试。非常粗略,确保包含被比较的两条线的矩形重叠。如果它们不重叠,则线不能相交,尽管如果它们进行更全面的测试,则需要应用。
边界框测试是看两个框的 x 间隔是否重叠,两个框的 y 间隔是否重叠。有专门为有效的区间交叉点检查而设计的数据结构。查看有关区间树的信息。在许多情况下,这样的结构意味着您将在更少的行上执行边界框测试;在需要应用测试之前丢弃一些行(通过它们的间隔)的数据结构。