Wie kann man am effizientesten prüfen, ob sich zwei Bereiche überschneiden?

Question

Gegeben sind zwei umfassende Bereiche [x1:x2] und [y1:y2], wobei x1 x2 y y1 y2 Wie lässt sich am effizientesten prüfen, ob es Überschneidungen zwischen den beiden Bereichen gibt?

Eine einfache Umsetzung sieht wie folgt aus:

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

Aber ich gehe davon aus, dass es effizientere Wege gibt, dies zu berechnen.

Welche Methode wäre die effizienteste, weil sie die wenigsten Arbeitsschritte erfordert?

Answer 1

Was bedeutet es, wenn sich die Bereiche überschneiden? Es bedeutet, dass es eine Zahl C gibt, die in beiden Bereichen liegt, d. h.

x1 <= C <= x2

et

y1 <= C <= y2

Um Verwirrung zu vermeiden, sollten die Bereiche wie folgt aussehen: [x1:x2] und [y1:y2]

Wenn wir nun annehmen dürfen, dass die Bereiche wohlgeformt sind (so dass x1 <= x2 und y1 <= y2), dann ist es ausreichend, zu prüfen

x1 <= y2 && y1 <= x2

または

(StartA <= EndB) und (EndA >= StartB)

Answer 2

Gegeben sind zwei Bereiche [x1,x2], [y1,y2]

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)

Answer 3

Das kann ein normales menschliches Gehirn leicht verwirren, daher habe ich festgestellt, dass ein visueller Ansatz leichter zu verstehen ist:

le Erläuterung

Wenn zwei Bereiche "zu fett" in einen Schlitz passt, der genau der Summe der Breite beider entspricht, dann überlappen sie sich.

Für Bereiche [a1, a2] y [b1, b2] wäre dies:

/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
  // too fat -- they overlap!
}

Answer 4

Tolle Antwort von Simon aber für mich war es einfacher, über den umgekehrten Fall nachzudenken.

Wann überschneiden sich 2 Bereiche nicht? Sie überschneiden sich nicht, wenn einer der beiden Bereiche nach dem anderen beginnt:

dont_overlap = x2 < y1 || x1 > y2

Jetzt ist es leicht auszudrücken, wann sie sich überschneiden:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)

Answer 5

Die Subtraktion des Minimums an den Enden der Bereiche vom Maximum am Anfang scheint den Zweck zu erfüllen. Wenn das Ergebnis kleiner oder gleich Null ist, liegt eine Überschneidung vor. Dies veranschaulicht es gut: