My home area is Austin but I've traveled up the east coast a few times and through New Mexico. Many areas of CA are hard since there are a lot of NIMBY anti-homeless laws. The midwest has a ton of BLM land so it's one of the easiest places to camp, so long as you don't mind being in the middle of nowhere.

Middle of nowhere is rarely a problem I agree from my personal experiences too - it's proximity to particularly small towns with bored cops where my friend has the most problems, including just driving through. Must be a visual thing, maybe he triggers something with cops. His wife is gorgeous, maybe that is a stimulant also. Mileage may vary etc with personal experiences