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

return x2 >= y1 && x1 <= y2;

Answer 2

Ich nehme an, die Frage bezog sich auf den schnellsten, nicht auf den kürzesten Code. Die schnellste Version muss Verzweigungen vermeiden, also können wir etwas wie dieses schreiben:

für den einfachen Fall:

static inline bool check_ov1(int x1, int x2, int y1, int y2){
    // insetead of x1 < y2 && y1 < x2
    return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};

oder, für diesen Fall:

static inline bool check_ov2(int x1, int x2, int y1, int y2){
    // insetead of x1 <= y2 && y1 <= x2
    return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};

Answer 3

Wenn Sie es mit zwei Bereichen zu tun hätten [x1:x2] y [y1:y2] Die natürliche/antinatürliche Ordnung erstreckt sich dabei auf alle Bereiche:

• natürliche Ordnung: x1 <= x2 && y1 <= y2 o
• antinatürliche Ordnung: x1 >= x2 && y1 >= y2

dann können Sie dies zur Überprüfung verwenden:

*sie überschneiden sich <=> `(y2 - x1) (x2 - y1) >= 0`**

wo nur vier Operationen beteiligt sind:

• zwei Subtraktionen
• eine Multiplikation
• ein Vergleich

Answer 4

Gegeben: [x1,x2] [y1,y2] entonces x1 <= y2 || x2 >= y1 würde immer funktionieren. wie

      x1 ... x2
y1 .... y2

si x1 > y2 dann überschneiden sie sich nicht oder

x1 ... x2
    y1 ... y2

si x2 < y1 sie sich nicht überschneiden.

Answer 5

Falls jemand nach einem Einzeiler sucht, der die tatsächliche Überschneidung berechnet:

int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations

Wenn Sie ein paar weniger Operationen, aber ein paar mehr Variablen benötigen:

bool b1 = x2 <= y1;
bool b2 = y2 >= x1;
int overlap = ( !b1 || !b2 ) ? 0 : (y2 >= y1 && b1 ? y1 : y2) - ( x2 <= x1 && b2 ? x1 : x2) + 1; // max 9 operations