I would suggest abandoning your position-based approach, because there is no way to tell whether v6 and v7 in your last example are adjacent (i.e. connected) based solely on their position. Instead, make a graph indicating which points are connected to which other points: the points will be vertices of the graph, and you add an edge between each pair of vertices that are adjacent/connected.
To construct the graph, you could try this algorithm (just off the top of my head):
- Create a graph with the given vertices and no edges
- Group the vertices (points) by their x coordinate. Create a map of vertices to groups, or some other way to look up which group a given vertex is in.
- For each group, create a disjoint set data structure with the vertices in that group.
- Iterate through all the vertical edges of the rectangles, and for each edge, perform a union on the subsets corresponding to the two vertices at the ends of that edge.
- Iterate through the groups, and for each group iterate through its subsets. For each subset, first sort the vertices in that subset by y coordinate, and add edges to the graph between pairs of consecutive vertices.
Then repeat steps 2-5 with the role of x and y coordinates switched (and using horizontal edges instead of vertical edges).
Naturally, this relies on the assumption that all edges (lines) are either horizontal or vertical.