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?

• you may want to replace "this is the end result" by "this is what I want to get" because at first I thought you were showing what the script gives you and I didn't really understand the problem. Otherwise I'm unfortunately helpless for this problem, but I find your idea interesting, although it doesn't seem you imagined how it would decide where to create new edges and what would happen if the ngon didn't have exclusively straight angles, so I think it's more complicate than it may seem at first sight. – ChameleonScales Mar 13 '17 at 23:43
• oh I forgot you mentioned either vertical or horizontal so it's not meant to work on anything else. – ChameleonScales Mar 13 '17 at 23:50
• @ChameleonScales, Thanks, I reworded it. It's exclusively straight edges. – mrkotfw Mar 13 '17 at 23:54
• Do you want to achieve this programatically or using Blender's ui? – Ideogram Mar 14 '17 at 5:31
• Might "dissoleve limited" help? See the topmost answer to my question in: blender.stackexchange.com/questions/69602/… – Ideogram Mar 14 '17 at 5:34

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.

• The question is asking about doing it using python. Also Tinycad was added to blender 2.78 so it's now a standard addon. – sambler Mar 14 '17 at 7:36
• OK, I didn't know it was added, but you still need to enable it. Also, I realize the point was to automate the task, hence "You might need to tweak it, but at least if gives something to start from." It's better than no answer at all. – Doyousketch2 Mar 14 '17 at 7:47
• @Doyousketch2, I tried it, and from what I see, it requires that I select the edges. My problem is that I need to find out which edges I need to join. Hence, the need to implement an algorithm. – mrkotfw Mar 14 '17 at 22:22
• Most likely, yeah. My thought was that this would give you a code-base to look at how he iterated through the vertices. I saw another tool that duplicated, then extended. Almost like a bevel in reverse, if that makes sense. I'm trying to think of where I saw it. If I can remember, I'll link you to it. It might get you closer to the algo' you're looking for. – Doyousketch2 Mar 14 '17 at 22:48
• This was the other script I was thinking of. - wiki.blender.org/index.php/Extensions:2.6/Py/Scripts/Modeling/… - I don't know how applicable that one would be, but looking at the source code, it does check how to merge 90° angles, so maybe you'll find that a little easier to figure out. – Doyousketch2 Mar 14 '17 at 23:00