Generating promising hypotheses plays a critical role in the success of multi-structure model fitting methods. However, conventional multi-structure hypothesis generation strategies do not exploit the information derived from the results of model selection to guide the subsequent hypothesis generation process. This leads to the problem that these hypothesis generation strategies are often computationally expensive for generating promising hypotheses, especially for heavily contaminated multi-structure data. To address this problem, we first propose a guided sampling strategy to accelerate promising hypothesis generation process by using information derived from the results of model selection on the fly. Then we present a Unified Hypothesis Generation (UHG) framework, which effectively combines the conventional multi-structure hypothesis generation strategy with the proposed guided sampling strategy by using a Markov Chain Monte Carlo process based on a cooling schedule. Experimental results on public databases demonstrate that the proposed UHG achieves significant superiority over several state-of-the-art sampling methods in terms of accuracy and efficiency, especially on multi-structure data.