delenie obdlznikov

vital · Napísal **vital**: 22.01.2011 16:27

nejaka hlava co by vedela poradit algoritmus na delenie obdlznikov?

popisem blizsie.
mam pole struktur, struct obsahuje udaj o dolnom lavom a hornom pravom rohu obdzlnika ktorymi je obdlznik zadany (a ine, pre toto nepodstatne udaje).
takze kazdy obdlznik v zozname je definovany suradnicami v rovine (x1,y1,x2,y2)

mam funkciu na zistenie intersekcie dvoch obdlznikov. teda dva obdlzniky su bud neprekryte a pokracujem porovnanim dalsich dvoch, alebo su prekryte a -> potrebujem ich rozdelit a kazdy z nich pridat do zoznamu.

viac (snad) napovie obrazok:
delenie obdlznikov

do zoznamu chcem teda pridat vsetkych 5 oblznikov (dva povodne zmazem). vedeli by ste poradit co najjednoduchsi a efektivny algoritmus, ktory by bol funkcny pre vsetky pripady intersekcie?

ak ano, poprosil by som len slovny popis, alebo pseudokod.

vopred vdaka

Fico · Napísal **Fico**: 22.01.2011 16:50

V prvom rade presne definuj, ako sa majú obdĺžniky rozdeliť, pretože okrem tvojho spôsobu by sa to dalo rozdeliť aj takto:

delenie obdlznikov

alebo takto:

delenie obdlznikov

vital · Napísal autor témy **vital**: 22.01.2011 16:52

je jedno ci podla x alebo y. ten treti urcite nie.

Fico · Napísal **Fico**: 22.01.2011 21:19

Fajn, tak postup by mohol byť takýto:

1.) budeš kontrolovať každý bod jedného obdĺžnika, či sa nenachádza v druhom. Pomocná funkcia ( jazyk C ):

Kód:

typedef struct {               // struktura popisujuca suradnice obdlznikov

   int x1, y1, x2, y2;

} coord;

// x a y su suradnice jedneho bodu obdlznika, rect su suradnice x1:y1, x2:y2 druheho obdlznika

bool isInRect( int x, int y, coord rect ) {

   if ( ( ( x > rect.x1 ) && ( x < rect.x2 ) ) && ( ( y > rect.y2 ) && ( y < rect.y1 ) ) )
      return true;

   return false;

}

2.) ak bude výsledok funkcie true, znamená to, že daný bod je vnútri obdĺžnika a vzniká tam nový bod pre ďalšie obdĺžniky.

3.) do poľa (zoznamu), kde chceš ukladať nové súradnice, pridávaj nové súradnice obdĺžnikov a to takto: nakoľko sa kontrolovaný bod jedného obdĺžnika nachádza v druhom obdĺžniku ( popis v bode 2 ), daný bod rozdelí tento obdĺžnik na tri časti:

delenie obdlznikov

čiže do poľa uložíš tri nové obdĺžniky takto (je to rozdelené v osi X, keďže si vravel, že to je jedno):

Kód:

typedef struct {               // struktura popisujuca bod

   int x, y

} point;

// ...

   // kontrolovany bod

   coord rect1, rect2, temp;      // suradnice: 1. obdlznik, 2. obdlznik, pomocna premenna temp
   std::vector< coord > array;      // pole obdlznikov

   point p;            // v nom budu suradnice kontrolovaneho bodu

   // prvy novy obdlznik

   temp.x1 = rect1.x1;
   temp.y1 = p.y;
   temp.x2 = rect1.x2;
   temp.y2 = rect1.y2;
   array.push_back( temp );

   // druhy novy obdlznik

   temp.x1 = rect1.x1;
   temp.y1 = rect1.y1;
   temp.x2 = p.x;
   temp.y2 = p.y;
   array.push_back( temp );

   // treti novy obdlznik

   temp.x1 = p.x;
   temp.y1 = rect1.y1;
   temp.x2 = rect1.x2;
   temp.y2 = p.y;
   array.push_back( temp );

Pre os Y to bude iba s drobnými zmenami. To isté budeš robiť pre všetky body ( tzn celú kontrolu ) a nakoniec v poli porovnáš súradnice, ktoré sú rovnaké ( pretože niektoré sa budú opakovať ).

