Szybkie przecięcie prostokąta do prostokąta

81

Jaki jest szybki sposób sprawdzenia, czy przecinają się 2 prostokąty?


Wyszukiwarka w Internecie wymyśliła ten jeden wiersz (WOOT!), Ale nie rozumiem, jak napisać go w Javascript, wydaje się, że jest napisany w starożytnej formie C ++.

struct
{
    LONG    left;
    LONG    top;
    LONG    right;
    LONG    bottom;
} RECT; 

bool IntersectRect(const RECT * r1, const RECT * r2)
{
    return ! ( r2->left > r1->right
        || r2->right < r1->left
        || r2->top > r1->bottom
        || r2->bottom < r1->top
        );
}
Robin Rodricks
źródło
5
Myślę, że popełniłeś literówkę w kopiowaniu / wklejaniu
fmark
5
Oryginalny artykuł zawiera literówkę. r2->right leftnie ma sensu. Może być uszkodzony z powodu problemów z ucieczką HTML.
Marcelo Cantos
42
Jestem ciekawy, jak myślisz, jak wyglądałby powyższy kod w „nowoczesnej” formie C ++.
jamesdlin
3
Jestem pewien, że brakujące znaki to <symbole ze względu na ucieczkę HTML.
devios1
1
@jamesdlin uczyniłbyś funkcję jako funkcję składową struktury, przyjmując jeden parametr. Po drugie, normalnie używałbyś const & zamiast const *. Możesz użyć szablonów, aby mieć zarówno wersje int, long, jak i double, zamiast używać makra Win32 ... (To również nie kompiluje się, ponieważ RECT kończy się wystąpieniem nienazwanej struktury, a nie nazwą typu). Przykład : ideone.com/bnzwl3
Sebastian Wahl

Odpowiedzi:

142

W ten sposób ten kod można przetłumaczyć na JavaScript. Zwróć uwagę, że w kodzie i artykule jest literówka, zgodnie z sugestią komentarzy. W szczególności r2->right leftpowinno r2->right < r1->lefti r2->bottom toppowinno być, r2->bottom < r1->topaby funkcja działała.

function intersectRect(r1, r2) {
  return !(r2.left > r1.right || 
           r2.right < r1.left || 
           r2.top > r1.bottom ||
           r2.bottom < r1.top);
}

Przypadek testowy:

var rectA = {
  left:   10,
  top:    10,
  right:  30,
  bottom: 30
};

var rectB = {
  left:   20,
  top:    20,
  right:  50,
  bottom: 50
};

var rectC = {
  left:   70,
  top:    70,
  right:  90,
  bottom: 90
};

intersectRect(rectA, rectB);  // returns true
intersectRect(rectA, rectC);  // returns false
Daniel Vassallo
źródło
Aby dodać / potwierdzić - testujemy trzy pudełka o wymiarach 20 x 20 pikseli, z wyjątkiem rectB, które ma 30 pikseli x 30 pikseli
verenion
6
jeśli r1 i r2 są identyczne, funkcja intersectRect zwróci wartość false
zumalifeguard
Fantastyczna, elokwentna implementacja. Kocham to! +1, działało idealnie w mojej grze.
Unome
1
@zumalifeguard Dlaczego tak myślisz?
Minix
Ta funkcja jest genialna. Nigdy bym o tym nie pomyślał, zamiast tego próbowałbym sprawić, by oba pudełka się przecinały.
nikk wong,
69
function intersect(a, b) {
  return (a.left <= b.right &&
          b.left <= a.right &&
          a.top <= b.bottom &&
          b.top <= a.bottom)
}

Zakłada się, że topzwykle jest mniejsze niż bottom(tj. Że ywspółrzędne rosną w dół).

DS.
źródło
Dobre i działające rozwiązanie, ale powinno być nieco wolniejsze, ponieważ wszystkie warunki muszą zostać ocenione. Drugie rozwiązanie jest wykonywane, gdy tylko jeden z warunków zostanie uznany za prawdziwy.
Gigo,
21
Ta czynność jest również wykonywana, gdy tylko jeden z warunków zostanie uznany za fałszywy. Tj. Dokładnie w tych samych przypadkach co poprzedni.
DS.
3
Jest to lepsze, ponieważ usuwa działanie negacji.
Discipol
4
+1, o tyle ładniejsza niż zaakceptowana odpowiedź. jeśli używasz półotwartych zakresów (tj. prostokąt obejmuje górę i lewą stronę, ale nie obejmuje dołu i prawej strony, co jest powszechne w wielu systemach graficznych), zmiana <=na <powinna działać.
Jules
Podoba mi się to rozwiązanie, ponieważ mogę usunąć =warunek dla każdego warunku i pozwala prostokątom „dotykać” granic.
prograhammer
20

W ten sposób platforma .NET Framework implementuje Rectangle.Intersect

public bool IntersectsWith(Rectangle rect)
{
  if (rect.X < this.X + this.Width && this.X < rect.X + rect.Width && rect.Y < this.Y + this.Height)
    return this.Y < rect.Y + rect.Height;
  else
    return false;
}

Lub wersja statyczna:

public static Rectangle Intersect(Rectangle a, Rectangle b)
{
  int x = Math.Max(a.X, b.X);
  int num1 = Math.Min(a.X + a.Width, b.X + b.Width);
  int y = Math.Max(a.Y, b.Y);
  int num2 = Math.Min(a.Y + a.Height, b.Y + b.Height);
  if (num1 >= x && num2 >= y)
    return new Rectangle(x, y, num1 - x, num2 - y);
  else
    return Rectangle.Empty;
}
Schwarrior
źródło
6

Inny prostszy sposób. (Zakłada się, że oś Y rośnie w dół).

function intersect(a, b) {
  return Math.max(a.left, b.left) < Math.min(a.right, b.right) &&
          Math.max(a.top, b.top) < Math.min(a.bottom, b.bottom);
}

Cztery liczby (maks. I min.) W powyższym stanie również dają punkty przecięcia.

Książę
źródło
0

Użyłem mieszanki metod, aby wykryć mniejszy prostokąt wewnątrz dużego prostokąta. Jest to metoda nodejs i wykorzystuje szerokość / wysokość, ale można ją łatwo dostosować.

            isIntersectingRect: function (r1, r2) {
              var quickCheck = (r1.x <= r2.x + r2.w &&
                      r2.x <= r1.x + r1.w &&
                      r1.y <= r2.y + r2.h &&
                      r2.y <= r1.y + r1.h)
              if (quickCheck) return true;
              var x_overlap = Math.max(0, Math.min(r1.x + r1.w, r2.x + r2.w) - Math.max(r1.x, r2.x));
              var y_overlap = Math.max(0, Math.min(r1.y + r1.h, r2.y + r2.h) - Math.max(r1.y, r2.y));
              var overlapArea = x_overlap * y_overlap;
              return overlapArea == 0;
            }
Langerz
źródło