How to subdivide concave face into quads 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.



This is what I'm hoping to achieve. The "cuts" could go either vertically or horizontally.


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: Wording

Edit: Would adding edges in all four directions to every vertex that has an interior angle greater than 180 be a better solution?
Download TinyCAD script from GitHub:
https://github.com/zeffii/mesh_tiny_cad

File > User Preferences > Add-ons > Install from file...
choose the zip file

Edit mode + Edge select > C
select an edge, and another one you'd like it to extend to.
Right-click to finalize selection.  

W to bring up specials menu > TinyCAD > VTX | AUTO  

I'm not having much luck with this script over here.
I'm not a pro at it, but I'm hoping it gets you in the right direction.  

You might need to tweak it, but at least if gives something to start from.
Or file a bug-report on GitHub, if it's not doing what you need.  

I've used a similar feature in drafting class, so I get what you're going for.
Hope it does better for you.