11

我对这个算法问题有疑问；我将粘贴问题，然后回顾一下我目前的想法和解决方案。

有N (up to 100,000)线段定义为[(x1, y1), (x2, y2)]，其中x1 < x2和y1 < y2（例如，线段具有正斜率）。没有线段接触或相交，即使在端点处也是如此。第一段有(x1, y1) = (0, 0). 将每个部分想象成一个人必须攀登的二维小山。

一个人从第一座山丘开始(0, 0)并降落。每当一个人降落在山上时，他都会爬到尽头，(x2, y2)然后直接向下跳。如果他降落在另一座山上（路段上的任何地方），该过程将继续：他爬上那座山并跳跃。如果没有更多的山丘，他就会跌倒-INFINITY，这个过程就结束了。每个小山(x1, y1) -> (x2, y2)都应该被看成是含点(x1, y1)而不是含点(x2, y2)，这样人从上面的一个位置跌到山上就着地，从上面x = x1跌到山上就不会着地。以上在x = x2。

目标是计算他接触了多少座山。

我现在的想法

我正在考虑沿 x 轴在平面上扫一条线。每个段由一个 BEGIN 和 END 事件组成；每次遇到线段的开头，我们将它添加到一个集合中。每次遇到线段的结尾时，我们都会将其从集合中删除。当我们到达当前山的终点时，我们应该检查我们可以登陆的最高山的集合。但是，我不知道如何确定如何快速检查，因为集合内可能有 N 个条目。另外，跳到另一座山后，这些顺序会改变，因为每个段的坡度可能不同，我不知道如何解释这种差异。

有什么想法吗？

4

4 回答 4

1

巴伦，你的算法是完全正确的。排序列表中元素的顺序不会随着扫描线的移动而改变，因为如果发生这种情况，您将拥有线段的交点。

您只需要一种方法来跟踪已排序的线段。做到这一点的一种方法是保留线段图，其中比较运算符通过线段上的 y 值比较线段，该线段由当前扫描位置的当前 x 值计算得出。从此映射中插入、删除和查询是 O(log(n))。

于 2014-05-23T09:02:40.997 回答
1

在预处理中，您可以遍历所有线段并在 stl multimap<pair,linesegment> 或类似的东西中添加点。这种预处理的成本将是 O(NlogN)。然后你可以继续你的扫线方法。您需要从多图迭代点。因为所有点都是排序的，并且包含对点对应的线的引用，所以它将花费 O(N)。

于 2014-03-19T05:14:16.293 回答
0

我认为线扫描算法在这里是个好主意。让我总结一下到目前为止的算法并添加我的改进：

  • 您正在从左到右扫过一条线。
  • 您有一个活动列表，其中列出了所有当前活动的段。这些是与扫描线相交的线段
  • 每个线段的每个端点都被认为是一个“事件”
  • 当线扫过段的“开始”时，该段被添加到活动段列表中
  • 当线扫过段的“末端”时，该段将从活动段列表中删除
  • 如果在移除线段时活动集中没有线段，则该过程结束
  • 如果移除一条线段后激活集中有线段，我们需要确定
    • A) 活动集中是否有任何线段的部分“低于”先前移除的端顶点，以及
    • B）该人将降落在这些线段中的哪一个。

这个想法是对“活动集”中的线段进行排序，以便此查询有效。我在想的是，如果我们知道一条线的斜率和 y 截距，我们可以计算起始顶点 x 位置的交点

GreaterThan(segment1,segment2){ // is segment 1 higher than segment 2?
//y = mx + b; compute y value of point on segment 2 for a given x value from s1
//that is, m and b are slope and y-intercept of s2
yVal = m * (segment1.first.x) + b
if (yVal < segment1.first.y)
   return true //the point on s2 corresponding to s1.first is lower than s1.first
return false
}

因为线不相交，所以你可以假设没有其他线会“穿过”这条线。

如果我们避免添加任何开始顶点高于我们“人”当前行的结束顶点的线段，那么我们应该成功地避免将任何无关的线段添加到活动集中（即线段“高于”我们当前的线段）

现在我们只需要担心最后一条线段的顶点不是“可着陆”的特殊情况。因为顶点是事件，所以我们将在进行分段测试之前处理所有事件。这样，您不会意外地落在活动集中线的末端顶点，而是会落在刚刚添加的线段上。

现在我们在活动集中有一个线段的排序列表，我们可以在恒定时间内查询它以获得顶部的线段，并且添加一个新的线段应该只需要对数时间。

这听起来如何？

于 2013-03-09T03:25:40.443 回答
0

这是 Haskell 的粗略方向。“段”是线段。（在此示例中，第三段略高于第二段以测试代码。）“匹配”查找将最后一段顶部 pt (x0,y0) 置于其 x 范围内的山/段并且大于或等于对应于 x0 的仿射变换的 y（“仿射”计算段的仿射函数 - 可以说是 ax+b）。最后，countHills 测试下一个山丘的可能匹配项，并选择 y 与 y0 最接近的那个（由仿射 a*x0+b 计算），并输出结果，按顺序累积爬上的山丘。显然，这个想法可能需要针对更长的段列表进行优化。

下面的结果输出显示了第一段和第三段。第二个山/段不在结果中，因为它低于第三个 - 我们落在第三个上：

*Main> countHills 段
[((0.0,0.0),(2.0,5.0)),((1.0,1.5 ),(5.0,3.0))]

import Data.List

segments = [((0,0),(2,5)),((1,1),(5,2)),((1,1.5),(5,3))]

top segment = snd segment

matches pt = 
  let x0 = fst pt 
      y0 = snd pt
  in filter (\x -> x0 >= fst (fst x) 
                   && x0 < fst (snd x) 
                   && (affine x) x0 <= y0) segments  

affine segment = 
  let x1 = fst $ fst segment
      y1 = snd $ fst segment
      x2 = fst $ snd segment
      y2 = snd $ snd segment
  in (+ ((x1*y2-x2*y1) / (x1-x2))) . (* ((y2-y1) / (x2-x1)))

countHills segments = countHills' (head segments) [] where
  countHills' x result = 
    let hills = matches $ top x
        x0 = fst (top x)
        y0 = snd (top x)
    in if null hills 
          then result ++ [x]
          else let nextHill = 
                     minimumBy (\a b -> compare 
                                        (y0 - (affine a) x0) 
                                        (y0 - (affine b) x0)) hills
               in countHills' nextHill (result ++ [x])
于 2013-03-09T04:10:51.800 回答