扫描线算法 - 一维平面的实现

Question

问题很简单，平面上有一些给定的一维直线。我们需要找到至少有一行的 space 的总大小。

让我用一个例子来讨论这个问题-

这可能是个案例。或者

这可能是一个案例或类似的案例。

我知道这是Sweep Line Algorithm的基本问题。

但是网上没有合适的文档可以让它正确理解。

我最好的一个是 Top Coder 的博客，那就是 here.

但不清楚如何实现或模拟如何。

如果我愿意，我们可以用 2 个循环在 O(n^2) 中完成，但我不知道该过程是怎样的。

或者有比 O(n log n) 更好的算法吗？

任何人都可以通过分享任何 Sudo 代码或模拟来帮助我吗？

如果 Sudo 代码或示例代码不可用，从我可以实现的地方模拟理解就足够了。

Re- Problem calculating overlapping date ranges 不是我要找的，因为首先，它是 O(n^2) 和所以，这不是我想要的。而且像这个问题描述的不完整

Answer 1

没有太多关于此主题的信息。

所以，我正在与您分享我为您创建的算法和模拟，它也与 O(n log n) !!!!!

开始吧-

创建所有行动点的优先级列表（行动点是一条线的起点或终点）。 PQ 的每一项都有 3 个元素（当前点、开始或结束、来自哪一行）。（O(n log n) 操作，如果我们使用 Quick Short 进行排序。
初始化用于存储当前活动行的 Vector。
初始化一个数组，大小 = 行数 + 1（用于存储影子长度之和）。

现在从 PQ 中删除一个项目，然后运行针对该项目的特定操作，如下图所示，您就完成了。

0

1

2

3

4

5

6

7

8

9

10

11

直到 PQ 为空。

在你的例子中，找到数组从 1 到末尾（索引号 1 到 m）的所有元素的总和，这就是你的答案。

但是使用这个算法和数组，你可以很容易地得到许多更复杂的问题答案，比如 space 的长度是多少，有 3 个影子 = Arr3 等等。

现在的问题是订单是什么，对吧？

