c - 优化一个简单的 pinball 求解器

Question

我正在尝试解决编程挑战，但只取得了部分成功；我需要优化解决方案 - 这就是你的用武之地。首先，参数:

• 给你一些线段int x1, y1, x2, y2 .
• 给你一个起点int px, py = INT_MAX为了你的球。
• 你要模拟一个球从px, py“掉落”直线向下(较小的 y 值)
  • 当它与一条线相交时，它会沿着这条线直到它的下端点
  • 当没有更多的线相交时，输出px .

所以，我认为:

• 将行读入行元组列表int xtop, ytop, xbot, ybot ,
• 按 ybot 对行进行排序.这允许我们跳过球已经通过的线，
• 轨道索引 imin这样 lines[i].ybot >= py对于所有 i < imin ，然后直到找不到相交:
  • 最大化垂直相交 yi = kx + m ,
  • 设置px, py = lines[i].{x, y}bot .

问题是这个时间复杂度 ∈ θ(n²) - IOW，对于大输入来说很糟糕。

一个想法是使用类似 k-d tree 的东西，但接下来的问题是计算哪些线进入哪些所谓的半空间是否会非常昂贵。

Answer 1

听起来您似乎对 point location in a planar subdivision 感兴趣.我链接到的 slab 分解方法是更简单的选择之一；简而言之，您从线段的每个端点延伸垂直线，形成 2n + 1 个垂直板。对于每个板，您计算一个二叉树，从上到下指示哪些段穿过板。然后，要找到球击中的位置，确定它在哪个板中，然后确定它击中了哪个部分(如果有的话)；两个操作都是 O(log n) 时间。

要首先计算二叉树，请使用扫描线算法。从一个空的二叉树开始，按照 x 坐标的排序顺序处理端点。对于左端点，将线段插入树中。对于右边，将其从树中移除。假设段不交叉，则永远不需要在树内重新排序。天真地，我们必须在每一步后复制树，但是将存储从 O(n^2) 降低到 O(n log n) 的一个简单策略是使用纯功能性红黑树，避免需要副本。

此方法的整体运行时间和空间为 O(n log n)。