This is a bit of a hard problem really since you need to worry about some things. Polygons can be simple convex things, or more complicated "concave" shapes, or multi-branched shapes composed of multiple "islands" and lakes. I would get that part straight first since if you only need the simple case it's better.
1) Convex polygons are easy to generate from random points, since you just need the convex hull - the ordering of the points does not affect the result. For actual polygons the order in which you link them together as a boundary is very important or you will get non-sensical shapes with twisted boundaries. But, there is the
alphahull package to generate smarter hulls from non-convex points.
2) If no part of the polygon can exceed the main boundary, then you need every vertex to be both inside the boundary and that no segment joining them crosses the main boundary. Imagine a polygon whose vertices are all inside the national boundary, but one segment crosses a river inlet. There are sampling functions for getting points within a polygon (
splancs) and there are geometry tests in
rgeos that could be used to ensure there are no crossings - still that's extra work since you are testing for failure of a set of sample points defining a polygon rather than generating known "good cases".
If you can relax some of the constraints then it might be fairly doable. You mention "circular polygons", do you really mean circles (or approximate circles) since if so then some of the tests could become much simpler.
I'd be inclined to dig into your aims and see if this really is what you want to be doing, or if you can simplify things more.