Have you tried politely asking them to move their legs?

In my experience, most people who do this are either completely unaware that they're doing it, or they are unaware that it's an issue. Asking them "Could you move your legs, please?" will often be met with a response like "Oh, sorry", and the situation is resolved.