There is some undocumented functionality in Graphics`Mesh that may help.

• SimplePolygonPartition will break apart a self-intersecting polygon into non-self-intersecting components (the components include the "holes" in the original)
• PolygonCombine will merge those components into a single polygon (note that while free of interior holes this polygon may still intersect itself)
• FindIntersections will find any self-intersections and can therefore be used to filter out such polygons

.

Graphics`Mesh`MeshInit[]; randompoly := Module[{poly}, While[Length[FindIntersections[ poly = PolygonCombine @ SimplePolygonPartition @ Polygon[RandomReal[{-1, 1}, {25, 2}]]]] > 0]; poly] Graphics[{EdgeForm[Red], Yellow, randompoly}] 

There is some undocumented functionality in Graphics`Mesh that may help.

• SimplePolygonPartition will break apart a self-intersecting polygon into non-self-intersecting components (the components include the "holes" in the original)
• PolygonCombine will merge those components into a single polygon (note that while free of interior holes this polygon may still intersect itself)
• FindIntersections will find any self-intersections and can therefore be used to filter out such polygons

.

Graphics`Mesh`MeshInit[]; randompoly := Module[{poly}, While[Length[FindIntersections[ poly = PolygonCombine @ SimplePolygonPartition @ Polygon[RandomReal[{-1, 1}, {25, 2}]]]] > 0]; poly] Graphics[{EdgeForm[Red], Yellow, randompoly}] 

There are also some built-in polygons which may be useful for testing. They are:

PolygonData[] (* {"Blob", "ChvatalComb", "FractalCross", "HeptaSpiral", "HexaSpiral", "LSystem01", "PentaSpiral", "RandomWalk", "Test01", "TriSpiral"} *) 

The available properties are:

PolygonData["Properties"] (* {"Data", "Graphics", "GraphicsLine", "GraphicsPoint", "GraphicsPolygon", "Line", "MeshObject", "Point", "Polygon"} *) 

For example

polys = PolygonData[#, "Polygon"] & /@ PolygonData[]; Graphics[{EdgeForm[Red], Yellow, #}, ImageSize -> 100] & /@ polys