Antenna layout is an important design consideration for radio interferometers because it determines the quality of the snapshot point spread function (PSF, or array beam). This is particularly true for experiments targeting the 21 cm Epoch of Reionization signal as the quality of the foreground subtraction depends directly on the spatial dynamic range and thus the smoothness of the baseline distribution. Nearly all sites have constraints on where antennas can be placed---even at the remote Australian location of the MWA (Murchison Widefield Array) there are rock outcrops, flood zones, heritages areas, emergency runways and trees. These exclusion areas can introduce spatial structure into the baseline distribution that enhance the PSF sidelobes and reduce the angular dynamic range. In this paper we present a new method of constrained antenna placement that reduces the spatial structure in the baseline distribution. This method not only outperforms random placement algorithms that avoid exclusion zones, but surprisingly outperforms random placement algorithms without constraints to provide what we believe are the smoothest constrained baseline distributions developed to date. We use our new algorithm to determine antenna placements for the originally planned MWA, and present the antenna locations, baseline distribution, and snapshot PSF for this array choice.