For every edge check if there's an adjacent edge. If there's none, it's part of the outline. If there's one or more, split the edge up in parts that are adjacent and parts that are not.

That's my guess.

THis might be weird, but how about... I was thinking voxel. find min max, grid that out with a manageable resolution, go O(n) just once but flood fill on empty space marking appropriate visited. early out on visited. weird right...It would be an accurate / persist-able representation of the solid space in that slice and transformable  whoh...in this representation, you can still continue to slice it up by making a sub group active. Break those off to their own instance, wash rinse repeat. I guess we still need to rasterize. sorry.

This is kind of from memory so I hope I'm getting it right. I had to do something like this for semi-conductor layout processing back in the 90s.......

First question is: do all the sub-polygons have the same winding?  For instance if they have clockwise winding you can do a "left turn" algorithm.  You have to first set up some data structure that connects all the lines and vertexes. This is kind of a pre-processing step.  So for instance each vertex should have a list of pointers to lines that connect to it. In realty you only really need the outgoing lines. In fact you probably don't need the lines at all, you can make them implicit by having a vertexes point to vertexes, but again vertexes need to be able to point to more than one vertex. If you have crossing polygons you have to break lines that intersect and add a vertex.

Then you start at the first line in your array and traverse in the winding direction. When you hit a vertex with more than two lines connected to it, you take the left most turn that's still in the winding direction.  As you go you mark the path you took, and flag which vertexes and edges you visited.  When you hit a previously encountered line you have found an outline. In that case you loop around the path you just created again, and you will come back to that same line. As you go, copy the outline, and save it however you like.  That's the first outline.....

Now you go to the next line in your array and repeat the process. You can just skip over lines that were flagged in previous steps. When you reach the end of your line array you are done.   I would get a piece of paper, draw some shapes and try it by hand.  Then it becomes obvious how it works.

hi! how you doing  Looks like you have some work to do edge splitting and triangulating the remaining internally as to not hurt your current representation and then apply the suggested logic. Your silhouette edge list needs to be separately built at some point.

5 hours ago, _WeirdCat_ said:

 But maybe i'm lacking some additional preprocess like subtracting one edge from another

I would just intersect all the lines up front and introduce new vertexes where you need them. For lines that overlay each other you can intersect lines with the end vertexes of the other line. If it has to be fast and/or the data set is large you can use some sort of quad-tree based algorithm.  Otherwise you can just use N^2 brute force checking.

Do the sub-polygons ever overlap? I can't tell from your picture because one can be behind another.  If not, you can then just look for lines that don't double up as @Mussi suggested above. That's probably simpler than what I outlined. However if they can overlap, that won't work. Also keep in mind you will likely have to introduce some sort of fudge factor to catch all the intersections because of floating point rounding errors.

Tessellating to triangles would work, but the images look like generated by binary space partition? In that case the boundary information could be found by keeping track of solid / empty space for the half spaces while constructing the tree. So in case you do the BSP construction yourself this should be easy to add.