External Face not being calculated properly

[MobiZaman]

I am running the following code:

import networkx as nx
from topology_shape_metrics.TSM import TSM
from matplotlib import pyplot as plt

nodeData = {'0': [233.40717895650255, 245.2668161593756], '1': [197.16129504244714, 30], '2': [141.70696162531476, 231.32493034071877], '3': [60.65624829590422, 113.49167630171439], '4': [108.35736160598731, 76.64552177189921], '5': [87.0130296182083, 188.10311014236993], '6': [319.33416955603843, 259.2393822803765], '7': [30, 277.38385767958584], '8': [98.92200205792096, 284.1742280192017], '9': [179.4743438581056, 319.91589873409737], '10': [287.1444006787124, 72.41331541473198], '11': [31.12464635584422, 32.898914774980994], '12': [158.93331495445887, 99.4944443930458], '13': [139.43918552954983, 153.80882320636442], '14': [369.5136536406337, 104.14142146557003], '15': [290.598502710234, 165.863033803461], '16': [211.4553136831521, 174.1784364618411], '17': [228.30221376063673, 102.81798218614415], '18': [37.389296631515435, 206.8668863010132], '19': [387.48004971189835, 189.04480920874767], 'cdnode1': [70.62903289986328, 215.04295834065474], 'cdnode2': [91.39401162703457, 219.91146037454223], 'cdnode3': [98.17352514597789, 132.9352577570292], 'cdnode4': [120.30579006619145, 105.56723017608186], 'cdnode5': [102.94092788747736, 108.040441996923]}

edgeData =[['0', '2'], ['0', '6'], ['0', '15'], ['0', '9'], ['1', '4'], ['1', '17'], ['1', '10'], ['2', '16'], ['2', '13'], ['3', '5'], ['3', '11'], ['4', '11'], ['6', '19'], ['7', '18'], ['8', '9'], ['10', '15'], ['10', '14'], ['12', '16'], ['14', '19'], ['15', '17'], ['cdnode1', '18'], ['5', 'cdnode1'], ['cdnode1', '7'], ['2', 'cdnode2'], ['cdnode2', 'cdnode1'], ['5', 'cdnode2'], ['cdnode2', '8'], ['3', 'cdnode3'], ['cdnode3', '13'], ['cdnode3', '5'], ['cdnode4', '12'], ['4', 'cdnode4'], ['cdnode4', '13'], ['3', 'cdnode5'], ['cdnode5', 'cdnode4'], ['4', 'cdnode5'], ['cdnode5', 'cdnode3']]

G = nx.Graph()
pos = {}
for node in nodeData:
    G.add_node(node)
    pos[node] = nodeData[node]
for edge in edgeData:
    src = edge[0]
    tgt = edge[1]
    G.add_edge(src, tgt)
tsm = TSM(G, pos)
tsm.display()

So, basically I have positions of nodes and data of edges and I am constructing a graph with this data. Then I run the code with only planarization i.e. I am not running orthogonalization or compaction. The external face is determined incorrectly for this case.

[MobiZaman]

I am using these positions for the embedding, and not applying another layout on it in TSM.

[MobiZaman]

For ease of understanding, I labelled the figure:

The external face should be f3, but it is choosing f12 as well the external face. The corner point selected for choosing the external face is 7.

[MobiZaman]

I followed the best answer from this post for finding the outer face. It seems to be working correctly, though I haven't tested it out for many graphs.

`def get_external_face(self): if len(self.pos) < 2: return list(self.dcel.faces.values())[0]

    #find the leftmost node
    corner_node = min(self.pos, key=lambda k: (self.pos[k][0], self.pos[k][1]))
    print (corner_node)
    print(self.G.adj[corner_node])

    #find the arc with the largest slope
    other = max(self.G.adj[corner_node], 
        key=lambda node: (self.pos[node][1] - self.pos[corner_node][1]) / (self.pos[node][0] - self.pos[corner_node][0]))

    #get the left face of the arc
    return self.dcel.half_edges[corner_node, other].twin.inc`

[uknfire]

Thank you so much. Your solution is right, except that it may lead to division by zero error. I have fixed it in lastest commit.

[MobiZaman]

Oh yes, you are right. In wanting a quick solution, I forgot to consider that. Thanks a lot!