Алгоритм Sweep Line — Реализация для 1D-плоскости

Вот подход, который вы можете попробовать (на С#. Я не тестировал его, поэтому, пожалуйста, простите опечатки и тому подобное; просто возьмите "идею"/стратегию).

Производительность равна O(N log m), где m — количество непересекающихся «теней», которые вы создадите. Таким образом, в худшем случае (если ВСЕ сегменты линий не пересекаются по отношению к их теням) у вас будет 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;
}

Создайте массив/список структур, содержащих координату конечной точки сегмента X и атрибут +1 для начальной точки и атрибут -1 для конечной точки A. НА)

Сортировать массив по ключу X. O(NlogN)

Инициализируем CurrCount до нуля, прогоняем массив, добавляя атрибут A к CurrCount. НА)

Вы получите диапазоны, в которых CurrCount больше нуля (покрытые) и где CurrCount равно нулю (не покрытые).

Это не очень сложно.

Сформируйте массив, в который вы поместите все абсциссы конечной точки интервала с флагом, указывающим, является ли это начальной или конечной точкой.

Отсортируйте массив по возрастанию.

Затем сканируйте массив при обновлении счетчика: начальная точка увеличивает его, конечная точка уменьшает его.

Запрошенный размер легко найти по значениям, при которых счетчик переключается с нуля на ненулевое значение и наоборот.

Я не думаю, что это возможно сделать быстрее, чем O (N Log (N)) из-за сортировки (которой, я не думаю, можно избежать), если только данные не допускают сортировку по линейному времени (например, сортировка гистограммы ).

Может быть, вы можете добиться большего успеха, чем при слепой сортировке, со следующей схемой, полученной из MergeSort:

• предположим, что у вас есть два списка непересекающихся интервалов, отсортированных по возрастанию границ;

• выполнить шаг слияния, как в MergeSort (всегда переходить к ближайшей границе из каждого списка), чтобы вычислить объединение интервалов;

• основываясь на четности индексов из обоих списков, вы можете сказать, какие границы выдавать (например, объединение AB и CDEF с упорядочением ACBDEF, выход будет ADEF).

Это операция с линейным временем.

Используя это модифицированное слияние, вы можете реализовать модифицированную сортировку слиянием, которая начинается с одиночных интервалов и рекурсивно формирует объединения. В итоге вы получите единый список интервалов, который даст вам запрошенный размер.

В худшем случае ни одна граница не исчезнет, ​​и процесс останется O(N Log(N)). Но когда возникает достаточно много интервальных объединений, количество интервалов уменьшается, и время обработки может снизиться до линейного O(N).