Preveri če skupina pravokotnikov prekriva pravokotik

Vse o programiranju na in za PC

Moderatorji: Kroko, tilz0R

Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a tilz0R » 09 Jul 2018, 20:37

Imam nek pravokotnik, za katerega imam znano x in y pozicijo ter širino in višino.
Nad njim imam N pravokotnikov (vsi so ->next na linked listi, začnejo se z mojim pravokotnikom za katerega me zanima če je skrit), vsak ima spet x in y, ter višino in širino.

Kako bi lahko najlažje preveril, če vsi pravokotniki skupaj prekrijejo osnovni pravokotnik?
Kar pomeni, da če bi vse narisal na papir, originalnega ne bi videl, ker bi ga ostali prekrili.

Iščem rešitev, ki ne bi vključevala n dinamičnih alokacij. Delam v C-ju.
Zadeva je precej bolj kompleksna, kot sem imel v mislih v avtu med potjo domov :)

Kakšna ideja?
Knowledge sharing is people' caring., T. MAJERLE
Uporabniški avatar
tilz0R
 
Prispevkov: 1393
Pridružen: 18 Jan 2015, 00:12
Kraj: Črnomelj
Zahvalil se je: 182 krat
Prejel zahvalo: 341 krat
Uporabnika povabil: s56rga
Število neizkoriščenih povabil: 255

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a VolkD » 09 Jul 2018, 22:20

Jaz bi naredil dobesedno s prekrivanjem.
Pri celotnem prostoru v katerem je/so pravokotnik (i) je treba najprej določiti raster. Ta definira najmanjšo možno točko neprekritega.
Potem v prostor narišeš prvi pravokotnik in celoten raster (površino) ki ima začetno vrednost(0) označiš z neko vrednostjo (1). Nato postopoma vrisuješ še ostale pravokotnike katerih površino označuješ z novo vrednostjo (2). Na koncu preprosto preiščeš površino. Če je kje vpis (1), potem pravokotniki niso v celoti uspeli prekriti prvega pravokotnika.

Seveda tega ne rabiš v resnici risati, dovolj je le označevanje v nekem velikem array-u.

Upam, da sem bil razumljiv.
Dokler bodo ljudje mislili, da živali ne čutijo bolečine, bodo živali čutile, da ljudje ne mislijowww.S5tech.net
Uporabniški avatar
VolkD
Administratorji strani
 
Prispevkov: 26475
Pridružen: 29 Dec 2014, 20:49
Kraj: Kačiče (Divača)
Zahvalil se je: 4874 krat
Prejel zahvalo: 3499 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 254

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a tilz0R » 09 Jul 2018, 22:35

VolkD je napisal/-a:Jaz bi naredil dobesedno s prekrivanjem.
Pri celotnem prostoru v katerem je/so pravokotnik (i) je treba najprej določiti raster. Ta definira najmanjšo možno točko neprekritega.
Potem v prostor narišeš prvi pravokotnik in celoten raster (površino) ki ima začetno vrednost(0) označiš z neko vrednostjo (1). Nato postopoma vrisuješ še ostale pravokotnike katerih površino označuješ z novo vrednostjo (2). Na koncu preprosto preiščeš površino. Če je kje vpis (1), potem pravokotniki niso v celoti uspeli prekriti prvega pravokotnika.

Seveda tega ne rabiš v resnici risati, dovolj je le označevanje v nekem velikem array-u.

Upam, da sem bil razumljiv.


To je ena izmed opcij. Kar se mi ne dopade, je to da je pravokotnik lahko velik kot je velikost zaslona, recimo 800x480. Če vsak jih dajem kot bite v array-ju, je to 800*480/8 = 48kB rama :)
Knowledge sharing is people' caring., T. MAJERLE
Uporabniški avatar
tilz0R
 
Prispevkov: 1393
Pridružen: 18 Jan 2015, 00:12
Kraj: Črnomelj
Zahvalil se je: 182 krat
Prejel zahvalo: 341 krat
Uporabnika povabil: s56rga
Število neizkoriščenih povabil: 255

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a VolkD » 09 Jul 2018, 22:42

Temu ne boš mogel pobegniti. Razmisli malo. Dokler ne narišeš vseh, recimo, da si pri predzadnjem, ne moreš sprostiti informacij, ki so jih naredili predhodni. Govorim seveda o tem, da je prvi pravokotnik lahko velik kot ekran.

