2

我已经实现了 Graham 扫描，但我发现我的程序的瓶颈是排序（80% 的时间）。我想改进它，现在我正在做以下事情：

 std::sort(intersections.begin() + 1, intersections.end(), [&minElement](Point const& a, Point const& b)
 {return angle (minElement - a, XAxis) < angle (minElement - b,XAxis);});

这给了我确切的角度，但它并不便宜，因为我的角度函数如下所示：

float angle (const Point& v1, const Point& v2) {
    return dot (v1, v2) / (v1.Length () * v2.Length ());
}

在 Length 函数中，我必须做一个平方根，这是最昂贵的操作之一。但这样我得到了一个很好的订购。

我尝试按 Slope、dot、ccw 对数组进行排序，甚至只从比较中删除 sqrt，但这些都没有为我提供相同的排序。你能给我什么建议吗？

4

2 回答 2

3

当您按它们的相对角度对点进行排序时，您不需要知道两个点形成的确切角度。相反，您只需要知道一个点是在另一点的左侧还是在另一点的右侧。

以图像为例，您想比较两个点 (x 1 , y 1 ) 和 (x 2 , y 2 )，假设最底部的点在 (x p , y p )。查看两个向量 v 1 = (x 1 - x p , y 1 - y p ) 和 v 2 = (x 2 - x p , y 2 - y p )。要确定 v 1是在 v 2的左侧还是右侧，这意味着您要查看从 v 1到 v的角度的符号2 . 如果为正，则 v 2在 v 1的左侧，如果为负，则 v 1在 v 2的左侧。

2D 叉积具有很好的性质：

v 1 × v 2 = |v 1 | |v 2 | 罪（θ）

其中 θ 是从 v 1到 v 2所形成的角度。这意味着如果 v 1在 v 2的右侧，则 θ > 0 ，反之亦然，这很好，因为这可以让您通过取叉积来比较哪个去向！

换句话说：

  • 如果 v 1 × v 2 > 0，则 v 2在 v 1的左侧。
  • 如果 v 1 × v 2 = 0，则这些点是共线的。
  • 如果 v 1 × v 2 < 0，则 v 2在 v 1的右侧。

二维叉积公式由下式给出

(Δx 1 , Δy 1 ) × (Δx 2 , Δy 2 ) = (Δx 1 Δy 2 - Δx 2 Δy 1 )

其中，这里，Δx 1表示 x 1 - x p等。

因此，您可以计算上述数量，然后查看其符号以确定两点如何相互关联。不需要平方根！

于 2017-01-12T22:53:18.677 回答
0

您可以通过缓存进行临时优化。

首先，Length() 可以将其结果缓存在成员变量中。您只需要在点更改的情况下使该值无效（可能不是这种情况）。您可以进行惰性计算，因此 Length 将检查它是否有值，如果没有则计算/存储，然后返回存储的值。

其次，对于给定的 minElement 和 xAxis，角度 (minElement - a, XAxis)成为 1 个参数的函数，因此您可以在排序之前为每个点保存（缓存）它的值，并在准备好的值上使用比较器。

对这些事情的幼稚方法：在主算法中使用 Point 的子类，因此每个点都已经有必要的方法和缓存值的位置。

于 2017-01-13T10:47:00.833 回答