Überlappende Bereiche Überlappung prüfen

Question

Ich habe eine Liste von Bereichen und möchte herausfinden, ob sie sich überschneiden.

Ich habe den folgenden Code. Was scheint nicht zu funktionieren. Gibt es eine einfachere Möglichkeit, dies zu tun oder eine Möglichkeit, die funktioniert :)

Vielen Dank im Voraus für eine Beratung.

public partial class Form1 : Form 
{ 
    public Form1() 
    { 
     InitializeComponent(); 
    } 

    private IList<Range> rangeList; 

    private void Form1_Load(object sender, EventArgs e) 
    { 
     rangeList.Add(new Range{FromNumber = 0, ToNumber = 100}); 
     rangeList.Add(new Range { FromNumber = 101, ToNumber = 200 }); 

     // this range should over lap and throw an exception 
     rangeList.Add(new Range { FromNumber = 199, ToNumber = 300 }); 

    } 

    private bool RangesOverlap() 
    { 
     var bigList = new List<List<int>>(); 

     foreach (var range in this.rangeList) 
     { 
      bigList.Add(new List<int> { range.FromNumber , range.ToNumber }); 
     } 

     IEnumerable<IEnumerable<int>> lists = bigList; 

     return lists 
     .Where(c => c != null && c.Any()) 
     .Aggregate(Enumerable.Intersect) 
     .ToList().Count > 0; 
    } 
} 


public class Range 
{ 
    public int FromNumber { get; set; } 
    public int ToNumber { get; set; } 
} 

Answer 1

Erste Zahlen verschmelzen und dann generierte Liste überprüfen in sortierter Reihenfolge ist:

rangeList 
.OrderBy(p => p.FromNumber) 
.Select(p => new[] { p.FromNumber, p.ToNumber }) 
.SelectMany(p => p) 
.Aggregate((p, q) => q >= p ? q : int.MaxValue) == int.MaxValue 

Answer 2

Sie können Ihre neue Anforderung mit einer geringfügigen Änderung von RezaArabs erfüllen beantworten:

rangeList 
.Select(p => new[] { p.FromNumber, p.ToNumber }) 
.SelectMany(p => p.Distinct()) 
.Aggregate((p, q) => q >= p ? q : int.MaxValue) == int.MaxValue 

Answer 3

Die Lösung zu diesem Problem kann so einfach wie das Schreiben Ihrer eigenen RangeList : IList<Range>, deren Add()-Methode eine Ausnahme auslöst, wenn der angegebene Bereich mit einem oder mehreren überlappt Bereiche, die bereits in der Sammlung sind.

Arbeitsbeispiel:

class Range 
{ 
    public int FromNumber { get; set; } 
    public int ToNumber { get; set; } 

    public bool Intersects(Range range) 
    { 
     if (this.FromNumber <= range.ToNumber) 
     { 
      return (this.ToNumber >= range.FromNumber); 
     } 
     else if (this.ToNumber >= range.FromNumber) 
     { 
      return (this.FromNumber <= range.ToNumber); 
     } 

     return false; 
    } 
} 

class RangeList : IList<Range> 
{ 
    private readonly IList<Range> innerList; 

    #region Constructors 

    public RangeList() 
    { 
     this.innerList = new List<Range>(); 
    } 

    public RangeList(int capacity) 
    { 
     this.innerList = new List<Range>(capacity); 
    } 

    public RangeList(IEnumerable<Range> collection) 
    { 
     if (collection == null) 
      throw new ArgumentNullException("collection"); 

     var overlap = from left in collection 
         from right in collection.SkipWhile(right => left != right) 
         where left != right 
         select left.Intersects(right); 

     if (overlap.SkipWhile(value => value == false).Any()) 
      throw new ArgumentOutOfRangeException("collection", "The specified collection contains overlapping ranges."); 

     this.innerList = new List<Range>(collection); 
    } 

    #endregion 

    private bool IsUniqueRange(Range range) 
    { 
     if (range == null) 
      throw new ArgumentNullException("range"); 

     return !(this.innerList.Any(range.Intersects)); 
    } 

    private Range EnsureUniqueRange(Range range) 
    { 
     if (!IsUniqueRange(range)) 
     { 
      throw new ArgumentOutOfRangeException("range", "The specified range overlaps with one or more other ranges in this collection."); 
     } 

     return range; 
    } 

