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

Bill Atkinson halálhíre kapcsán az internet népe megemlítette a régiókat, melynek hatására elkezdtem én is gondolkozni a problémán: két fedésben lévő ablak közül a felsőt elmozdítva hogyan határoznám meg azt a legkisebb felületet, amely az alsó ablakból láthatóvá válik (és ezért újra kell rajzolni)? A problémát bizonyára ezerszer megoldották, tehát nem a spanyol viaszt akarom feltalálni vele; csak jó érzésnek ígérkezett az éjszakai agytorna.

( apal v | 2025. 06. 08., v – 19:11 )

Ez a computational geometry meg mindig egy nagyon szep temakor :)

Nekem ez ennyire komplex modon meg nem kellett (leragadtam a "ket teglalap metszete" illetve a "teglalap es kör metszetenek a terulete" temakoroknel), de ha egy kicsit absztraktabban gondolkodunk, akkor csinalhatunk egy olyan megkozelitest is hogy bevezetjuk a "csik" fogalmat. A teglalap ugye az "x0 <= x < x1 es y0 <= y < y1" halmaz, a "fuggoleges csik" legyen az "x0 <= x < x1" halmaz, es a "vizszintes csik" pedig az "y0 <= y < y1" halmaz. Ekkor igazak az alabbi allitasok:

  • vizszintes csikok metszete egy vizszintes csik, fuggoleges csikok metszete egy fuggoleges csik
  • ket vizszintes csik kulonbsege egy vagy ket vizszintes csik, ugyanez hasonloan fuggolegesre is
  • ket vizszintes csik unioja egy vagy ket vizszintes csik, ugyanez hasonloan fuggolegesre is
  • teglalap az egy vizszintes es egy fuggoleges csik metszete

Nem tudom, de ebbol mar szerintem relative egyszeruen kovetkezik az hogy ket tegnalap kulonbsege eloall max negy diszjunkt teglalap uniojakent ill az algoritmus maga is kipottyan. Ket teglalap unioja pedig talan 3 diszjunkt teglalap uniojakent(?). Oke, ezutobbiban nem vagyok biztos, meg kell nezni :)

A masik amivel neha szembekerulok az hogy teglalapot, vagyis szakaszt hogy erdemes reprezentalni. Igy hogy [x0,x1) vagy hogy [x0,x0+sx). Neha ez jobb, neha az... nem tudom...

Masik megkozelites lehet hogy:

  • minden teglalapot felszeleteluink 2 ... 9 masik kisebb, osszepasszolo, diszjunkt teglalapra attol fuggoen hogy hol van a masik teglalapnak a hatara
  • ezek a darabok akkor ugye vagy teljesen atfednek vagy teljesen diszjunktak lesznek
  • sima boolean logika szerint megnezzuk mi a metszet, kulonbseg, unio
  • opcionalisan a maradekot valami egyszeru algoritmussal osszeejtjuk kevesebb de nagyobb teglalappa ha lehetseges. 

Ezutobbi lehet erdekes hogy hogyan is skalazodik. O(N^2)-tel konnyu megcsinalni, de valami egyszerubb indexeles kell(het) akkor ha ennel jobb futasidot szeretnenk. 

( lacos | 2025. 06. 08., v – 20:16 )

Egy másik megközelítés (pontosabban ugyanannak az átfogalmazása):

  1. Mivel T₀ \ T₁ = T₀ \ (T₀ ∩ T₁), azért először számoljuk ki az [X₁, Y₁) × [X₂, Y₂) := (T₀ ∩ T₁) metszetet. Ha ez üres halmaz, akkor a különbség T₀ \ {} = T₀.
  2. Egyébként pedig a nemüres metszet-téglalap a T₀-nak részhalmaza, és akkor a fenti ciklus azonos módon működik.

 

@@ -45,15 +45,20 @@
   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[1] = max(r0->tl.x, r1->tl.x);
+  xdiv[2] = min(r0->br.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[1] = max(r0->tl.y, r1->tl.y);
+  ydiv[2] = min(r0->br.y, r1->br.y);
   ydiv[3] = r0->br.y;
 
+  if (xdiv[1] >= xdiv[2] || ydiv[1] >= ydiv[2]) {
+    *diff = *r0;
+    return 1;
+  }
+
   n = 0;
   for (i = 0; i < 3; i++) {
     for (j = 0; j < 3; j++) {

... szerk.: a program két változata között az a különbség, hogy az első változat a T₁-et "clamp"-eli a T₀-ra, és az eredményt mindenképpen körüljárja (akkor is, ha a clamp-elt halmaz üres), a második változat pedig metszetet képez, és a metszetet -- de csak ha az nem üres -- járja körbe. Az utóbbi esetben nem számít, hogy a metszet pontosan "hogyan" üres, az előbbi (clamp-elt) megközelítésnél viszont nagyon is számít.