因此，排序 = O(n log n) 和清扫 = O(m) [m=行动点数，所以 m

因此，总阶数 = O(n log n) + O(m) = O(n log n)

认为您可以轻松理解它，这将对您和其他许多人有很大帮助。并认为您将能够轻松实现它。

Answer 2

制作一个 array/list 结构，包含段终点坐标 X 和 +1 属性作为起点，-1 属性作为终点 A。 O(N)

按 X 键对数组进行排序。 O(NlogN)

初始化CurrCount为零，运行通过数组，给CurrCount添加A属性。 O(N)

您将获得 CurrCount 大于零（覆盖）和 CurrCount 为零（未覆盖）的范围

Answer 3

这是您可以尝试的一种方法（在 C# 中。我没有测试过，所以请原谅拼写错误等；只需采用 "idea"/策略）。

性能为 O(N log m)，其中 m 是您将创建的不相交 "shadows" 的数量。所以，最坏的情况（如果所有线段相对于它们的阴影都是不相交的）你会有 O(N logN)，但是当你只有很少的阴影时，它基本上是 O(N)。

  public class LineSegment
  {
    public int Begin;
    public int End;
    // assumed to INCLUDE Begin but EXCLUDE End, so that
    // length = End-Begin

    public LineSegment Clone()
    {
      LineSegment clone = new LineSegment();
      clone.Begin=this.Begin;
      clone.End = this.End;
      return clone;
    }
  }

public int TotalShadow(LineSegment[] segments)
{
  // Class LineSegment has int members Begin and End, and Clone method to create a (shallow) Copy.
  // Can/should be adapted if we're dealing with LineSegments with double/float coordinates.

  // Easy special cases: no segements at all, or precisely one.
  int N = segments.Length;
  if (N == 0)
    return 0;
  else if (N == 1)
    return (segments[0].End - segments[0].Begin);

  // build a list of disjoint "shadows", cast onto the x-axis by all line segments together,
  // sorted by their "Begin" (leftmost coordinate).
  List<LineSegment> shadows = new List<LineSegment>();
  // Initialize with the first segment, for convenient iteration below.
  shadows.Add(segments[0].Clone());

  for (int k = 1; k < N; ++k) // start at #1: we handled #0 already.
  {
    // find its position (Begin) in relation to the existing shadows (binary search).
    int xBegin = segments[k].Begin;

    int jLow = 0;
    int xLow = shadows[jLow].Begin;

    int jHigh, xHigh;
    if (xBegin <= xLow)
      jHigh = jLow; // avoid any more binary searching below
    else
    {
      jHigh = shadows.Count - 1;
      xHigh = shadows[jHigh].Begin;
      if (xBegin >= xHigh)
        jLow = jHigh; // avoid any more binary searching below
    }

    while (jHigh - jLow > 1)
    {
      int jTry = (jLow + jHigh) / 2;
      int xTry = shadows[jTry].Begin;

      if (xTry <= xBegin)
        jLow = jTry;
      else
        jHigh = jTry;
    }

    // If it starts BEFORE "low" we create a new one: insert at jLow;
    // Elseif x falls INSIDE "low", we merge it with low;
    // ELSE we create a new shadow "between" low and high (as regards Begin)
    // In all cases we'll make sure jLow points to the applicable shadow (new or existing).
    // Next we'll check whether it overlaps with adjacent higher-lying shadows; if so: merge.
    if (xBegin < shadows[jLow].Begin)
      shadows.Insert(jLow, segments[k].Clone()); // jLow now points to the inserted item
    else if (xBegin <= shadows[jLow].End)
    { // merge: extend existing low if applicable.
      if (segments[k].End > shadows[jLow].End)
        shadows[jLow].End = segments[k].End;
    }
    else // if (xBegin > shadows[jLow].End)
      shadows.Insert(++jLow, segments[k].Clone()); // jLow increased to point to the inserted item.

   // Try to merge, starting at the next higher lying shadow.
    jHigh = jLow + 1;
    while (jHigh < N && shadows[jLow].End >= shadows[jHigh].Begin)
      jHigh++; // jHigh will point to the first one that we do NOT merge with.

    if (jHigh > jLow + 1) // any merges?
    {
      if (shadows[jHigh - 1].End > shadows[jLow].End)
        shadows[jLow].End = shadows[jHigh - 1].End; // set the appropriate End.

      for (int jRemove = jHigh - 1; jRemove > jLow; --jRemove)
        shadows.RemoveAt(jRemove); // Remove all shadaow-entries that we've merged with.
    }
  }

  // Wrap up.
  int shadowTotal = 0;
  foreach (LineSegment shadow in shadows)
    shadowTotal += (shadow.End - shadow.Begin);

  return shadowTotal;
}

Answer 4

这不是很复杂。

形成一个数组，在其中放置所有区间端点横坐标，并带有一个标志，指示它是起点还是终点。

对数组进行递增排序。

然后在更新计数器的同时扫描数组：起点增加，终点减少。

请求的大小很容易从计数器从零切换到非零以及相反切换的值中找到。

我认为由于排序（我认为无法避免），不可能让它比 O(N Log(N)) 更快，除非数据允许线性时间排序（比如直方图排序）。

Answer 5

也许你可以做得比盲排序稍微好一些，使用以下方案，派生自 MergeSort：

假设您有两个非重叠间隔列表，按递增界限排序；
像 MergeSort 一样执行合并步骤（总是移动到每个列表的最近边界），以计算区间的并集；
根据两个列表中索引的奇偶校验，您可以判断要发出的边界（f.i。将 AB 和 CDEF 与排序的 ACBDEF 合并，输出将是 ADEF） .

这是线性时间操作。

配备此修改后的合并，您可以实现修改后的 MergeSort，它以单个间隔开始并递归地形成联合。最后，您会得到一个间隔列表，它将为您提供请求的大小。

在最坏的情况下，没有绑定会消失，进程仍然存在O(N Log(N))。但是当出现足够多的区间并集时，区间的数量会减少，处理时间可以下降到线性 O(N).

扫描线算法 - 一维平面的实现

Sweep Line Algorithm - Implementation for 1D plane

algorithm

sorting

simulation

implementation

mark-and-sweep