Find the smallest polygon with a certain edge on a 2d dijkstra graph

Question

Sorry for bad English. It's somehow called Minimal Cycle Basis of graph algorithm. I'm currently working on some algorithm to seperate a graph into rooms. Like the example. I have a graph link like the one in left, I want to tell there are 2 rooms in the graph, like the red area and the orange area in the right.

So far, I've tried to walk the shortest path from an edge, which failed. Like, in the left image, I started from the edge marked red, the shortest path would be like the right image.

I've also tried to always take the turn with largest angle in clockwise. If it work in one graph, it would failed when starting with opposite direction.

Is there any cheap solution on this one? I'm currently quick trapped.

Answer 1

Start at any edge, keeping track of which direction you're considering the edge in. Find the vertex at the end of the edge, then find the vertex coming out from the edge with a direction (out from that vertex) which makes the largest signed counterclockwise angle with the direction edge you started at. For instance, starting at the black edge, you could choose the blue edge or the green edge:

In this case, the angle formed to the blue edge is about 95 degrees, and the angle formed to the green edge is about 150 degrees. So you transition to the green edge. Keep following that rule, and eventually you'll get back to the starting edge. Those edges, taken in order, form a "room" (a face, in geometric terms).

Then, start with a new edge, one which you haven't yet visited in that direction. Each edge will be visited twice, once in each direction. That'll be a new room.

After you're all done, you'll have one edge loop for each room, plus an edge loop for the outside "room". Filter that one out if you like; it's the only one with a negative signed area.

Answer 2

With python, you could make a Graph, get the cycle_basis, then polygonize its elements :

import networkx as nx
from shapely import Polygon, polygonize, unary_union

rooms = [
    poly
    for poly in polygonize(
        unary_union(
            list(
                x.exterior for x in map(Polygon, nx.cycle_basis(nx.Graph(edges)))
            )
        ).geoms
    ).geoms
]

# [
#     <POLYGON ((160 20, 10 100, 100 120, 160 20))>,
#     <POLYGON ((160 20, 100 120, 10 100, 30 180, 140 220, 180 140, 160 20))>
# ]

Used input :

edges = [
    ((10, 100), (30, 180)),
    ((30, 180), (140, 220)),
    ((140, 220), (180, 140)),
    ((180, 140), (160, 20)),
    ((160, 20), (10, 100)),
    ((10, 100), (100, 120)),
    ((100, 120), (160, 20)),
]

Answer 3

I would probably attempt an algorithm where:

1. I mark every side of every edge as a potential room;
2. Group these potential room into sets which are actually the same room (you could use the paths you've already drawn to do this)
3. Discard the outside of the shape
4. Treat each remaining set as a room

Answer 4

Finally, I've got the principles. For an edge inside the graph, which should be shared by 2 circle basises, priorizing the largest signed angle (counter-clockwise) would find one of them, whose edges going counter-clockwisely. And priorizing the smallest (clockwise) would find the other (edges go clockwisely). So both would be correct.

But for an edge on the 'edge' of the graph, who was only contained by 1 circle basis, one of the basises should not exist. So one of the priorizing ways would give the wrong result.

On this scenario, you could find the polygon, in the result, clockwisely doesn't match pathfinding priorizing. So you could change the priorizing and got the right result.

The way to determine if a polygon is clockwise could be found below. How to determine if a list of polygon points are in clockwise order?