Алгоритъм за преместване на линия - Реализация за 1D равнина

Ето един подход, който можете да опитате (в C#. Не съм го тествал, така че моля, простете за правописни грешки и други подобни; просто вземете „идеята“/стратегията).

Производителността е 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).

Това е операция с линейно време.

Снабден с това модифицирано сливане, можете да приложите модифициран MergeSort, който започва с единични интервали и рекурсивно формира обединения. В крайна сметка получавате единичен списък с интервали, който ще ви даде искания размер.

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