[ Príspevkov: 7 ] 
AutorSpráva
Offline

Užívateľ
Užívateľ
delenie obdlznikov

Registrovaný: 30.12.09
Prihlásený: 13.06.17
Príspevky: 253
Témy: 42 | 42
Bydlisko: Praha_4/Presov
NapísalOffline : 22.01.2011 16:27 | delenie obdlznikov

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


_________________
macbook pro '15 && IBM X61
PC: mobo: DFI LanParty UT P45 t2rs; cpu: Core2Extreme QX6850; ram:OCZ 4x1GB 1150Mhz PC9200 CL5; gpu: asus 9800gx2 hdd: Samsung F3 500GB; psu: TTTP-1,5kW; chassis: Fractal Define r2 lcd: Samsung SyncMaster 2343NW @2048x1152
Offline

Skúsený užívateľ
Skúsený užívateľ
delenie obdlznikov

Registrovaný: 11.01.09
Prihlásený: 26.01.18
Príspevky: 1290
Témy: 9 | 9
Bydlisko: HE
NapísalOffline : 22.01.2011 16:50 | delenie obdlznikov

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


Offline

Užívateľ
Užívateľ
delenie obdlznikov

Registrovaný: 30.12.09
Prihlásený: 13.06.17
Príspevky: 253
Témy: 42 | 42
Bydlisko: Praha_4/Presov
Napísal autor témyOffline : 22.01.2011 16:52 | delenie obdlznikov

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


_________________
macbook pro '15 && IBM X61
PC: mobo: DFI LanParty UT P45 t2rs; cpu: Core2Extreme QX6850; ram:OCZ 4x1GB 1150Mhz PC9200 CL5; gpu: asus 9800gx2 hdd: Samsung F3 500GB; psu: TTTP-1,5kW; chassis: Fractal Define r2 lcd: Samsung SyncMaster 2343NW @2048x1152
Offline

Skúsený užívateľ
Skúsený užívateľ
delenie obdlznikov

Registrovaný: 11.01.09
Prihlásený: 26.01.18
Príspevky: 1290
Témy: 9 | 9
Bydlisko: HE
NapísalOffline : 22.01.2011 21:19 | delenie obdlznikov

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.


Offline

Užívateľ
Užívateľ
delenie obdlznikov

Registrovaný: 30.12.09
Prihlásený: 13.06.17
Príspevky: 253
Témy: 42 | 42
Bydlisko: Praha_4/Presov
Napísal autor témyOffline : 23.01.2011 14:46 | delenie obdlznikov

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.


_________________
macbook pro '15 && IBM X61
PC: mobo: DFI LanParty UT P45 t2rs; cpu: Core2Extreme QX6850; ram:OCZ 4x1GB 1150Mhz PC9200 CL5; gpu: asus 9800gx2 hdd: Samsung F3 500GB; psu: TTTP-1,5kW; chassis: Fractal Define r2 lcd: Samsung SyncMaster 2343NW @2048x1152
Offline

Užívateľ
Užívateľ
delenie obdlznikov

Registrovaný: 03.01.11
Prihlásený: 21.02.11
Príspevky: 54
Témy: 1 | 1
NapísalOffline : 24.01.2011 15:15 | delenie obdlznikov

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)


Offline

Užívateľ
Užívateľ
delenie obdlznikov

Registrovaný: 30.12.09
Prihlásený: 13.06.17
Príspevky: 253
Témy: 42 | 42
Bydlisko: Praha_4/Presov
Napísal autor témyOffline : 24.01.2011 23:43 | delenie obdlznikov

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.


_________________
macbook pro '15 && IBM X61
PC: mobo: DFI LanParty UT P45 t2rs; cpu: Core2Extreme QX6850; ram:OCZ 4x1GB 1150Mhz PC9200 CL5; gpu: asus 9800gx2 hdd: Samsung F3 500GB; psu: TTTP-1,5kW; chassis: Fractal Define r2 lcd: Samsung SyncMaster 2343NW @2048x1152
 [ Príspevkov: 7 ] 


delenie obdlznikov



Podobné témy

 Témy  Odpovede  Zobrazenia  Posledný príspevok 
V tomto fóre nie sú ďalšie neprečítané témy.

nechapem delenie

v ATI/AMD grafické karty

6

972

27.01.2010 3:28

foxXx

V tomto fóre nie sú ďalšie neprečítané témy.

Delenie diskov

v Operačné systémy Microsoft

6

315

27.06.2008 19:40

Flety

V tomto fóre nie sú ďalšie neprečítané témy.

delenie HDD

v Pevné disky a radiče

12

499

05.06.2013 21:52

sp33d

V tomto fóre nie sú ďalšie neprečítané témy.

Delenie viet

v PHP, ASP

6

651

15.07.2008 16:18

vladooo

V tomto fóre nie sú ďalšie neprečítané témy.

Delenie disku

[ Choď na stránku:Choď na stránku: 1, 2 ]

v Pevné disky a radiče

43

2467

21.05.2008 16:24

tommy1104

V tomto fóre nie sú ďalšie neprečítané témy.

Delenie Hdd

v Pevné disky a radiče

7

227

21.09.2015 4:45

branci6138

V tomto fóre nie sú ďalšie neprečítané témy.

Delenie HDD

v Ostatné programy

10

626

27.12.2011 15:15

Ominous

V tomto fóre nie sú ďalšie neprečítané témy.

delenie pomocou *.cue

v Audio programy

1

758

04.09.2006 19:51

maciakba

V tomto fóre nie sú ďalšie neprečítané témy.

Assembler i8080 delenie

v Assembler, C, C++, Pascal, Java

1

313

12.04.2010 21:20

dEVIANT

V tomto fóre nie sú ďalšie neprečítané témy.

Delenie v ciselnych sustavach

v Ostatné

1

848

07.11.2010 10:30

Fico

V tomto fóre nie sú ďalšie neprečítané témy.

OpenOffice Writer - delenie slov

v Ostatné programy

3

711

23.04.2009 23:05

SkyHiRider

V tomto fóre nie sú ďalšie neprečítané témy.

Soft na delenie disku.

v Ostatné programy

4

443

06.08.2008 16:46

SilverSurfer

V tomto fóre nie sú ďalšie neprečítané témy.

Delenie HDD vo W7

v Operačné systémy Microsoft

0

258

11.08.2010 14:53

mirom

V tomto fóre nie sú ďalšie neprečítané témy.

Instalacia OS + delenie HDD

v Operačné systémy Unix a Linux

4

1778

26.10.2009 6:54

Jaro

V tomto fóre nie sú ďalšie neprečítané témy.

Program na delenie disku ?

v Ostatné programy

6

1767

08.02.2009 17:59

McDog

V tomto fóre nie sú ďalšie neprečítané témy.

Delenie HDD + 2 OS

v Pevné disky a radiče

4

1420

07.06.2008 20:10

OmeGa



© 2005 - 2018 PCforum, edited by JanoF