c++ - 对二维线对执行操作的最佳方法是什么？

Question

所以我在 2d 平面上定义了 10 000 条线，因此每条线都显示为 (A1, A2, B1, B2)(A，B 点)。我有一系列函数需要在每对线上执行:

Angle(A,B)
    return Atan((B.y-A.y) / (B.x-A.x)) 

NearlyParallel(angle1, angle2)
    delta = Abs(angle1-angle2)
    return (delta < threshold) or (delta > Pi-threshold)

Collinear(A,B, C,D)
    return NearlyParallel(Angle(A,C), Angle(B,D)) and NearlyParallel(Angle(A,D), Angle(B,C))

所以通常我需要说明每条线哪条线与哪条线共线，哪条线几乎平行于另一条线。

我需要使用 boost 和所需的任何开源库在 C++ 中完成此操作。我是在 visual studio 2010 的 windows 下做的。

哪个库及其部分可以帮助我为我的数据组织快速计算？例如 boost graph lib 会有帮助吗？我的意思是通常我需要执行一些线程/处理器优化以加快速度。而且我不会有任何花哨的视频卡来执行所有...

Answer 1

您可以在每一行上使用 Angle 函数并将结果存储在 std::map 中，使用角度作为键。这将使具有相似角度的线靠近在一起，因此您可以快速选择对来测试 NearlyParallel 和 Collinear。