Minimal Cyle basis extracted from straight skeleton

Question

I'm trying to implement an algorithm which finds the corresponding area of each individual edge of outer polygon given at the below shape. That is, corresponding area of 1,2 edge is [1,6,7,8,2], area for edge 2,3 is [2,8,3] and so forth, CCW or CW is not a issue here. To be verbose here the black bolded line is outer polygon and the inner dashed blue line is straight skeleton of given outer polygon, I have no control over the inner node numbering scheme here which means that from left to right nodes it can be 8,7,6 or 6,8,7 or 7,6,8 etc..

After googling for days I came across that minimal cycle basis with combination of Floyd Warshall algorithm is named of this technique and can be used to extract the required minimal cycle graph, I think that I'm at least on right path, please confirm?

I follow the instructions given at the "Polygon Detection from a Set of Lines Alfredo by Ferreira Manuel J. Fonseca Joaquim A. Jorge" nomenclature.

The following pseudo code is given to extract the minimum cycle path,

***MINIMUM-CYCLE-BASIS(G)***
1 Γ ← empty set
2 Π ← ALL-PAIRS-SHORTEST-PATHS(G)
3 for each v in VERTICES(G)
4 do for each (x, y) in EDGES(G)
5 do if Π x,v ∩ Π v,y = {v}
6 then C ← Π x,v ∪ Π v,y ∪ (x, y)
7 add C to Γ
8 ORDER-BY-LENGTH(Γ)
9 return SELECT-CYCLES(Γ)

• At the 2nd line **Π ← ALL-PAIRS-SHORTEST-PATHS(G)**is Floyd Warshall algorithm which will construe the Π with all the shortest paths. But some of the paths will be unnecessary to calculate, for example I don't need and have any direct relation between 2,4-7,5-1,7 etc.. vertices?
• What the originator means with that condition checking at line 5 and 6 if Π_x,v ∩ Π_v,y = {v} then C ← Π x,v ∪ Π v,y ∪ (x, y), AFAIU from the given pseudo code snippet the content structure of Π must be 2D array which holds the shortest distance for the given distance , e..g Π[2,7] = length_of_vertices(2,7). So what is the sense of having the abscissa and vertex in Π_x,v, what does it really represent?

Thanks

Answer 1

I'd suggest a much simpler approach. Start with any outer edge, say P1->P2. Then you check each node PX connected to P2, and pick the one where the angle (P1,P2,PX) has the smallest positive value. That node PX is the next node in your polygon. Then go on finding the node PY connected to PX where the angle (P2,PX,PY) has the smallest positive value.
There are several possible approaches to calculating the angle. One would be:

c = inner_product( P1-P2, PX-P2 ) / ( abs(P1-P2) * abs(PX-P2) ) # cosine of the angle
s = cross_product( P1-P2, PX-P2 ) / ( abs(P1-P2) * abs(PX-P2) ) # sine of the angle
angle = atan2( s, c ) # arc tangent with correct sign

With:

def cross_product( a, b ):
    return a.x*b.y - a.y * b.x

def inner_product( a, b ):
    return a.x*b.x + a.y*b.y

Be careful with the sign, it depends on CW vs CCW. And of course you can omit the normalization terms (abs...), because they cancel each other.
If concave polygons are allowed, you have to re-normalize the result of the arc tangent in order to ensure the angle is always positive:

def atan2_normalized( y, x ):
    angle = atan2( y, x )
    if angle < 0:
        return angle + 2 * Pi
    else:
        return angle