In this paper, we propose a solution for a fundamental problem in computational harmonic analysis, namely, the construction of a multiresolution analysis with directional components. We will do so by constructing subdivision schemes which provide a means to incorporate directionality into the data and thus the limit function. We develop a new type of non-stationary bivariate subdivision schemes, which allow to adapt the subdivision process depending on directionality constraints during its performance, and we derive a complete characterization of those masks for which these adaptive directional subdivision schemes converge. In addition, we present several numerical examples to illustrate how this scheme works. Secondly, we describe a fast decomposition associated with a sparse directional representation system for two dimensional data, where we focus on the recently introduced sparse directional representation system of shearlets. In fact, we show that the introduced adaptive directional subdivision schemes can be used as a framework for deriving a shearlet multiresolution analysis with finitely supported filters, thereby leading to a fast shearlet decomposition.