Če je manjši je pa dovolj, da se greš igranja le na njegovi površini, pri vseh ostalih točkah pa ugotoviš le, da so izven in ne narediš ničesar.
Dokler bodo ljudje mislili, da živali ne čutijo bolečine, bodo živali čutile, da ljudje ne mislijowww.S5tech.net
Uporabniški avatar
VolkD
Administratorji strani
 
Prispevkov: 26475
Pridružen: 29 Dec 2014, 20:49
Kraj: Kačiče (Divača)
Zahvalil se je: 4874 krat
Prejel zahvalo: 3499 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 254

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a tilz0R » 10 Jul 2018, 07:18

Verjetno res ne, ne vem še. Gre se za to, da če imam nek (recimo) gumb na zaslonu, ki je prekrit z drugim, ampak na istem oknu (isti parent), potem spodnjega ne bi rabil risati, ker bom itak zgornjega čez še enkrat.
Če je rectangle velik, pisanje vseh teh bitov + alokacija bo trajalo dlje kot pa risanje teh pixlov.

Idealno bi bilo, če bi lahko imel x1, y1, x2, y2 in iskal vidno polje prvega pravokotnika, ampak mislim da ne bo šlo.
Knowledge sharing is people' caring., T. MAJERLE
Uporabniški avatar
tilz0R
 
Prispevkov: 1393
Pridružen: 18 Jan 2015, 00:12
Kraj: Črnomelj
Zahvalil se je: 182 krat
Prejel zahvalo: 341 krat
Uporabnika povabil: s56rga
Število neizkoriščenih povabil: 255

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a xfce » 10 Jul 2018, 07:50

@tilz0R

Hm... ja meni se vsekakor zdi nesmiselno, da bi izrisal stvari, ki se jih na koncu ne vidi. To je zelo procesorsko potratno, da bi npr barval celo ozadje modro, potem pa narisal čez še en lik, ki prekriva 99% spodnjega in še potem en lik, ki pokriva 98% prejšnjega. Praktično bi narisal sliko na zaslonu 3x namesto 1x.

Kaj, če bi pa šel tako:
Za vsak lik bi shranil koordinate in barvo v RAM. Torej bi imel samo 2D array likov (samo točke, ki kreirajo lik, ter njegovo barvo), ki si jih narisal, ter shranjenje po layerjih.

Potem bi pa imel for zanko za izris celotnega zaslona/oz samo dela, ki izriše na zaslon po posameznih pikslih. Za vsak piksel bi se pogledal po likih, če je na na najvišjem layerju lik prisoten (potem bi pobarval), če ne bi šel na nižji layer pogledat, če je tisti lik prisoten itd, čez vse layerje.
Za preverjanje, če je lik v tisti točki prisoten bi uporabil uporabil nekaj takega: http://alienryderflex.com/polygon/, potem greš pa samo še po layejih.

Na ta način:
Koda: Izberi vse
for(x=0;x<screen_width;x++){
     for(y=0;y<screen_height;y++){
        char layer = num_of_layers;
        while(layer--){
           if is_point_in_polygon(x,y,polygon[layer]) {
            draw_pixel[x,y,polygon[color]];
            layer -1;
            }
       }

    }

}


Sem bil razumljiv? :D
xfce
 
Prispevkov: 534
Pridružen: 14 Feb 2015, 12:38
Kraj: Poljane nad Škofjo loko
Zahvalil se je: 66 krat
Prejel zahvalo: 132 krat
Uporabnika povabil: S52O
Število neizkoriščenih povabil: 26

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a tilz0R » 10 Jul 2018, 08:00

BIl si razumljiv. Tak način je še najbolj potraten, ker je to ogromno zank in iz stališča CPU-ja je to pipeline flushing. V tem primeru bi bilo hitreje če bi HW narisal vse tri like enega na drugim :)

Uporabiti hočem HW kolikor se le da, kar pomeni, da rečem HW-ju, imaš X in Y pozicijo ter width/height info. Nariši kvadrat. Pri tem se vsak pixel zapiše v memory v 1-ciklu vhodne ure.

S tem, ko bi izračunal, če je lik popolnoma prekrit, bi rad samo naredil skip risanja in šel pogledat naslednjega. Zato bi rabil nek način (če obstaja), kjer bi samo z zanko med ostalimi pravokotniki določil, če prekrivajo prvega.
Teoretično rabim algoritem, ki je hitrejši kot risanje lika. Vsi dosedanji poskusi so počasnejši ali max enako hitri.
Ampak bolj kot probavam, bolj komplicirano je :)
Knowledge sharing is people' caring., T. MAJERLE
Uporabniški avatar
tilz0R
 
