Why do you need to find the entire perimeter? I would have thought that you could just check when they try an place an object. For this a raytracing approach should not be too expensive. You could split them into two groups: horizontal and vertical. Then trace an x_ray scanning lines where the y_pos falls between the upper and lower limit. I would think that it should be fast enough, since none of the lines are at angles.
Alternatively if the area can be split into cells of a fixed size you could just make a boolean array for the grid and check of whether its inside or outside of your area. That would be faster.
