Fractal theory has been adopted as an effective tool for modelling complex and irregular natural phenomena facing in the fields of Computer Science, Engineering, Medical, Climatology and so on. In this paper, we presents an algorithm which enhances the performance of the triangular prism method(TPM) which has been widely used for fractal dimension extraction of natural terrains and images. For this, existing sampling methods are analyzed and a new sampling method which takes their merits is proposed. The effectiveness of the proposed algorithm is tested on fractal terrain maps and its performance is compared with that of other methods.