Prispevkov: 1393
Pridružen: 18 Jan 2015, 00:12
Kraj: Črnomelj
Zahvalil se je: 182 krat
Prejel zahvalo: 341 krat
Uporabnika povabil: s56rga
Število neizkoriščenih povabil: 255

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a xfce » 10 Jul 2018, 08:54

No, če imaš pa HW, ki ti riše like na display, potem pa res ne vem kako misliš, da bi lahko s CPU kaj prehitel. Če bi optimiziral, bi lahko samo iz tega stališča, če rišeš piksle z CPU, če pa uporabljaš funkcije displaya pa mislim, da nimaš pogojev, da boš ti hitreje ugotovil kaj je za narisati, kot če boš enostavno poslal ukaze LCD driverju. :D
Kakor, sem sam delal, so liki res mala malica. Problem je recimo risanje grafa, ki se pomika po Y osi (to sem naredil za prikazovanje temperature). To procesorju pobere čas, da ti izriše vsakič cel zaslon.
xfce
 
Prispevkov: 534
Pridružen: 14 Feb 2015, 12:38
Kraj: Poljane nad Škofjo loko
Zahvalil se je: 66 krat
Prejel zahvalo: 132 krat
Uporabnika povabil: S52O
Število neizkoriščenih povabil: 26

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a s54mtb » 10 Jul 2018, 09:04

1. Narediš de-overlaping in izračunaš površino poligona
2. dodaš iskani lik, ponoviš #1 in pogledaš, če se je površina povečala

Rabiš tole: Efficient De-overlap Algorithm in Fast polygon area algorithm. Kateri je najučinkovitejši za tvoj primer, boš pa moral sam poiskat.
En primer prvega: https://ieeexplore.ieee.org/stamp/stamp ... er=7858504 Lahko tudi tu pogledaš, kako je narejeno: https://github.com/Denvi/FlatCAM
Pa primer drugega https://www.mathopenref.com/coordpolygonarea2.html
s54mtb
 
Prispevkov: 7888
Pridružen: 15 Jan 2015, 01:10
Zahvalil se je: 1012 krat
Prejel zahvalo: 2521 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 46

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a Kroko » 10 Jul 2018, 09:30

Obstaja več načinov, kako risati na zaslon. Preprostejše aplikacije pošiljajo primitive direktno na zaslon. Kompleksnejše uporabljajo back buffer na katerega narišejo sliko katera je potem ob sync signalu prenešena na zaslon v burst načinu.

Vprašanje, če je računanje bounding patha smiselno. Konec koncev na ekranu ponavadi nimamo čudno zafecljanih pravokotnikov. Če se vseeno tako odločiš potem bo tak path imel največ 4*depth koordinat. Tako lahko zmanjšaš število potrebnih alokacij.

Mogoče je namesto bounding patha bolj smiselno računati bounding box. Če se dva prekrivata potem bi samo preveril, če višji v celoti "odreže" zgornji, spodnji levi ali desni del spodnjega bounding boxa. Namesto "if" lahko računaš "intersecting rars" in morda še kaj prišparaš.

Tako na pamet se mi zdi, da v real life primerih ne bo veliko worst case situacij.
http://www.planet-cnc.comKroko was here!
Uporabniški avatar
Kroko
 
Prispevkov: 3901
Pridružen: 14 Jan 2015, 12:12
Kraj: Ljubljana
Zahvalil se je: 614 krat
Prejel zahvalo: 1252 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 230

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a s54mtb » 10 Jul 2018, 10:02

Deoverlap za ortogonalno geometrijo je lahko sila preprost in učinkovit. Prav tako računanje površine.
s54mtb
 
Prispevkov: 7888
Pridružen: 15 Jan 2015, 01:10
Zahvalil se je: 1012 krat
Prejel zahvalo: 2521 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 46

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a tilz0R » 10 Jul 2018, 10:52

Kroko, tukaj je vseeno ali je back-buffer ali direktno na zaslon. Kar jaz hočem doseči je sprostiti CPU, da nerabi pisati po pomnilniku, če to ni potrebno.
Recimo, če imam poln zaslon widgetov in odprem tipkovnico, se le-ta odpre preko njih.
Lahko ročno vse ostale skrijem, ali pa preprosto nastavim window za tipkovnico preko njih in na ta window tipke od tipkovnice.

Če sedaj user spremeni nekaj na widgetu, ki je pod tipkovnico, le-tega ni potrebno trenutno narisati. Če ga narišem, potem označim LCD invalid region in ga pač narišem ob naslednjem loopu. Če njega narišem, moram tipkovnico popraviti. Precej enega dela po nepotrebnem.

