Assuming I’m following your approach properly, the easiest way of getting the outer hull of a potentially self intersecting polygon is to:
1] convert the poly into a mesh. I.E. an unordered list of points which contain pointers to the points to which they are connected. Typically each point will have two connections. Points that lie on intersections will have more than two.
2] find the intersection points on the poly, and insert them into the mesh. Disconnect the lines in the mesh that were intersected, and connect them to the new intersection points. I.E. the line AB is intersected at P. Add P to the mesh, disconnect AB, and connect AP and PB.
3] choose a suitable extreme starting point. Essentially you just need a point that has to lie on the outer hull. Typically you can just find the points that lie on the smallest X, and then find the highest Y in that set (assuming your co-ordinate system is normal euclidean, for rasterized Y co-ordinates, you’ll want the lowest value of Y).
4] Walk through your mesh one point at a time. When you reach an intersection, take the path that forms the largest clockwise angle (without being 2 Pi of course ) from your current path. Repeat until you reach the start point.
This will always return the outer hull of the mesh. As such, if you dilate your ‘S’ to the extent that the concavities collapse, and the structure becomes self intersecting, this’ll provide a robust method for getting just the outer part of the polygon.
 not necessarily the fastest, but most of the cost is in the intersection detection stage. Fast intersection detection is a whole other story.