The analysis of complex data distributed over large or highly textured regions poses new challenges for spatial statistics. Available methods usually rely on global assumptions about the stationarity of the field generating the data and are unsuitable for large, textured or convoluted spatial domains, with holes or barriers. We here propose a novel approach for spatial prediction which cope with the data and the domain complexities through iterative random domain decompositions. The method is general and apt to the analysis of different types object data. A case study on the analysis and spatial prediction of density data relevant to the study of dissolved oxygen depletion in the Chesapeake Bay (US) will illustrate the potential of the novel approach. This is a joint work with Alessandra Menafoglio and Giorgia Gaetani, at MOX-Department of Mathematics, Politecnico di Milano.