My guess would be that the most efficient way to sample would be to random sample from a well-chosen parallelogram-shaped bounding box, and then discard the point and repeat if the point lies outside of the shape. While you have the additional effort of generating more points than you ultimately end up with, my guess would be that the complexity of ensuring to only generate points inside the shape and yet stay uniform is higher than the extra effort from generating those points you then throw away. Of course in the end, the only way to say for sure is to measure.

I think i have the wrong impression with my question - my data is very high dimensional, so i'm not certain reject sampling would work very well? And i'm not sure how to generate a bounding box using vectors $\vec{G}_j$ and values $v_j$?

That is indeed a very important information. With thousands of dimensions, reject sampling probably would not be a good strategy. Another important question is the number of vectors. there are of course at least (dimension+1) of them (or else you'd not have a finite volume), but it should make a huge difference if the number of vectors is only slightly above the number of dimensions, or much larger.