téglalapok metszete, különbsége, uniója

Az alábbiakban balról zárt, jobbról nyílt intervallumokat fogunk használni; ez ui. egyrészt praktikus, másrészt az egyetlen helyes reprezentáció :) Intervallumnak most nemnegatív egész számokat tartalmazó halmazokat fogunk tekinteni; a, b ∈ ℕ esetén definiáljuk

• [a, b) := { n ∈ ℕ | a ≤ n ∧ n < b }

Minden olyan esetben, amikor (a ≥ b), akkor az intervallum üres; más szóval, az intervallum nemüres pontosan akkor, ha (a < b).

Két intervallum metszete szintén ilyen -- balról zárt, jobbról nyílt -- intervallum:

• [a, b) ∩ [c, d) := { n ∈ ℕ | (a ≤ n ∧ n < b) ∧ (c ≤ n ∧ n < d) }

Az n-re vonatkozó becsléseket típusaik szerint csoportosítva azt kapjuk, hogy

• [a, b) ∩ [c, d) = { n ∈ ℕ | (a ≤ n ∧ c ≤ n) ∧ (n < b ∧ n < d) }
• [a, b) ∩ [c, d) = { n ∈ ℕ | (max { a, c } ≤ n ∧ n < min { b, d } }
• [a, b) ∩ [c, d) = [max { a, c }, min { b, d })

És a metszet természetesen lehet üres is, az első bekezdés utolsó mondata szerint.

Most térjünk át téglalapokra!

Téglalapot két intervallum Descartes-szorzataként definiálunk:

• [x₀, x₁) × [y₀, y₁) := { (x, y) ∈ ℕ×ℕ | (x₀ ≤ x ∧ x < x₁) ∧ (y₀ ≤ y ∧ y < y₁) }

Két téglalap metszete -- ([x₀, x₁) × [y₀, y₁)) ∩ ([u₀, u₁) × [v₀, v₁)) -- szintén téglalap. Kezdésként írjuk fel a metszet-téglalap feltételét -- a metszet pontjai azon pontok, amelyek mindkét eredeti téglalapnak elemei:

• { (x, y) ∈ ℕ×ℕ | ((x₀ ≤ x ∧ x < x₁) ∧ (y₀ ≤ y ∧ y < y₁)) ∧ ((u₀ ≤ x ∧ x < u₁) ∧ (v₀ ≤ y ∧ y < v₁)) }

Mivel a feltétel itt is csak "logikai és" ∧ műveleteket használ, azért szabadon átrendezhetjük:

• { (x, y) ∈ ℕ×ℕ | (x₀ ≤ x ∧ u₀ ≤ x) ∧ (x < x₁ ∧ x < u₁) ∧ (y₀ ≤ y ∧ v₀ ≤ y) ∧ (y < y₁ ∧ y < v₁) }
• { (x, y) ∈ ℕ×ℕ | (max { x₀, u₀ } ≤ x ∧ x < min { x₁, u₁ }) ∧ (max { y₀, v₀ } ≤ y ∧ y < min { y₁, v₁ }) }
• [max { x₀, u₀ }, min { x₁, u₁ }) × [max { y₀, v₀ }, min { y₁, v₁ })

Mivel a "logikai és" műveleteket tetszőlegesen átcsoportosíthatjuk, ezért téglalapok metszetét úgy kapjuk, hogy dimenziónként az intervallumoknak a metszetét képezzük, és a metszet-intervallumokat összeszorozzuk. A metszet-téglalap pontosan akkor üres, ha legalább az egyik dimenzióban a metszet-intervallum üres.

A téglalapok metszetével az eredeti kérdést részletesebben meg tudjuk fogalmazni. A felső ablak elmozdítása előtt az alsó és a felső ablaknak van egy metszete (ez lehet üres is); ez a metszet van takarásban. Legyen ez M₀. A felső ablak elmozdítása után -- esetleg átméretezése után -- a két ablaknak ismét lesz egy metszete (ami önmagában megint csak lehet üres is); ez legyen M₁. Ami minket érdekel (vagyis az a "leleplezett" felület, amit az alsó ablakból újra kell rajzolnunk a felső ablak elmozdítása/átméretezése után), az a két metszet különbsége: (M₀ \ M₁) -- azok a pontok, amelyek korábban takarásban (= metszetben) voltak, de most már nincsenek takarásban (= metszetben).

Azt már beláttuk, hogy mind M₀, mind M₁ téglalapok -- a különbségük viszont nem az! Most találjuk ki, hogy hogyan lehet téglalapok különbségét praktikusan felírni!

Írjuk fel két téglalap különbségét a definícióval:

• T₀ := [x₀, x₁) × [y₀, y₁) = { (x, y) ∈ ℕ×ℕ | (x₀ ≤ x ∧ x < x₁) ∧ (y₀ ≤ y ∧ y < y₁) }
• T₁ := [u₀, u₁) × [v₀, v₁) = { (x, y) ∈ ℕ×ℕ | (u₀ ≤ x ∧ x < u₁) ∧ (v₀ ≤ y ∧ y < v₁) }
• T₀ \ T₁ = { (x, y) ∈ T₀ | (x, y) ∉ T₁ }

Innentől a különbséghez tartozást megadó predikátumot kell pofozgatnunk:

• (x, y) ∈ T₀ ∧ (x, y) ∉ T₁

A lényeg a logikai "és nem":

• ((x₀ ≤ x ∧ x < x₁) ∧ (y₀ ≤ y ∧ y < y₁)) ∧ ¬((u₀ ≤ x ∧ x < u₁) ∧ (v₀ ≤ y ∧ y < v₁))

Hagyjuk is el a felesleges zárójeleket:

• x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ ¬(u₀ ≤ x ∧ x < u₁ ∧ v₀ ≤ y ∧ y < v₁)

A logikai negálást De Morgan azonossággal bevisszük a zárójelen belülre. Ennek a szabályai:

1. konjunkcióból (∧) diszjunkció (∨) lesz,
2. az eredeti konjunkciók operandusait negáljuk; konkrétan ≤-ből > lesz, valamint <-ből ≥ lesz.

A De Morgan azonosság alkalmazásával kapjuk:

• x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ (u₀ > x ∨ x ≥ u₁ ∨ v₀ > y ∨ y ≥ v₁)

A disztributivitás alkalmazásával bontsuk fel a zárójelet -- ennek hatására a kifejezésünk diszjunktív normálformát ölt:

• (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ u₀ > x) ∨
  (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ x ≥ u₁) ∨
  (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ v₀ > y) ∨
  (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ y ≥ v₁)

Itt fizetődik ki az, hogy balról zárt, jobbról nyílt intervallumokat használunk! Nézzük meg a fenti diszjunktív normálforma minden egyes elemi konjunkcióját! Bármelyiket tekintjük a négyből, valójában egy téglalapot látunk leírva, azzal a huncutsággal, hogy a téglalap egyik dimenziójában az alkotó intervallum valamelyik határára nem egy, hanem kettő becslés vonatkozik; ráadásul pontosan ugyanolyan relációs jellel.

Megismétlem a fenti kifejezést, csak más kiemelésekkel:

• (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ u₀ > x) ∨
  (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ x ≥ u₁) ∨
  (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ v₀ > y) ∨
  (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁ ∧ y ≥ v₁)

(A balról zárt, jobbról nyílt intervallumos ábrázolásnak itt az a haszna, hogy amikor a De Morgan azonossághoz a relációs operátorokat negáltuk, akkor a nyílt határok zártba váltottak, és viszont.)

Az azonos változóra azonos relációs jellel vonatkozó becsléseket most vonjük össze, a szokásos módon: vegyük a nem-lazább becslést. Ezt kapjuk:

• (x₀ ≤ x ∧ x < min { x₁, u₀ } ∧ y₀ ≤ y ∧ y < y₁) ∨
  (max { x₀, u₁ } ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < y₁) ∨
  (x₀ ≤ x ∧ x < x₁ ∧ y₀ ≤ y ∧ y < min { y₁, v₀ }) ∨
  (x₀ ≤ x ∧ x < x₁ ∧ max { y₀, v₁ } ≤ y ∧ y < y₁)

Azt látjuk, hogy a T₀ \ T₁ különbség négy téglalap uniója -- ahol minden egyes téglalap (a többitől függetlenül) lehet persze üres is [*].

([*] Például -- feltételezve azt, hogy sem T₀, sem T₁ nem üres -- a legutolsó elemi konjunkció ponosan akkor kielégíthetetlen, ha (v₁ ≥ y₁). Ugyanis ekkor (v₁ ≥ y₁ > y₀), tehát (max { y₀, v₁ } = v₁). Ezálal a negyedik elemi konjunkció vége úgy alakul, hogy (y₁ ≤ v₁ ≤ y < y₁); ez kielégíthetetlen bármely y számára, mert (y₁ < y₁) konstans hamis.)

Most érdemes egy ábrát készítenünk (megjegyzés: az ábrát javítottam, mert az eredetileg feltüntetett koordináták kimondatlanul feltételezték, hogy a T₁ a T₀-on belülre esik):

                             x₀  max { x₀, min { x₁, u₀ } }  min { x₁, max { x₀, u₁ } }  x₁
                          0--|---------------|---------------------------|---------------|--> x
                          |
                        y₀-  +---------------+---------------------------+---------------+
                          |  |\\\\\\\\\\\\\\\|///////////////////////////|\\\\\\\\\\\\\\\|
                          |  |\\\\(0; 0)\\\\\|//////////(1; 0)///////////|\\\\(2; 0)\\\\\|
                          |  |\\\\\\\\\\\\\\\|///////////////////////////|\\\\\\\\\\\\\\\|
max { y₀, min { y₁, v₀ } }-  +---------------+-------------------------------------------+
                          |  |///////////////|                           |///////////////|
                          |  |////(0; 1)/////|          (1; 1)           |////(2; 1)/////|
                          |  |///////////////|                           |///////////////|
min { y₁, max { y₀, v₁ } }-  +---------------+-------------------------------------------+
                          |  |\\\\\\\\\\\\\\\|///////////////////////////|\\\\\\\\\\\\\\\|
                          |  |\\\\(0; 2)\\\\\|//////////(1; 2)///////////|\\\\(2; 2)\\\\\|
                          |  |\\\\\\\\\\\\\\\|///////////////////////////|\\\\\\\\\\\\\\\|
                        y₁-  +---------------+---------------------------+---------------+
                          |
                          v

                          y

Az ábrán azt látjuk (általánosan), ahogy a T₀ téglalapból kivonjuk a T₁ téglalapot. A satírozott rész a (T₀ \ T₁) különbség, a fehéren hagyott rész pedig T₁ (a kivonandó téglalap).

A fenti diszjunktív normálforma elemi konjunkciói (abban a sorrendben) a "bal" (0; *), "jobb" (2; *), "felső" (*; 0), "alsó" (*; 2) téglalapokat adják meg.

Satírozásra két mintát használtam. Ha a leírt négy téglalap uniója szerint "naivan" frissítenénk a "leleplezett" területet, akkor a backslash-sel satírozott területeket duplán rajzolnánk, és csak a forward slash-sel satírozott területeket rajzolnánk pontosan egyszer.

A dupla rajzolás elkerülésére a (T₀ \ T₁) különbséget bontsuk fel nyolc kis téglalapra. A téglalapok koordinátái leolvashatók az ábráról. Lényegében van egy X abszcisszalistánk (i ∈ { 0, 1, 2, 3}):

• x₀
• max { x₀, min { x₁, u₀ } }
• min { x₁, max { x₀, u₁ } }
• x₁

és egy Y ordinátalistánk (j ∈ { 0, 1, 2, 3}):

• y₀
• max { y₀, min { y₁, v₀ } }
• min { y₁, max { y₀, v₁ } }
• y₁

és a Kᵢⱼ kis téglalap (i, j ∈ { 0, 1, 2 }, (i, j) ≠ (1; 1)) akkor nem üres, ha

• Xᵢ < Xᵢ₊₁ ∧ Yⱼ < Yⱼ₊₁

Továbbra is igaz, hogy minden intervallum (mindkét dimenzióban) balról zárt, jobbról nyílt. Tehát például az

• (X₁, Y₁) = (max { x₀, min { x₁, u₀ } }, max { y₀, min { y₁, v₀ } })

sarokpont a (0; 0), (1; 0), (0; 1) kis téglalapok egyikének sem része.

A T₀ és T₁ egymáshoz képesti elhelyezkedésétől függően, ahogy írtam, a négy darab elemi konjunkció által leírt egyes téglalapok lehetnek (egymástól függetlenül) üresek; ez azt is jelenti, hogy a nyolc kis téglalap sem feltétlenül létezik mind egyszerre.

C nyelvű kódrészlet a (T₀ \ T₁) különbség számítására:

#include <assert.h>
#include <stddef.h>

struct point {
  unsigned x, y;
};

struct rect {
  struct point tl, br;
};

static unsigned
min(unsigned a, unsigned b)
{
  return a < b ? a : b;
}

static unsigned
max(unsigned a, unsigned b)
{
  return a > b ? a : b;
}

/*
 * Calculate "r0" \ "r1". Store the difference as an array of mutually disjunct
 * nonempty rectangles, starting at "diff".
 *
 * At most 8 rectangles are stored. The number of rectangles stored is
 * returned. If "diff" is NULL on input, then nothing is stored, only the
 * number of output rectangles is returned.
 *
 * The caller is responsible for ensuring that "r0" and "r1" are nonempty
 * rectangles.
 */
size_t
rect_minus(const struct rect *r0, const struct rect *r1, struct rect *diff)
{
  unsigned xdiv[4], ydiv[4];
  size_t n;
  size_t i, j;

  assert(r0->tl.x < r0->br.x);
  assert(r0->tl.y < r0->br.y);
  assert(r1->tl.x < r1->br.x);
  assert(r1->tl.y < r1->br.y);

  xdiv[0] = r0->tl.x;
  xdiv[1] = max(r0->tl.x, min(r0->br.x, r1->tl.x));
  xdiv[2] = min(r0->br.x, max(r0->tl.x, r1->br.x));
  xdiv[3] = r0->br.x;

  ydiv[0] = r0->tl.y;
  ydiv[1] = max(r0->tl.y, min(r0->br.y, r1->tl.y));
  ydiv[2] = min(r0->br.y, max(r0->tl.y, r1->br.y));
  ydiv[3] = r0->br.y;

  n = 0;
  for (i = 0; i < 3; i++) {
    for (j = 0; j < 3; j++) {
      if (i == 1 && j == 1) {
        continue;
      }
      if (xdiv[i] < xdiv[i + 1] && ydiv[j] < ydiv[j + 1]) {
        if (diff != NULL) {
          diff[n].tl.x = xdiv[i];
          diff[n].tl.y = ydiv[j];
          diff[n].br.x = xdiv[i + 1];
          diff[n].br.y = ydiv[j + 1];
        }
        n++;
      }
    }
  }
  return n;
}

A kódot természetesen nem teszteltem :)

Felmerül még a kérdés, hogy hogyan tudnánk két téglalap unióját reprezentálni, páronként diszjunkt kis téglalapok felhasználásával. A metszet és a különbség fent megadott számításával ez megoldható, ugyanis az unióra áll az alábbi diszjunkt felbontás:

• T₀ ∪ T₁ = (T₀ \ T₁) ∪ (T₁ \ T₀) ∪ (T₀ ∩ T₁)

A metszet önmaga is (potenciálisan üres) téglalap, a két különbség -- együttesen: a szimmetrikus differencia -- pedig páronként diszjunkt kis téglalapok (potenciálisan üres) halmaza.