I'm aware of
bpy.ops.mesh.vert_connect_concave() and the result is similar to what I'm looking to implement. However, with
bpy.ops.mesh.vert_connect_concave(), it adds edges to an already existing vertex.
This is an example of a selected concave face.
I was thinking of going through every outside vertex and performing the concave test. If it passes, add an edge, or add new vertices and edges.
Is there an algorithm for this? The constraint is that the edges are always straight: vertical or horizontal. Think floor plans without any diagonals.
Edit: Fixed order of images
Edit: Would adding edges in all four directions to every vertex that has an interior angle greater than 180 be a better solution?