Je to postup písaný z hlavy, určite to bude mať nejaké muchy, ale snáď máš teraz aspoň nejakú víziu, ako na to.

vital · Napísal autor témy **vital**: 23.01.2011 14:46

velka vdaka za tvoj cas, necakal som ze sa na to niekto pozrie.
funkcne to urcite bude, problem ale pre mna je ze to riesi len jeden pripad (resp 4) a to vtedy ked sa v druhom obdlzniku nachadza prave jeden bod toho prveho.

existuje ale celkom (tusim) 14 sposobov prekrytia, ktore je treba riesit a vypisovat kazdu moznost je dost neefektivne (myslim ze by to slo zredukovat aspon na 3 alebo 4 moznosti).
prikladam obrazok, ako to vidim...

delenie obdlznikov

takymto riesenim by tam dost stupla cyklomaticka zlozitost si myslim, a druhy problem je ten, ze vysledny program (v ktorom je to delenie len jednou z funkcii) ako celok to musi stihnut v obmedzenom casovom horizonte s velkym datovym objemom a obmedzenou pamatou, preto hladam co najefektivnejsie riesenie. v helpe bolo uvedene ze pridavanie obdlznikov do zoznamu by sa malo riesit rekurzivne, ale nejak som nato zatial nedosiel ako ich delit a pridavat rekurzivne.

ako som sa zmienil, ide mi len o nejaky logicky napad, na efektivne riesenie, nejaku moznost ako by to slo riesit. urcite necakam kompletne funkcie alebo neviem co.

vdaka este raz.

//podarilo sa mi to zredukovat na 3 pripady zatial... keby ste ale vedeli o niecom univerzalnom, velmi by mi to pomohlo.

prohibit · Napísal **prohibit**: 24.01.2011 15:15

tvojich 14 moznosti nie je spravne. Ide o rovinu, a nie priestor a teda je jedno ci je obdlznik 2 nad (v zmysle osi z) obdlznikom 1 alebo opacne. Teda v tvojom poslednom prispevku z prvej stvorice su dva pripady (prvy a druhy stlpec), z druhej stvorice mas zase totozne pripady v riadkoch, v tretej stvorici ich mas zase v riadkoch totozne a v poslednej dvojici mas tiez iba jeden pripad. Tebe sa totiz osi pretinaju a vidis ich ako siet a nie ako plne utvary. Takze tych moznosti je 7 + moznost kedy je jeden cely obdlznik vnutry druheho (teda zjednotenie oboch mnozin dava ten vacsi obdlznik. Algoritmicky ti to vsak odchyti druhy typ co si nakreslil, takze uvazujme iba 7 moznosti). Vsetky s vynimkou poslednej ti ale zahrnie Ficov postup, jedine by som navrhol lepsi test na intersekciu bodu a obdlzniku. Netreba tam 4 podmienky, da sa spravit dvoma:

Kód:

bool isInRect( int x, int y, coord rect ) {
   return (x + rect.x1 < rect.x2) && (y + rect.y2 < rect.y1 );
}

tych 7 moznosti tiez nie je maximum, vedel by som to zredukovat na jedinu ale to by si musel byt menej konzervativny a nezavrhnut tak razne posledne Ficove riesenie. Delil by som to v oboch osiach, a potom v jednej osi spajal obdlzniky kde ich je v rade menej ako tri (to mi pokryje aj posledny pripad z tvojich obrazkov)

vital · Napísal autor témy **vital**: 24.01.2011 23:43

jedno to podla mna nieje, kedze tie obdlzniky porovnavas ako obdlznik A a B. na to aby sa dalo riesit menej moznosti teda staci vymenit obdlzniky pri porovnani. delit po oboch osiach je nepripustne kvoli casovemu limitu v ktorom musi program prebehnut, pretoze toto je len cast programu, a zoznam obdlznikov je potrebne prelistovat vela krat, preto udrziavat tam zbytocne obdlzniky nieje vyhodne.
moznost kedy je jeden obdlznik cely v druhom nieje potrebne riesit, taky obdlznik zo zoznamu mazem.
a tie posledne dva su len jeden, mas pravdu, tam som sa sekol.

kazdopadne, delenie mam uz vyriesene(fico mi dal napad, za co velmi pekne dakujem), nie nejak prilis efektivne, ale funkcne, uz len dufam ze to bude stihat.

delenie obdlznikov

Podobné témy