Finding outside a geometric graph

0. Clarification: I'm not sure if the green connections between convex polygons are provided as part of the input, or if the program should define the corresponding green connections as the shortest paths between the polygons themselves. I just noticed that your image is missing the green border in the upper right corner (which will be part of the outer border, if allowed).

1. Solution. Always choose the next edge. If your input indicates which green lines are allowed and which are not, then you simply traverse the boundary of the outer component, typing one starting point (for example, taking the corner of the polygon with the smallest x-coordinate), ordering the green edges that extend from the polygon of that current point in tactical order and select the edge immediately after the current point in CCW order . Now take the other end of this edge as the "current point" and repeat the same method to find the next edge ... until you return to the first polygon.

2. Solution: Start with the convex body. If you allow all possible green lines, you don't need them as input. The convex hull of all edges of the polygon is the first approximation to your solution (see below for details of finding): the convex hull contains the real edges of the polygon (let them consider them "black": they are part of your final solution, already in the correct order) and the edges that connect the polygons (think of them as red: they need to be replaced with green edges and possibly parts of other polygons).

Completing the second solution: Divide and Conquer: Now we need to replace each red edge with a combination of green and black edges. We just focus on one red line at a time (and apply the same method for every red line we might have).

So, we have one red line containing two polygons that have one green line (the shortest connection between them) - the four edges of these two lines define a quadrilateral. If none of the other corners of the polygon are in this quad, you fail: replace the red edge with a green edge and any black edges on the polygons to get to the connection points.

But if you find a polygon in a quad, pick the one closest to the red edge. Move the red edge to this point - so that the new point will cut the red edge into two red edges. These two new red edges replace the one old red edge: apply this method recursively to both of them. Their corresponding quads are much smaller and contain fewer polygon edges.

As you continue to practice this division and conquest method, you will not end up with red edges (because you lose one red edge every time you find an empty quad).

Convex Corpus: This is a tricky problem in n dimensions, but simple in two dimensions: if you search the web or browse SO you will surely find a better solution than I can think of right now, but here's one that comes to mind (again: divide and conquer ): find one point A with the maximum x-coordinate and one point B with the minimum x-coordinate, connect them with two directed "blue" edges: A-> B and B-> a. Divide your points into two sets: on the right side of the edge A-> B and on the left side (which is indeed the right side of B-> A). We repeatedly replace each blue edge until we find a convex hull:

Take one blue edge A-> B and look at its right side. If not, then that blue edge is really black (part of your solution). Otherwise, take point C farthest to the right of the blue edge and replace edge A-> B with two blue edges A-> C and C-> B. Divide the points to the right of A-> B by those that are on the right side of A-> C, those on the right side of C-> B, and those that are neither (they are ignored). Repeat until all blue edges have been replaced.