From cf24533db0f7cef52bfc8a17128345beae807c4e Mon Sep 17 00:00:00 2001 From: Luca Heltai Date: Sun, 10 May 2020 00:49:10 +0200 Subject: [PATCH] Added another test, and images to the documentation. --- doc/doxygen/images/rtree-process-0.png | Bin 0 -> 7584 bytes doc/doxygen/images/rtree-process-1.png | Bin 0 -> 6033 bytes doc/doxygen/images/rtree-process-2.png | Bin 0 -> 7616 bytes include/deal.II/numerics/rtree.h | 97 +++++++++---- tests/boost/extract_reprsentative_set_02.cc | 94 ++++++++++++ ...ive_set_02.with_p4est=true.mpirun=3.output | 134 ++++++++++++++++++ 6 files changed, 301 insertions(+), 24 deletions(-) create mode 100644 doc/doxygen/images/rtree-process-0.png create mode 100644 doc/doxygen/images/rtree-process-1.png create mode 100644 doc/doxygen/images/rtree-process-2.png create mode 100644 tests/boost/extract_reprsentative_set_02.cc create mode 100644 tests/boost/extract_reprsentative_set_02.with_p4est=true.mpirun=3.output diff --git a/doc/doxygen/images/rtree-process-0.png b/doc/doxygen/images/rtree-process-0.png new file mode 100644 index 0000000000000000000000000000000000000000..8b0506659d71c5c8145744efa4d6260ee1e7f12f GIT binary patch literal 7584 zcmZ{J2UrtZ*KTH*$b_2En-D+{5D<~7h!Z+eRhpDTq1r%lI(gf)UVo;h$6QnB+ zf^-m%iXfs$v(Ql#0m&b}d+t5wd!GB}nM^W!XRr0HwcfRM_TF)p=7#JnLM%8Oj@{Tu z?*tA9qBtBd0W&dLKu-B##)G7#sg*vRPG_{xXtbRV42MJM7>= z<4^=c=}J^I0f$3S937>H(O(tG$uWi^6GMz~LPA0Z4<0l#GxPB92n!3#$;qj$t;H~` zzrTNGW`?0+Sy?${F{NT;cG-G)f=*u?kD%ALRV^;k-{2V9aBhrym_&kvVuI~|o)ZKG z0~k7}mA5cQlktFTyQG zET-dLj?>0dED>w({U{F(<>5gQ#)YC(45iZ19sCHL#<-|-S^yox=nQ-4*g!-6GJTm= zKhQ>R8^EeV=?INZZf$MFO~G{yfj(nUMM;*4gzKSQ3YxE`WJ`diw+2ACq>V%S>tefzl!Xwzs! zdst4?()q|_0p|Y}I08;4e3<|bNlsKTRJAjF`;V#saDy|+_Ue^9I)^3%8J23;(oNWi zM3Dm3&*EUjNtwesj|!EUqtFTRKj<9?Q4hT}c!1CF<_Crj8JOEJsZ;%*rdXEDukEsFIxFx7fXK@-PGqcC!2|yb`zIVYr z{(cA-7_suVeRo*Av^JQ5wg44i6zq#cC!oJ!+#`5Rcr%bEX2Oldryw?cak2*dcQkf` znI(}#;(UQRc;dwOFkdd!#7@BSUxAUD3NQ3!5L*&N%AlF^Qzn+1xW!I=`u*H zUO#0V!ayJs_H8Tc_7jFk7VA`@=o<*Oe>Es7m_x9NNX*0JXgyVI&r%H@s3DB0rCqn6!U|W%$uUY!o#?Ej56>bJV?v)1l zGjW2-3;gxps}4a>R|@AZMkSH`ak4lkkr5Wpg5Z&!ZJ8v;LyQ!pvYkK_7FH98Fx-h% zQLZ`N*eYTz@i=>^K8;A^ktKBRH~6Zo!^lb-K-i5z6|t3W8QC*|r**pA9To297wU4a z6(ATVBk9T#rgKX<@!-{za4^&SFEib6RIJbf$(Mej`0HG-@zsFW{NBPW(AK|l{$FYG z|1VcNh0cSualR<*WZQ1pEBn_65iBdf1KPs}^gQqxR-yA9lghbzWoE=9vL%2CxN=kK zmxfMi5qZM5T8; zfwnZ-C23oS#qVUBQn2J8D=hGpumbtEW`u3EA(ndn8cIvB0meLnKf$E{;H+beMVxCD ziq857-fTUrhw+Q!ebN^}V5(Zigo3@X-1wu~#G>66woANBT#lAsS>C27K3QM>vQLtB zbpZfA#Ihaoi$Rmla)PbIl_`bkN^Z+6#qR>0c;G|79?-DOAGY?GkK;(pSqi2e)P!Dm z=S@<=0nSee;B45Dpt#X57VObmb|d@~!n_^NX&$u-FdmM@Se@urP zy`CAF&45DNo!WUj9DD9|4fS|6COI(~dgz>J%x7-mvT9-iI=6c1>Z|x0H^1@>wX!n- zw|o46g%uc z)V{HsG!(7kj=!jnoe#H{Ag?Swi$SoxC%A_oFoL9FfH@zR9)AFr{t`LLkx5uMsR^(1 z4U&`|)fl=Y8rH0SBDv`B@`9}_W?0P2MNz;cyh;E#HNi0CE)lpj^=W`YQc8$5*165p zX-rkI9VNo+dN#lU?dQISt!e~;VZk8mTwG1m+1WMKI92ig05U`J^*iSj0fqaz?Ghx( z3Fqtnuag;3x?YP}65=Dk>jxetM1F|hTJr%i!q;tjdZKE?iOX^2T}i=wf>jIP z+n2`2`c8@hZ|-vn0u{yu?}*DP<|L(3EaCVn*Q(xAqS9_*iHXZQEN_QYN?A+If0HL{ z1w?@M=0^fj`^EQLIlhzt?Sr1UVLrOp%f=@3^sOZpe)0WN+31fD^(vj7giEJQ&I3*x zit3P75{ab5b9!#oCH)bx>T?hQyn6jIOQ};EhH8GU9 zTsNPDJ`mdXw0FkZj*zvhRT@~kf4WJ0;*6F7Rw4B4>)RN#p1&gyk%|%&ve6R~OXIRayNYh-{tk9+)?pFn& zaz<|GNRW?4b-W)w7l}$aB*LZo+V*bKX-mXqg+yK@wI->1hnU|fdwHwoFl|ST#TPDh z817G-p!k6HCF8k-Qa#Kw=<~>9u%26#2+RewU&aBsITF-e+?J;rhEL^skSq&3SaXeP zyubMPHC20+Z4-;hyycw7Mj3@AZbDhzn`xR*m z#gjJ$FYkF$p`GA+q5rO3_;2>bHQ58&f4)Ee+08g?WpEeRe3q2*`qZSDwwO3=zp3}j zj{7=T7ZV^pVWr4pc_ep3+RK|4yqfqJ%#^+w4GX-TreBRcmC9QB{lb1=ZTvJ7Fy01t zvv%HXu|S+v9qm#ZMc1+(3VE}u>mr*+C620>BFIH=K(#M*Q=GSx)ox+vIcrD$0TivY z#e$coD$0Yu$zLvW*AxY6EwkUJm@Kw8?K154-#3#xfG=;EZIHXg#0AaYHAEusphfM5 z3@(eD3>*`D{&O)^Q|#z?j61)a??5@beIzm0*H;W*5UMN)L0UQ&A(i(0-M|%-gw^AD zllZ0=V2t>~b~y@m@CzxWD(SGMTW%2Y#GW_hyrHK)rWBRp!sKdvfg=XxZ@Xi^L6Xi5 zocY!|a{@?uxp({ovgvpm0GuMx;f_)n>eni(oQ|V6JoDHpf{I$g(dY-flVs>z5=qIz z22#oMKzRf2yN($kHB`($Axc zwC6?~s!iT_w%sM_x#WpI3<%xFikbVx1YPuHesx_bPy@&8Xvc`N_Rp zrqSwuDNsdfl(Ps9OaQlH0$Kpilu*r(lQ;Z;(OsotxEnUj*2v}TFYgHm#`D{U_szFG z&rEyYY`!7`uJ}z-`H1&jRNukzKKjhV#WnD>H#;cZ@tbnsrO^pfUXCdOsA#+(^`7&# zAnz7MJ!>+rXRl!y1 zcjrk;*V_}(VUP6~aq80^k`g<6$9vrs8CunIvEs8*z<`%gIX-idx0+||l6jjJCs?dy zk7U(02dJd)e_SqkqnUH!~)wxzNMI$&wdzu+=B{19m?j0;%qHG96|WKpSL4}9DXb%A^M&GI4BL-&o95VQF340ot36w=?-vr-?wCeC^WkCwKP@g>&n0oBya71 z4ee0l3@!sRIY)}X4e~=`9({6|16UYp z@A@E3mA(FeJr;FstU#sa8Os9|Edk*7dOvKJt~zSr6NX@r88&I2p zr~oSFKWUjrbh{yQ>TVVJ_y_)T(I*20tPYj^H47xmksU1TQ;TH!<`U7-(S3*0Z-JQ- zB~sLaPI2H@_0)C%`2?@!VGnuzQ~9RrGJ0CMTe<1td~kzmZ+uFS2gLKSTndb*$<{Y} zG>rT>*Y0&(8J{Kc&EbIv?+}NI8_((3oOy#g)V@@$KcrmXUlc!+9^Mtv^`a&Jh_bhz z4R6cY`U!$^BD_i#?x1u+o0bAtoN!gC4*)_a_K69^1D|M(&dqqo8qlDa(kFhI-^2;i zYRP8d&z-ycgVg516Rou^YhWkOVt3uS7>%|s&*rIi9Izem6J0Tz<(WmD`G*equiu%z zdBPWbE1?2+$LfvQTZ57LEa?W*osMeQ0bT;4Dele7Y01$Du|NtZX=tYu-i-5Sx-9N9$QYR*J;UMW62kndTFG9iFoB=*-IW#a%UY zol$c|k%Tt~PhmIz82#Aq7X<^}17AQs?;O%lgJi7TSeegW{_D@?a^%TJug@Ave7)nJ zR$pQFG}YPU3&oESxDwglV6npue~0=sCokpap@*|ry@(0rlJ=>ZR7aETp-p*b&z?n| zK4$Kypw3{0r#ZAsiRf3&XlQHm99AEx@REBzl zf2a2#P%%|kp_;H_(~|*}U;CH}8}+DqF&0mWj-isj__8FZ@B1vUn6tV_Tq0Y@1C*VcJf%g56)N-dPmN0 zZ9r$b(|nAM7)AS*Wk~%Y0E)U~qN-6o>?9>k+e#-X;ivqEBqlzDWll$#`GPh*u>fP~ zT5^#f5FM9RHSHJG7*z0~xl~N&!zZErzfuodW6kzw{Ka)W_Vy72B7-mGq0x4paJFKJ z`?P*{5h!ieBV%-G^T1sJ4)KXyE9X||AriEiOg5`+4@LQVhyaU9^MFnB=c~pMkMp(iVCR#s zAIo987pe+*3sJ{Rt^6HzFu-aSm2W$E^~}n=f4R0HQpE4Aun816JFpf#G1u*MyWSCK zQv-)auUF5MY+#LKX2OWF>_L3FwfQcDxU4+LUww7iY0RA> zTfC-^DTKy6P-N${ZOJ_DSF+K#FZBvDz{^3fJIAPk9e=QrQaTFklSmPsLE24@_V)?d zHWnAdE&6mq6j$EdDfDsBPEw?(Z=lklOKNF`(Q)~3LZso~RhiC1* zH1~m`ljU%>zYG&7r)7&hw9tf`4xQ3o;^{y9d{vzG6as_?Z53{xExOW6>3-c4IHhkm zMXp(hMR%Jfq0@TR-|&CIMw1SiQ<4))Q+b83tgp};ky8iYkv4B=o{&vk)}AL-U&yl{ zSz5L(Wrg`kEVBMNGt<@9Y1nMlJ8>)PsM+3nu~s(zY9GGey*~OOum4<@6^%3i?!SV{ z-}v(`0slP5{qIcqky*W-W z3a0#MsfSXMWA2R3riOulyK+kJe0Y<=sQ zk{cGMotf6TI{x5f89^K#905IS+t|nD%`Q3#RYuh2#t#3~6XF8{V|xNM9`C&Hg^ zhnO=X<_1V_WJfEUO(=!a#&4c!6&?>tCW6Y>;l^xI^>NeQUC5$1sFvXI%n)u2j7QhR z_6mss4pE%!(?LjyDU?1DctH5@V{Ch`diGTx<(PCz1 z`QAV+@JNFh*1IfDI|-Tc{Th3E^sSXm`9g9sdTcpxoMaioa#NA0MNyKHik>nP$iW1z%8e?CPmD5l+I~6CTnzYduR?l)cnF#ozUoT9 zz9jaW8j4;4SIg4N{m0kZ zH-6f8yQbW;ULJU9x}lF1U0`{?k9J78%po4QI8|0YU20g@vZzy|c zevN_Ge|p0;JTs~p^2|Wji+xmK1yIePa1QUoo}mh~{N#nU?mq0&H$Die5xOPGJ$&ZL zXrId#61z6<)mK~g-Tk5nXd9d&gpEvvZ^|_5866# z6x{IN>wfo62spcN##ZDQ-%{>s__92_?uw#@XNW1c+8>_GzamtgWgqmi;$(eD?ShOC zoq~yV;rne@eha)UdHA3e?#7E8t3nrkU0!TL5WI4&G+~72tq_wGls9Mw`5cWsuIAy( zQYvfK)79IyGMmqOSXUT;eC{Yxziee>ZP$fpfvcvX1?EJ{QRYJDTsH3NYLmK{Kg_HV z{M+|rs(6?!^zN)u{@^~yM>|0W8(U!k77na#lP7jJ)uIbG21F#6svaMSK(o$1KnF@m zDfK^M^|3lLRq(=SRT2(VJFABQ0u7>xCzmt8n-1D;_jg0@G|1Eo^x-F~ykTctGXA>y zB@Vp#_}=+`YvOX3F7#c@u~h8RJbh1xSK6zMgkO%C+rABNjK?{P z8!y5M<@LUVtggF$Y*bH=LW4$Y2MVo=)|4=AVp<=vNhE@A=eepw zQ-vj{pE4*hnWJM~?_=^E_^PX`9#yJ2?~||c@4dUQ;E6zegj20-J{SWc{0>b8srHD4Jq(Msnp>+CXzIhOZ|pkKSs4g z7{glN5daG1zDTm%ou@4VuS=6@!=B#)$P>rk;^*@xKNw=~ALwFpDL*6om}7M31tA6S zhu9A`)du<{TmN_0BCbS6F~~L&shk--UxOZl_FTZ24Y3b)4_9Bw(#9X`g0xs5pG7;S z9nfkQ%K;!cunye|0=K&rBxocYJLj}m;$QBMx$%Vbv$~gqV)@wx^ql|MYP_$4V1C#lxmqevf$ez51D}dl<@&K9@=hx-f64v^V>@bxn>m1b4Y=9!o;BTBgs=K_M6 zpeP@4nTt%rLyw|PgZb=G=-y8Th_0}w0ip^?fUVh2eFapHmQVU3NHxFHL+~;9)23uC zT@o@Xxw162NNV20z4!g!`~Lr*_w&B1+4o60COoSQBd|j-lh?$bYA9Cz(O$8)i2Iny!+-8;~<01WX_GoG3y^z&do6gaac5*7q*X;PL)mI-^rAiapr0xtfI|cX5HhwQ2o*)BOk@K;nMuPoDw7t(L{TP|4-@TfC}1!dwEFIc z%!l1*RTPsI0xf!+)pKoLmuQ#eDqx5Ba{JcX>dSbX&;f8 zkM2j~Tw&O!s?RJjsd!?-5GapF`UIea5+YF(58P0IVVm19C0w%cj2&+JH58IvYULLR zQrP}jG9n-60F4h22)S{8So!k@b@KZ{2~uyi(+&XLCt@+He|h>-{Y4u~eXnx@62z@K zdj~mY$4iKzwjtj>pSplBSg?S9_iA1>uA033%+w?srkvScR{iv~cAm$;1X34zOzK{( z|4;6Z*b;~CYKMd^7~!_(cE-H#@qQjh=4(%L(0f`a@DtDbn*Lwlw^e*V69~kz0vWjf zv@cPn{y0Mf55MPZ{FxBuzj`f^(C1Qd=9i!JZ`zktBB{tZeBHl;*->+ykDegCv|2!=Da*S9u>Cp%|})kH(Rucf}y7C1$Q>o zlMpxFw#iLh64mL+m-`&^(m%Ybp(QCP5`FKVNp_h>k?iu%nm16mgxQ*@rZx#P0f_cxHFE4tP_POMqB&Z2( zFd|`t&SpTJ-3iFNJ?VlRO={S_zovRJ_iNEkr<$vy(_dScHkpv2R;wCrasX3itn4td z{9PydKdFFo5t1T*#^+~FZ*So33kXz6?3rF-UhX~K#G$DX9dg|P&VWnZX5xGIt@TGI_vCL#gbVo0XzJ7XAPlQUI zfhl^Vg)cNzjO+TctM-&J`uS-*D>QRwvc^&v%=L2r?1-+h80`pkn6|PD83-QwcnIV! z`P6+^i%8w>^#>-s>HGe1NFtV*$8g@`?gdt~NpZs>7d9sT<;avaERwo$yrfL6cC_Pf5(UkSw9m=X*JP0z zjxyDc;z@mGWIi zO4~_3(9FzTyGM_=uRL=$v828N>F^Z!PI&obD)>5&c}uHb%DW?HhIAuy5lJ{)WufNO zS53ftu#3gS9F5mKk#mTQ7VbKLetzr|NlZ8Fu#yHPh*J{t2DAL26;BaM3l!TF_y%C54v^?86 z=0>7dKksaJjs!ZhL!2DZoj1XPWGsZ1a8)Rc3mgbE-wj6W(42MlwBsf)%7!On-w*Z_ zCSe-OD)h$Zt=YYIZSb#^&cr$iwUi@n@rXXGNSnGcQYFyjF>3ob_FRLO)J>AAxDOt% zY95qSq@G{5mb3Eq)@!r2$z%l|%MAXfs$#> zGy0LmfKl zaxs)CXNI19Zr%N=ZSiKELjySQ?m{%cNyM}4r~W3kLQ4nVu|fuER`?>&J#JxL z1n@{pXcVwS)WwE`}B+zFQQ-K8dH&Ks5Bk>FCSzv|Zz?$A+vPq#~hGQj~p8eDAA3DIf zyGb1b@xu@>xLri2C``J6uTNmEs6sgNmA+VEf<#iu?^>hy&hls)vH}1+ANBzr+WNny z{diomNVErjt40ni{Q53o8@mpv^p?VT6?$iEq_twwdCLfv4CF|kz%r5QU~)?aj5zt| zrov}4^y5C?`!LX=edMJ;qEMgy+a~#Yr*(@|Wi7qJ9IXkA5KYtT968_A8uaI*e4Gss}8&C6Smb?AZG>PyH_%TM)p z-_P!&mzkz)#|nk7#0q3<)qS8pea24t ze0K1fIQ#Fhe3vhfW8ze1rtikoM&gAF^1LhO_XCy59F4rYu8ov8o{l-^phRE3(o@Pl z?8*`_WfTbZJZ#qBO3ludU^G!nZ$>`nZ9Ur~nMiyw~e7<$S|5>!%rEaZA z1mI z2JrtOn!X}+HshI{1~dYI6^pxGtjVjt&<@gotQDfWs#khVe)g9HhkZO!T z54uWVN^)=9A~3X_deuv#*EU8_#~9zm=4E;J?d$+Aa3IwE`6yG2v3xi`XxFtG|I!Rt z7b{WPIDapX>K;UdM#LqpvD4J9>YF` ze8ALIsoi^r+VVcIL4a!UVs9L8RahDF4I$EtB|=DppTr2jcQ!zSz&N~Vga=oOwU2>Tv$%dltDvq_TqUoS^smE##M1(cTK6G(E@>zpmXKa3pgFfx!iO z6Y2Me)b<-#5pQlrh9qo%MHWKM@#`#q=JLT2SZR^vfhm4*i1zS7p!W6Xk(y!g$371? zbGHXH+5-i{i=Jh7$M6MlLFHQa?<1)n3Y>t&`@3*pRvvacVp$T@ZWSYgt`qGbps^ot zQhC`^iRdtQYl12kkafm2m8MTSu*))tjPe_yTcBnksH=>ff(K$T^?FBCSn8Z6A!%y5U8*ox@zMJ8 zJlP3Y;T0U#Re(L76>nn~9lUBjDfRUFP9hvG>-Z<`O|!IMXe5Mm2+yctEbO{K_P+K}$@S1Eniqufb&=w#T`ipBmK*xh$ntGodd^?lOp*yQN+;lPt znUKri3%W-o(KCotvtsatO1IuwWY2=$@A5{>x~Y+^_s2)^%Gm?*@Ea|kEfzT(x(3E5 zTqg-}g1ghHp3Ro%Z#Tz~HU@O>is;n5B}_%2V^v%IZ?N3e<&Op@;rnGRg&bg2>&WN->rvAj>K{wW8q zYW~OZUZ77-QcYe5N8@-Czj{9ai1YiTE$f_-jm@`+cN%dN?3>xSqtp?-_(at62lhYO>r9X_`R6DuS;gLwj0YQm!T~9O$xztM(7>@6p~YR4rt!Mh$eWJ`<}jm+>yEj ziRS0=A5GJ;0UgOrx{v51`5S9B2hknNoIoV;iHKjWzmVE!M2ui49t_=dV1)60G;O&+ zKuRMcT{Dmt;s?!SVO9zjN^~6wao=}TZr-XuoOrg(`mBy8Kp3?n>2#M1`&1GvI! z7@#x8k5vVE7z`~u8?0OToO#C&`y%)ME81~`_Rc^_Wym!et7;2;chIhJ$KbCV0QjQ` zRoJKAC?DW*N*s9Rk)!mZ<;>1I2@D9=FhzS(NL15bmpLd($=I833x>xS_1#_axWErxkE^;! zq*@Tv3?*EAzVAuu3j`XH)S|9VsIG?zH0|ITu zd(VewSP>XKb=nmPUF(&FVrCCRqo#V>VOT$>5=cH%afFh!Yfp%f^1$22B;vMz>mp)J z$NfJS{TDyROX+b6`OS_K2z+ufnnjD)1BmU_kO|g>-0F|Lh8ULx;{_$c=+N~tfBr*A6@M%`aA8!hruDozs6cGWYWa^$S-xzKK{Fr(Y`!){AAR&U~FL^!;%j`1fY+hNPe)wwCLSiIZvC@W#~A)OK%$ IF*WYL0PZ}CvH$=8 literal 0 HcmV?d00001 diff --git a/doc/doxygen/images/rtree-process-2.png b/doc/doxygen/images/rtree-process-2.png new file mode 100644 index 0000000000000000000000000000000000000000..f8fc04332fc01af3a64db970c46e6b29ed938536 GIT binary patch literal 7616 zcmaKR2|QHa|M%SMj%EfmX2uf9C}byFWxYuDeJ$H4Tb4|bgt(RnEw*e~rlM5TB$1*n zN=T7puP@&slqHpHndkccf4|@JdtT4$dFFLz?m1^Z=YG!locHJbIrno?ZLLlCNFpR0 z4##I^y5Am$0}&h!7$tCFE#MY~KCH6S*3!|K!{J~pEEa3yhT?Dt2gPx4v$H6SYiq+9 z93A7JbQ}Vs2uFp1q~mZfg5w~ZI8JZ5oE+8_9__~ZiHL}(si|36S^4?-#l^)H6cjvo z@Bl^8&d$#9@o`MWysB!(Y(~|<#Jtn|D2FrqA%RodbZ>T+(~rZn;e4>)xE<*`l+s=P zsi$w<%EX3(!@W*<^A)!-L=NuFTMjLo6K6Y*ARJ@d3UXp9H)?+3d}CeEqhy|6zeZRH zol}mRO_mF2Lx1}8DXt{!nESa6;}Dsq2g7i<&CfT!z-9T(qBz_(BeVSm zj*&$(#e9X=<;cbdi@#R)R}}6?^(Tl7T|8>N>BPh4KvS=M0#P%5)3IEM0ot}X zQ`<8%74#Ds>a3A&jJk-F zzpa2#aR5vxhha92K*$Aw`2Cz!PTu!Y-LjS)geCqPZq7f5!CDF(JOd_qh=6GK)BgA) zkCElu)<9P#&%*_Kw>U6sXv&TcxVJl+llgRq)_Mw3I?)7vBth=a6Y-8wYud-N2fW!& zBe(91VI@QETOb{wcg`k(H%&C42JZi^v<3pv%7anRH_yu>Q}^`B(>uEjkH&!Z z*1H#qHJ`pNYiNPM)^FGEqC0*JgSna_V4sR98pD?=zvIUzaDqw(odMtqWa(V)#YNHE zbr%2)(ekwlr1AFyGnX&$f+%e8gZYj=sxiyY?h>l+-$xvfSBDzfnjxK_b+0OUi;l*R zk)#`JBgs*SPKVq(uHzec2#+qB@W|xO9bM!+YlUbanYe`8_>%-BAr_|-5M7rLF)+eo zTOT2RRmOV%2RHGuqo=~fp7%)fQEV-4G!bR)JwK)CeMN$P-3pB{u06DPzC@WZP*im` z_-fIaK+q803~iHOsdL*$C_%gkLT1Y9%QLhOxsaJs`to$jyx52g!^V&3VNGT$TeU9& zfHHe85OVgBOqC^Uu5AQb<2I(LC2yY4}|to9%s3Lz#O5YZo;FIzXUMjk?5?aeuPM_Q#=E)$|9%s96~Qj7@)^>=s=xS zr|7VYdyEN4x}#x=%B~@ZT0C-R834)`O`z!`=Pbq(FK$4HHf)4Gc|>QdPR;6qn$0h{ z0j>pbaqi1Sqy6nFxuk&yGriCH>GYIqF87`9)_@)I*J`FyD7K{UKWLUcLo;ur^lBq7 zIsBBj?+vE6FlIQ2?G71<7PGqnC0Y8=^7dmO|%wY_O=C*gMm4PnfGNn0d z*!x_>>ul)r!-cGabe3bWqbEO8aO0U0tN~9mjpO^x4;iArdWn0L!aL`9_A*_B39hm% zM+k*QL&}!q6ZT6mt`?98+HLEh|zaH*K1?i&#$E;x&)1!D@Q~17P z@I|PhwFL@JFX?P+X_kKOxo%D$h1M49#CC+afvp19DH%C&UoLF4EAb38|Auk`+jHb! zJa&VE_Z8WYRYc+jZX7nl6DnM)wIo@JNl4K>Vw=9-W&MD1s}(}7=KUpwB;JzMuSsuP({8pS8c0gDk9gJR>u8GLeq4PO-0@z$=A*xlyS0r$~n7 ztPrUmp$1Txy_s`l+hB$9YrVG1x&cDW?!^aUn=#kTkqa}BnHY^7X}^Tb=&SbV?TS{~ zG9=DT40$(RaP-)13sg~7%~1I+bsr!>-zAXIZ@*-Ipn~=_CR_hgbBP39xfkj+8+vMv z<~k6)ROA^Bc}Gpc?;#=DEOT_CxX=tOoAd?yb}>9W3XxVRhWqzUDBS46m3M@^c&Ls>#BeOg){>VPbyyAoGLdF> zEDu3gx%lU3G6~pa`}_SiT0;_Tx*F6R5j!u$j{V?w8~K%(Q8)h*KXQT?aCN?Xd_Y5r zrC1h@bB9+`)8?nrf5xAmx7$WkELZI>ADA1A&Tdad{&wTEAE$e#&Aj=`n94p`r}=6s z_m%)t;Welkl0SUqLb?GunbmFBlisdQbY|zhorij_DavLhF4%(yeA{E`byv+U7a_Eo zc*Frx5Oea{*><(a?Xou{)e!unANgLLGpwrGlo{bGEr<-*5L_qp0MR!Wze2%UN9?mnI>>ov$j1JMu{ zoz^;na8$3tAOi@xMP+A2<9W5qSrSY%-KmhN4>4z#wnjb}>7)?dcxpbH8^t=XfpoWXi;Jc6fTFqZN@jPm+LpFa2 zC$cCCeU=2dALiWRDXcMdJHtvQ?e#{caFrqkPHRgR<;b8%cJR+GRdcxS2$OtHsGS&@ z`{G3yHRE%95|>Wi1(%&t3|qDRuy@DZaSyPMla<{Iyl~>eZ+m$NkZ=9%0o1vJg+p4- z8fw6vG`I3bW2@~Mh}&)qa!?L80r;ZkfewXzCILYye)LiGSu5C!_RIJy)mB)L!qnSB zVM|=(-N(iEUBw27a zaW97Sk#0&xRf5&iLog3s`GwqqzA+H=$OV;)!t-vT?V=CvW|vDaAiVNnC$UxY&zlNl zm2SeH4q9YGWe;A} z+#1Tu5mqe7?kE0zEl}W zHGF6kkDOw9ppR*{FNis-*r8=9KFsi+PDkaSZ+-#bcHJALIi#DT4~R26*|sYlQ)6qn z>kbmf6F-+yQdh~&l)QnlACM%+q32uVEsE_rpB1FAruXdZOQLJ$4LtDbm9hXco1!A1 z^07X+n%Nnfo`o3mXPwiskWr$D3O1Xyp{1|N@?_l~acGZ9n#w*4m4jth8| z5hNyl+6ld_kd5~-;<*Rb)drysux12R?8q+0YsLexy3x!Vo7`I&#sz0XFsO?X=W+?Rt*El_WqO9P_u%$00gA-joszwek`R3&m* z)KQr=oT3MOsJ2Ecj82PyBn{ec)5?4)#&U%;=($sX-EdB9?_acM@x?>}U>u0=6b@5A z7cJ>rS(I>Tc?sw<1gl#FtCqF}3^ZgQ;nH-k3On@gl6Yj_kmf`bc*EigMElFs`s3sF z-qu&|B7wyF4{Yo*5U1b}$`iff8`=^?`YdCRLS#ipM$xe@#BfFWOnIpurIhQ72jKU90+TC z5#3>91TSif8y^3z=TuWB3s?!q=iItuiY|2bRHRqFr*uE+d&!+8W;{|FloOnx!w0zG za}L!v_c_eF0)Ot8{fLW*{Nymd4*>FxUqMbMISthtvg~Rkp*6)K%<;-k!S2jX+gWs6Qda9h5T zzJgbnDwC$yUnO4I1i0+BL78H-nH5&c8_05d7+uX6O>%?*g6r8GjQ0iU&E+Dhp+(3G zSUnTb5Y3gO51V3vVsvd^FeV|*=sn-u6QF4guQuo{FHaEz`sZ+p-G|oqUeo+@kV}HKyN*-=09&eWN}s5z4oUn`dW*u2an=zLgcKID3Hjn{ zXE59vnHKHx?GwuSnr$h=sCkn3&SuSDJkVn#y%2f+vhFf9BL*D0c#%_#WZwfM7=+Xx zWt}UAC(dNG^9;PqhB{j{pvp2UROf~r6A8R3(gi9BtOgYeo%i-M46$tB@Dbh^(|4yY_Sm@ zR@a90k8Lajt7^suc2?B~+LfL1kniKr^6vsE*#cx%wQr7Baum-^$nTPPY=QEIfUS8o z#o+W4$q&|qiubjWtSeW`iIdNGyA^kl+FT~MO~(4__gqU1Lgj$$Q!&@L$@44=G-l!# z!FBR&go`rcsu5v{R;x2u=RL5^Os)N)&iC?2WrIs&=WEZ;9Q%vZLt(~AaV%;j0P*B+ z9y^Sb?4t0&H(gNs?aqV>MIxYVFVC`V^OD1Nx+zr3KiPi-%o-!M-KEG;yO*qGtl{5o zQpcbxJ8ng;vXRp?;G+5Z3F{QKMUnY$a*w!q-yvR8#zHBT`ORG?1`VzY0=~r;YA#oS zxv@{^jGcD2`HbXe8T@{m0jD8+=g;?r$k@Smeg2Eg>1TRIsC$$CdYHNSsm}3klY`qXVsZ7gALeuew1$Es|3fgw3BJ*WQxn zH5b5%BQN(z4-0(Q!8qosOPsvhzhaiTsYmTVdv6q@ z>6H|OYaSFV`=l=}#rkgC5qgn*@bhYwIlA;THv>szf+e5AqH*5)uFk|!G<{OJJTKp&-W6J5*m zYO;o;2Gdfc7%X=MM(j?Roh)uB=g|&U#QCKwkMHU`p#eP;6-uxj9Q`9uAboBd1@PG7 zqdn&JN+kG!^3I)>7OQjgk8ej=2T;;_VLf$%40Ij6y$z9M3=u%R%~t67qdL)T${KcX zE#=dUtp_i)+n)}_&{L7Z@HO00Y2|DzaK>dp>WY`xlz+sqEaaY8>m^elsXr4}{rDkx zY5TR2OCc;g*bz+1v0UlmNxRf36^cOdv%rkJ}o;%q@4I&f*1$(UflM=I_JGYtla1kfZxGOYo4)Ez>*McBhUhM+)CY zcJ~xJt_WsDQ`>2jj7#xZX*F6~PkxF>NU=AC#|+RT3!w)I1V8V4!0&W)R3yV|vmvaK zx)q!V)oD}S3>Z`))m8RJN=4~@zu=)0)+&o9T58!r~e5GkDHLy+5{LFI)T+AuSydn=mGmVd3tpEBOni1 zbi-Bc*vqbyHil#jbghAjJ>1;Xha{PsJMZEKG%a=yMgPp97w&Mr`bJK z6o-i`054pBL`gZsB^(oVP;Vf{BP?)?7ThyOaI|T-3{F47E5vexvGLr%J8EbUC_>GX zc|Wm@3dQKAAqVQYYt+7MgCL=e3|vQf@o`X2=$J9^RcSS0EAftk)A$)+r)|q{d2jS(|-_^*8o8)<(B}jes2;#qWoYLJTb#rudasN8c z-ab>#6|!^qkIlgEYI9hOuq0bMIUw#Ek94G-G6g%XZUUYeodJgy5|?tH|2D3DIw7J` zwP>6%$1@_!A_e)ZQLqOGfO7r*K6zhl&>G3AWTf*qt@f>Y)y0L1$yAcOCewtn&|`=&AU~32%4z?Zwp2Lr4GUDF*iK6Y6AN zjdxMAKqI~+Y}LdB50D~X*E5p&_!EF~OE|!Ub4$MT>-U<^46D>AP z++f0!4IGlm3i$ud_BPqm>8>O!P2B$HPROfxWbR8cRD*wQ)FOT(4);$!_&*Z=clQ%5 z;!=YN6ITt;EzFiu-=TjO#cvG%yXX=&@b6+C^*^%x5B^gWax6JhvxN_gMV>snR_7Z) zp641_lo}T^N<_pNv-qb_;x=IN5Oe*6KB(qZX7p&z`I8Fu8(ff7a>NRp-qS%Q ze`XK|Vo25$m4-EoyPJmVeT9(A&%r}sYvIf<{2!CP>1L!tw9rfmIvI-**4Hn9s_{yX zFn5X1N18<6`~n}ZZV8Lny6(LVC!2tLdH6B+33n30;4MUk1_zY6fhL?e(e#@KO_DBb zy=Hb!fE}}sfHl@YK5u0Gj}Qplwi5I%9l>NWnHQ$aKblX!2eeCqL$b>T*z$L@`MX-d z<37BAfwCTO=~7$}B?EkoK?lB$e4%j`^i>x$Sj0mBy+@H1Gp$J`t2f~tl{cL#gCwa0 zlU9r^l5!A}toKC;oN4vr7^`4>6L9C9N)p0?^nYNnMf(KUvFm*`G8LUv7fN1IT)4?t zSFp4J|1R*e#bIEh;dADg5_I9jg@f!=EbRe}WFQO`1;A>8W=SSnZk#@-6Do@CoZ%r5 z3XfXDS`?-cn7~ilegHujN}~G3B{rEoc8L)5gWtNz7vRZD#0F(+mWR}y33gZK0Sx%< z;N5@G>G`k{Fu1D;0-9*g8?*xhq29aP67-4|DHc=6{R;9qcK-u1IR|^DEFQQ#%#WGP z?lST`W``9#W=IATC|K5W*h5KLb(es2c^;8&4FdKkI=42Bf-t`dY6CwX7cpM-!Uojk`NFo2^!blx+wGQl! z-6atlMjI*rqr^+%WSp?KAg0?B9{ZEuh~HP97$NQmD|>sQhp#-cip8O+fo z_!BXI+R$GGcGR_y$>BZOh)@3U=dm{$!HiAV!VUOS){Kav5cGQt|G8^z>vwM$n`uC8 zzAkb3Np~C;euy$3(&jxwN4V#?6MnnMVJ=ipyrqT<{4YB3!F(fS=7bM+;u0WLiueR! z_}FZXe!l8YARMEgNM6IZc+W;u{1;cqJBT-aDr)w zH`x$ogPc$(d(|5=2nI>)Ozc0JQ#n%g5As!cuzl6$IqLVr<{~$Ea7?lPQ)pvmQ%1xo v%g*WDi9!BmK*0TfJ~8QW4T6QXiFG$uH>Avrt@qzGWF-7AK?mQx literal 0 HcmV?d00001 diff --git a/include/deal.II/numerics/rtree.h b/include/deal.II/numerics/rtree.h index 339c7d8343..b230debecc 100644 --- a/include/deal.II/numerics/rtree.h +++ b/include/deal.II/numerics/rtree.h @@ -264,7 +264,7 @@ struct ExtractLevelVisitor * Since an RTree object is a balanced tree, you can expect each entry of the * resulting vector to contain roughly the same number of children, and * ultimately, the same number of leaf objects. If you request for a level that - * is not present in the RTree, an empty vector is returned. + * is not present in the RTree, the last level is returned. * * A typical usage of this function is in the context of * parallel::distributed::Triangulation objects, where one would like to @@ -277,35 +277,41 @@ struct ExtractLevelVisitor * computations. If however one constructs an RTree containing these bounding * boxes (for example, by calling * GridTools::Cache::get_cell_bounding_boxes_rtree()), and then extracts one of - * the first levels of the RTree, only a handful of BoundingBoxes would be + * the first levels of the RTree, only a handful of BoundingBox objects would be * returned, allowing the user to have a very efficient description of the * geometry of the domain, and of its distribution among processes. * + * An example usage is given by the following snippet of code: + * @code + * parallel::distributed::Triangulation<2> tria(MPI_COMM_WORLD); + * GridGenerator::hyper_ball(tria); + * tria.refine_global(4); + * + * std::vector> all_boxes(tria.n_locally_owned_active_cells()); + * unsigned int i = 0; + * for (const auto &cell : tria.active_cell_iterators()) + * if (cell->is_locally_owned()) + * all_boxes[i++] = cell->bounding_box(); + * + * const auto tree = pack_rtree(all_boxes); + * const auto boxes = extract_rtree_level(tree, 1); + * @endcode + * + * When run on three processes, the complete set of the BoundingBox objects + * surrounding only the locally owned cells and the second level of the rtree + * constructed with those boxes would look like in the following pictures (one + * image per process): + * + * @image html rtree-process-0.png + * @image html rtree-process-1.png + * @image html rtree-process-2.png + * * @author Luca Heltai, 2020. */ template -inline std::vector< - BoundingBox::value>> -extract_rtree_level(Rtree const &tree, const unsigned int level) -{ - constexpr unsigned int dim = - boost::geometry::dimension::value; - - using RtreeView = - boost::geometry::index::detail::rtree::utilities::view; - RtreeView rtv(tree); - - std::vector> boxes; - - ExtractLevelVisitor - extract_level_visitor(rtv.translator(), level, boxes); - rtv.apply_visitor(extract_level_visitor); - return boxes; -} +inline std::vector::value>> +extract_rtree_level(const Rtree &tree, const unsigned int level); @@ -401,6 +407,49 @@ ExtractLevelVisitor:: operator()(const ExtractLevelVisitor::Leaf &) {} + + +template +inline std::vector::value>> +extract_rtree_level(const Rtree &tree, const unsigned int level) +{ + constexpr unsigned int dim = + boost::geometry::dimension::value; + + using RtreeView = + boost::geometry::index::detail::rtree::utilities::view; + RtreeView rtv(tree); + + std::vector> boxes; + + const unsigned int target_level = + std::min(level, rtv.depth() - 1); + // There should always be at least one level. + Assert(target_level >= 0, ExcInternalError()); + + ExtractLevelVisitor + extract_level_visitor(rtv.translator(), target_level, boxes); + rtv.apply_visitor(extract_level_visitor); + return boxes; +} + + + +template +unsigned int +n_levels(const Rtree &tree) +{ + boost::geometry::index::detail::rtree::utilities::view rtv(tree); + return rtv.depth(); +} + + + #endif DEAL_II_NAMESPACE_CLOSE diff --git a/tests/boost/extract_reprsentative_set_02.cc b/tests/boost/extract_reprsentative_set_02.cc new file mode 100644 index 0000000000..f49bdb408c --- /dev/null +++ b/tests/boost/extract_reprsentative_set_02.cc @@ -0,0 +1,94 @@ +// --------------------------------------------------------------------- +// +// Copyright (C) 2020 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE.md at +// the top level directory of deal.II. +// +// --------------------------------------------------------------------- + +// Extract a representative vector of BoundingBox objects from an RTree + +#include + +#include +#include + +#include + +#include +#include + +#include + +#include + +#include + +#include "../tests.h" + + +std::string +print(const BoundingBox<2> &box) +{ + std::stringstream str; + + const auto p = box.get_boundary_points(); + const auto p1 = p.first; + const auto p2 = p.second; + + str << p1 << std::endl + << p2[0] << " " << p1[1] << std::endl + << p2 << std::endl + << p1[0] << " " << p2[1] << std::endl + << p1 << std::endl; + return str.str(); +} + + +int +main(int argc, char **argv) +{ + auto mpi_init = Utilities::MPI::MPI_InitFinalize(argc, argv); + MPILogInitAll log; + + parallel::distributed::Triangulation<2> tria(MPI_COMM_WORLD); + + GridGenerator::hyper_ball(tria); + tria.refine_global(3); + + std::vector> all_boxes(tria.n_locally_owned_active_cells()); + unsigned int i = 0; + for (const auto &cell : tria.active_cell_iterators()) + if (cell->is_locally_owned()) + all_boxes[i++] = cell->bounding_box(); + + const auto tree = pack_rtree(all_boxes); + const auto boxes = extract_rtree_level(tree, 0); + deallog << "LEVEL 0: N boxes: " << boxes.size() << std::endl; + + // Uncomment the following lines to generate the images of the documentation + + // std::ofstream ofile( + // "output_" + + // std::to_string(Utilities::MPI::this_mpi_process(MPI_COMM_WORLD)) + + // ".gpl"); + // + // std::ofstream all( + // "all_" + std::to_string(Utilities::MPI::this_mpi_process(MPI_COMM_WORLD)) + // + + // ".gpl"); + + + for (const auto &b : boxes) + deallog << print(b) << std::endl; + + // for (const auto &b : all_boxes) + // all << print(b); +} \ No newline at end of file diff --git a/tests/boost/extract_reprsentative_set_02.with_p4est=true.mpirun=3.output b/tests/boost/extract_reprsentative_set_02.with_p4est=true.mpirun=3.output new file mode 100644 index 0000000000..ba95e51838 --- /dev/null +++ b/tests/boost/extract_reprsentative_set_02.with_p4est=true.mpirun=3.output @@ -0,0 +1,134 @@ + +DEAL:0::LEVEL 0: N boxes: 7 +DEAL:0::-0.92388 -0.92388 +-0.297335 -0.92388 +-0.297335 -0.297335 +-0.92388 -0.297335 +-0.92388 -0.92388 + +DEAL:0::-1 -0.382683 +-0.603553 -0.382683 +-0.603553 0.707107 +-1 0.707107 +-1 -0.382683 + +DEAL:0::-0.748551 -0.459948 +-0.34467 -0.459948 +-0.34467 0.283171 +-0.748551 0.283171 +-0.748551 -0.459948 + +DEAL:0::-0.382683 -1 +0.707107 -1 +0.707107 -0.603553 +-0.382683 -0.603553 +-0.382683 -1 + +DEAL:0::-0.459948 -0.748551 +0.603553 -0.748551 +0.603553 -0.475682 +-0.459948 -0.475682 +-0.459948 -0.748551 + +DEAL:0::-0.396447 -0.558058 +0.0861675 -0.558058 +0.0861675 0 +-0.396447 0 +-0.396447 -0.558058 + +DEAL:0::-4.16334e-17 -0.558058 +0.5 -0.558058 +0.5 -0.292893 +-4.16334e-17 -0.292893 +-4.16334e-17 -0.558058 + + +DEAL:1::LEVEL 0: N boxes: 7 +DEAL:1::-0.292893 -0.292893 +0 -0.292893 +0 0.0732233 +-0.292893 0.0732233 +-0.292893 -0.292893 + +DEAL:1::-0.748551 -5.55112e-17 +-0.34467 -5.55112e-17 +-0.34467 0.603553 +-0.748551 0.603553 +-0.748551 -5.55112e-17 + +DEAL:1::-0.381282 -1.38778e-17 +0 -1.38778e-17 +0 0.34467 +-0.381282 0.34467 +-0.381282 -1.38778e-17 + +DEAL:1::-0.0732233 -0.292893 +0.292893 -0.292893 +0.292893 0 +-0.0732233 0 +-0.0732233 -0.292893 + +DEAL:1::0.5 -0.707107 +1 -0.707107 +1 -5.55112e-17 +0.5 -5.55112e-17 +0.5 -0.707107 + +DEAL:1::-0.0732233 -0.0732233 +0.292893 -0.0732233 +0.292893 0.292893 +-0.0732233 0.292893 +-0.0732233 -0.0732233 + +DEAL:1::0.21967 -0.0732233 +1 -0.0732233 +1 0.382683 +0.21967 0.382683 +0.21967 -0.0732233 + + + +DEAL:2::LEVEL 0: N boxes: 7 +DEAL:2::-0.448223 0.292893 +0.297335 0.292893 +0.297335 0.503141 +-0.448223 0.503141 +-0.448223 0.292893 + +DEAL:2::-0.707107 0.433058 +-0.0991117 0.433058 +-0.0991117 0.980785 +-0.707107 0.980785 +-0.707107 0.433058 + +DEAL:2::-0.19509 0.433058 +0.316342 0.433058 +0.316342 1 +-0.19509 1 +-0.19509 0.433058 + +DEAL:2::0.292893 -0.448223 +0.475682 -0.448223 +0.475682 0.34467 +0.292893 0.34467 +0.292893 -0.448223 + +DEAL:2::0.414752 -0.5 +0.823223 -0.5 +0.823223 0.336167 +0.414752 0.336167 +0.414752 -0.5 + +DEAL:2::0.158171 0.258502 +0.55557 0.258502 +0.55557 0.980785 +0.158171 0.980785 +0.158171 0.258502 + +DEAL:2::0.417474 0.224112 +0.92388 0.224112 +0.92388 0.83147 +0.417474 0.83147 +0.417474 0.224112 + + -- 2.39.5