A well-known, previously only 1D, algorithm using the Sparse Representation of Signals and an iterative Block Coordinate Descent method (the SparSpec-1D algorithm) has been further developed and tested in a 2D spatial domain to obtain the toroidal and poloidal periodicities of magnetic fluctuations in a tokamak. The tests are performed essentially using simulated data, because we know what the answer must be, and therefore it is straightforward to verify the accuracy of the algorithm. Two more examples using actual data from the JET and TCV tokamaks are considered to test the algorithm in real-life experiments; a further example using simulated data constructed from nominal test cases for the forthcoming ITER tokamak is also considered. The CPU run-time and the precision of the SparSpec-2D algorithm are studied as function of different analysis parameters. The stability of the algorithm is also tested via the introduction of random errors in the input signal. We find that the spatial-2D version of the baseline SparSpec-1D algorithm accurately finds the modes in the 2D toroidal and poloidal space, provided the set of magnetic sensors used for the analysis do not have a (quasi-)ignorable coordinate. The number of probes and their position are the key parameters that must be optimized for finding correct solutions. The main difficulty, as for the baseline SparSpec-1D algorithm, lies in dealing correctly with the intrinsic measurement uncertainties associated to the input magnetic fluctuation data, particularly the phase error, and this has been already separately reported in a companion work. However, the required CPU run-time for SparSpec-2D is significantly longer than that needed for 2 x SparSpec-1D, and thus SparSpec-2D is effectively suitable for use only when the 2 x 1D analyses cannot provide accurate results, which is the case when the set of measurements does not have an ignorable coordinate.