We develop a General Polyhedral Approximation (GPA), in which the uncertainty set $\mathcal{U}$ is substituted by a finite set of polytopes derived from the vertex set of an arbitrary polytope that dominates $\mathcal{U}$.
The union of the polytopes need not contain $\mathcal{U}$.
We analyse and computationally test the performance of GPA for the frequently used budgeted uncertainty set $\mathcal{U}$ (with $m$ rows).
For budgeted uncertainty affine policies are known to be best possible approximations (if coefficients in the constraints are nonnegative for the second-stage decision).
In practice calculating affine policies typically requires inhibitive running times.
Therefore an approximation of $\mathcal{U}$ by a single simplex has been proposed in the literature.
GPA maintains the low practical running times of the simplex based approach while improving the quality of approximation by a constant factor.
The generality of our method allows to use any polytope dominating $\mathcal{U}$ (including the simplex).
We provide a family of polytopes that allows for a trade-off between running time and approximation factor.
The previous simplex based approach reaches a threshold at $\Gamma > \sqrt{m}$ after which it is not better than a quasi nominal solution.
Before this threshold, GPA significantly improves the approximation factor.
After the threshold, it is the first fast method to outperform the quasi nominal solution.
Moreover, GPA allows for even stronger results on specific problems as we exemplify for the Transportation Location Problem.