Mare, bom poizkušal ta algoritem.
Knowledge sharing is people' caring., T. MAJERLE
Uporabniški avatar
tilz0R
 
Prispevkov: 1393
Pridružen: 18 Jan 2015, 00:12
Kraj: Črnomelj
Zahvalil se je: 182 krat
Prejel zahvalo: 341 krat
Uporabnika povabil: s56rga
Število neizkoriščenih povabil: 255

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a Kroko » 10 Jul 2018, 13:33

Glede back bufferja nisem odgovarjal tebi ampak tistim, ki bi z njim reševali tvoj problem.

Ne verjamem, da bi maretova metoda v tvojem primeru delovala.

Recimo, da imaš velik rrwidget in čez njega narišeš manjše. Kako boš to rešil? Katere dele velikega boš risal? Ali ni vseeno hitreje narisati celega velikega in čez njega male. Dvomim, da bi v real life imel situacijo, da bi mali povsem prekrili velikega.

Če pa imaš male in čez njih narišeš veliko tipkovnico bo že v prvi iteraciji bounding box nula. Če še procesiraš od zgornjega proti spodnjim bo velika tipkovnica, ki je na vrhu, takoj "odstranila" vse pod njo.
http://www.planet-cnc.comKroko was here!
Uporabniški avatar
Kroko
 
Prispevkov: 3901
Pridružen: 14 Jan 2015, 12:12
Kraj: Ljubljana
Zahvalil se je: 614 krat
Prejel zahvalo: 1252 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 230

Re: Preveri če skupina pravokotnikov prekriva pravokotik

OdgovorNapisal/-a tilz0R » 10 Jul 2018, 14:50

Kroko je napisal/-a:Recimo, da imaš velik rrwidget in čez njega narišeš manjše. Kako boš to rešil? Katere dele velikega boš risal? Ali ni vseeno hitreje narisati celega velikega in čez njega male. Dvomim, da bi v real life imel situacijo, da bi mali povsem prekrili velikega.

Pač rišeš vse, nimaš kaj, razen če boš iskal otočke kjer je potrebno risat.

Kroko je napisal/-a:Če pa imaš male in čez njih narišeš veliko tipkovnico bo že v prvi iteraciji bounding box nula. Če še procesiraš od zgornjega proti spodnjim bo velika tipkovnica, ki je na vrhu, takoj "odstranila" vse pod njo.


image.png
Window prekriva gumbe. Spodnji gumbov ni potrebno risati ponovno ob invalidaciji (razen če je window transparenten!)

Recimo primer na sliki. Imam en kup gumbov in čez window (transparenten je zato, da pokažem kaj je spodaj. Če je dejansko okno transparentno, potem vsa ta optimizacija pade v vodo ker je itak treba spodaj ponovno risat). Če jaz window premikam, ni nujno potrebno risati vseh gumbov spodaj. To z lahkoto ugotovim, ker en window v celoti prekrije gumb(e). To dela.

image2.png
Vsi 4 windowi skupaj prekrivajo button. Le-tega ni potrebno risati naslednjič.

Jaz bi pa rad sedaj ugotovil kontra. Imam en gumb in 5 windowow, pri katerem nobeden od njih ne prekrije gumba v celoti.

Dejstvo je pa itak sledeče. To vse velja, dokler je widget dejansko kvadrat. Ko to več ni, recimo okrogla slika, ki ima transparentno okoli, ali pa če ima widget transparentno v sredini (recimo analogna ura), potem to vse pade v vodo in je potrebno vedno vse risati. :)

Recimo, velikokrat ko je v igri "TextView", je ozadje prozorno (ga ni). Ko rišeš tekst, rišeš samo tekst in ne delaš rectangle pred tem. Če hočeš spremenit text, moraš widget invalidirati (in regijo, ki jo pokriva), moraš pa tudi njegovega parenta. Če ima parent tudi slučajno kakšno "prozorno" regijo, moraš tudi njega, etc. Invalid region nastaviš samo v okviru top widgeta, v tem primeru TextView.
Knowledge sharing is people' caring., T. MAJERLE
Uporabniški avatar
tilz0R
 
Prispevkov: 1393
Pridružen: 18 Jan 2015, 00:12
Kraj: Črnomelj
Zahvalil se je: 182 krat
Prejel zahvalo: 341 krat
Uporabnika povabil: s56rga
Število neizkoriščenih povabil: 255


Vrni se na Programski jeziki

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 1 gost