    public Range this[int index] 
    { 
     get 
     { 
      return this.innerList[index]; 
     } 
     set 
     { 
      this.innerList[index] = EnsureUniqueRange(value); 
     } 
    } 

    public void Insert(int index, Range item) 
    { 
     this.innerList.Insert(index, EnsureUniqueRange(item)); 
    } 

    public void Add(Range item) 
    { 
     this.innerList.Add(EnsureUniqueRange(item)); 
    } 

    #region Remaining implementation details 

    public int IndexOf(Range item) 
    { 
     return this.innerList.IndexOf(item); 
    } 

    public void RemoveAt(int index) 
    { 
     this.innerList.RemoveAt(index); 
    } 

    public void Clear() 
    { 
     this.innerList.Clear(); 
    } 

    public bool Contains(Range item) 
    { 
     return this.innerList.Contains(item); 
    } 

    public void CopyTo(Range[] array, int arrayIndex) 
    { 
     this.innerList.CopyTo(array, arrayIndex); 
    } 

    public int Count 
    { 
     get { return this.innerList.Count; } 
    } 

    public bool IsReadOnly 
    { 
     get { return this.innerList.IsReadOnly; } 
    } 

    public bool Remove(Range item) 
    { 
     return this.innerList.Remove(item); 
    } 

    public IEnumerator<Range> GetEnumerator() 
    { 
     return this.innerList.GetEnumerator(); 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return this.innerList.GetEnumerator(); 
    } 

    #endregion 
} 

Verbrauch:

IList<Range> rangeList = new RangeList(); 

try 
{ 
    rangeList.Add(new Range { FromNumber = 12, ToNumber = 12 }); 
    rangeList.Add(new Range { FromNumber = 13, ToNumber = 20 }); // should NOT overlap 
    rangeList.Add(new Range { FromNumber = 12, ToNumber = 20 }); // should overlap 
} 
catch (ArgumentOutOfRangeException exception) 
{ 
    Console.WriteLine(exception.Message); 
} 

Answer 4

In der Vergangenheit habe ich eine Herausforderung, wo ich hatte eine Validierung Algorithmus für Bereiche zu schreiben, die vom Benutzer erstellt werden (ganze Zahlen oder reellen Zahlen). Ich hatte 3 Dinge zu überprüfen:

1. Bereiche kontinuierlich sind
2. Bereiche überlappend sind nicht
3. LOW-Wert muss immer < sein = als HOCH

So kam ich mit dem folgenden PHP-Algorithmus nach oben .

//Let's hardcode an array of integers (it can be of reals as well): 
$range = array 
(
    array(1, 13), 
    array(14, 20), 
    array(21, 45), 
    array(46, 50), 
    array(51, 60) 
); 

//And the validation algorithm: 
$j = 0; 
$rows = sizeof($range); 
$step = 1; // This indicates the step of the values. 
       // 1 for integers, 0.1 or 0.01 for reals 

for ($x=0; $x<$rows; $x++) 
    for ($y=0; $y<$rows; $y++) { 
     if (($range[$x][0] <= $range[$y][0]) AND ($range[$y][0] <= $range[$x][1]) AND ($x != $y)) { 
      echo "Ranges intercepting"; // replace with error handling code 
      break 3; 
     } 
     if ($range[$x][0] > $range[$x][1]) { 
      echo "Not valid high & low"; // replace with error handling code 
      break 3; 
     } 
     if ($range[$x][0] - $range[$y][1] == $step) { 
      $j++; 
     } 
    } 
if ($j != $rows - $step) 
    echo "Not continuous"; // replace with error handling code 

Wir durchlaufen die Bereiche und vergleichen sie paarweise. Für jedes Paar wir:

1. überlappende Bereiche finden und einen Fehler
2. finden starten & Endpunkte in umgekehrter Richtung erhöhen und einen Fehler

Wenn keine der oben genannten erhöhen auftritt, zählen wir den Unterschied von Ende - Startpunkte. Diese Zahl muss gleich der Anzahl der Bereiche minus Schritt (1, 0,1, 0,01 usw.) sein. Ansonsten melden wir einen Fehler.

Hoffe, das hilft!