This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes.
How can we divide the plane using line segments in such a way that each subdivision contains exactly one connected component?
I was thinking of generating a voronoi diagram using the endpoints, but this presents some issues:
- Long edges are not guaranteed to be in the correct partition.
- The border becomes very complex (There is a separate line segment for most points)
Is there an algorithm that creates less complex borders?
The input would be a planar graph with multiple connected components, where each node has coordinates associated to it.
The output would be a subdivision for the bounding box given by the graph, which divides the plane using line segments.