Given edges and vertices, how do we decide which vertices can form a polygon?
Itâs a strange question, maybe you need to give an example.
However, the basics are, you need at least two vertices to make an edge, and a minimum of three edges to make a face, also known as a polygon.
A face with 5 vertices or more is called an ngon and faces can be set that canât exist is reality, like some bent origami, the tool does its best but you can get weird shading effects as it tries to figure it out.
It is possible to have vertices and edges with no faces attached, they wonât show up in the render.
There are several indexes, usually vertices are listed and identified, you then create indexes of faces that point to the existing vertices.
Example, I have vertices v1, v2, v3 and v4. v1 is represented as (0.4, 0, 2.3) by xyz coordinates, same for the others.
A face is defined as f(v1, v2, v3, v4) keeping this order, v1 connects to v2, v2 to v3 and so forth. You can also define if you want to store normals on the vertices or the faces, and then the UV info.
This way you can have several faces sharing vertices, obviously, as happens a lot in real topology (being the desirable thing).
Reading about the FBX ascii format will give you a good insight about this topic.
At first, we need a list of vertices. Index, and vertices coordinates.
Then, polygon is made of vertices, simply by listing their indices in a row, clockwise or counterclockwise. The difference between listing direction defines an orientation of generated normal of a polygon. Such drawing method has doesnât allow polygon to have a hole.
Correct me, if it is wrong.
Hi! To all, here is what I meant.
Say I only have edges, and vertices(ids, coordinates), itâs very easy to tell by eye that 23109 is a polyshape that can form a polygon(cycle), 01192 can form a polygon, 0265, 6417, and so on.
How do we automate this process in python code?
you could probably just invoke one of the operators for making/filling in faces with the relevant vertices selected.
bpy.ops.mesh.edge_face_add()
(API docs link) for an example or bpy.ops.mesh.fill(use_beauty=True)
(API docs link) might be even better.
For the broad question about how a collection of edges could form a polygon, consider scrounging around at Math Exchange or some similar board. You may find Equation to check if a set of vertices form a real polygon? to be an interesting starting point.
Specifically for Blender meshes, two cases have bearing. Do you have the MeshPolygon or not?

Yes: Then the problem is trivial.
MeshPolygon
gives you a loop iterator:
import bpy
from bpy import data as D
from bpy import context as C
aob = C.active_object
aod = aob.data
poly = aod.polygons
[e for e in poly[0].loop_indices]
#~ [0, 1, 2, 3]
These are indices into the meshâs loop list, aod.loops
. Each entry in this list is a MeshLoop and furnishing indices to one vertex âheadâ (vertex_index
) and one edge âtailâ (edge_index
) that together represents one corner and side of the polygon. Use these indices to retrieve vertex and edge data from aod.vertices
and aod.edges
respectively. Retrieving all the MeshLoops
in the order given by MeshPolygon's
loop iterator recovers an ordered list of the polygonâs vertices and edges.
 No: The problem is less trivial but not intractable.
I suppose there are a number of ways to go about this. Probably the more popular route is through the BMesh API. bmesh operator bmesh.ops.edgeloop_fill(bm, edges=my_BMEdge_list) orders the list and returns a face, if possible, or an empty list otherwise.
aob = C.active_object
aod = aob.data
bm = bmesh.new()
bm.from_mesh(aod)
bm.edges.ensure_lookup_table()
se = []
for e in bm.edges:
if(e.select == True) :
se.append(e)
len(se)
#~ 10
flst = bmesh.ops.edgeloop_fill(bm, edges=se)
flst
#~ {'faces': [<BMFace(0x7fd07b2c2790), index=144, totverts=10>]}
If the selected edges are not coherent:
# Same as above...
len(se)
#~ 21
flst = bmesh.ops.edgeloop_fill(bm, edges=se)
flst
#~ {'faces': []}
That gets you home free with a minimum of trouble: a bit of BMesh
black magic. You get a face with a coherent edge list, but nothing if your edge list is incoherent.
I suppose this begs the question if an arbitrary list of edges selected from a Blender mesh can be ordered into a loop whose (a) ending edge shares a vertex with the starting edge, and (b) whose each intermediary edge shares a vertex with a predecessor edge and a successor edge?
The game, then, is to detect that condition and then a (potential) polygon is at hand, otherwise ordering does not seem possible, so the concomitant polygon is also not possible.
In particular:
 Getting a list of selected edges. Blender selected edges are famously in no particular order.
 Making, perhaps, edgetovertices and verticestoedge maps that might detect loop coherency
 Picking an edge and starting an edgetovertextoedge walk that might come back to the starting edge
 Reporting success on a loop walk that goes nowhere, otherwise failing.
Along those lines, you might consider something like this:
import bpy
from bpy import data as D
from bpy import context as C
# Edges have been selected on the active object. Polygonal?
aob = C.active_object
# Try to make this True...
rslt = False
if (aob.mode == 'OBJECT') and (aob.type == 'MESH'):
aod = aob.data
edgl = aod.edges
vrtl = aod.vertices
# Anything selected?
elst = [e.index for e in edgl if e.select == True]
if bool(elst):
# There are selected edges.
# Get maps: e > [v0, v1]; v > [e0, e1,...]
emap = {}; vmap = {}
for e in elst:
emap.update({e: list(edgl[e].vertices)})
for v in edgl[e].vertices:
if v in vmap:
vmap[v].append(e)
else:
vmap.update({v: [e]})
# Consume elst, pop off edge indices until exhausted or the walk breaks
eidx = elst[0]
# Stack of potentially successor edges
nset = []
# Ordered list of edges
path = []
# temporary adjacent edge list
nxte = []
while all((not(eidx in path), bool(elst))):
nxte.clear()
if not(bool(path)):
# Starting path construction. Get edges branching from both
# ends of the current edge
nset.extend([ e for e in vmap[emap[eidx][0]] if e != eidx and e in elst])
nset.extend([ e for e in vmap[emap[eidx][1]] if e != eidx and e in elst])
else :
# In the midst of path construction. Expect only one edge branching
# off from the current edge. If there are more than one edge branchings,
# then we can't form a polygon. Ditto NO branches off the current edge  continuity break
nxte.extend([ e for e in vmap[emap[eidx][0]] if e != eidx and e in elst])
nxte.extend([ e for e in vmap[emap[eidx][1]] if e != eidx and e in elst])
if len(nxte) != 1:
# Case 1: nxte > 1: multiple successor edges. A fork in the road. Bail...
# Case 2: nxte < 1: no successor edges. 2a: Path ahead and behind  closing the path. 2b: end of road  Bail.
if len(nxte) > 1 :
break # Case 1
else:
# chk1: edges on one end. chk2: edges on the other.
chk1 = [ e for e in vmap[emap[eidx][0]] if e != eidx ]
chk2 = [ e for e in vmap[emap[eidx][1]] if e != eidx ]
if all((all([e in path for e in chk2]), bool(chk2))) \
and \
all((all([e in path for e in chk1]), bool(chk1))):
# 2a: Path on either end of the last edge. Closing the path.
path.append(eidx)
elst.remove(eidx)
break
else:
# 2b: We're on the last edge, but the path is not on both ends.
# Not a closed path. Not a polygon.
break
else:
# One way forward has been found.
# Path construction continues.
nset.extend(nxte)
path.append(eidx)
elst.remove(eidx)
try:
eidx = nset.pop()
except IndexError:
# Disjoint edge  Polys not possible
break
if bool(elst):
# Still have listed edges? edge walk broke somewhere...
rslt = False
else:
# Consumed all edges and back to where we started...
# If this test code was a function, return path to caller
rslt = True
else :
# No edges selected...
rslt = False
Dramatis personae
emap
and vmap
are forward and reverse lookup dictionaries. path
is a list of edge indices reflecting edges that are, thus far, in a coherent order. elst
is a list of edge indices awaiting examination. The endgame test is convoluted and Iâm not especially pleased by it (around line 50). On the penultimate edge, check if that edge is surrounded by alreadyfound path edges, and declare victory, or not, and fail.
Have fun seeing if there are any useful sweetmeats in here.
Postscript
A recursive approach might be lurking in your question: Find all potential polygons in a selected list of edges. This implementation declares a fail when it finds branching edges. (See âmultiple successor edgesâ around line 50) Consider that a recursion point: stack the current partial solution, walk down one branch to its conclusion, pop the stack and continue the walk down the other branch. These branches may also have their own branches, and so on. And so forth.
Hi ! Thanks for the useful links and code. I donât have the mesh polygons, only the vertices and edges. Itâs not clear how BentleyOttmann algorithm can be adapted to 3D cases.
The edgevertices walk should be the most promising approach, omitting the branching edges at first might help too, but the computational cost would be high. (Btw, why is BMesh black magic ?) I found a 2D implementation in Matlab that works well in 2D, it was looking for the polygon that doesnât overlap with any other polygons in the graph, but couldnât be generalized in 3D. Maybe thereâre some features we can extract for 3D cases.
It is an idiomatic expression which native English writers (such as myself) routinely deploy to confuse everyone else on the planet. I proposed bmesh.ops.edgeloop_fill()
in my previous post in the manner of a magic spell â without explanation of its internal operation.
So â if I may restate the problem, based on your diagram:
Given vertices: {v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11}
and edges: {e0: [v1, v7], e1: [v1, v8], e2: [v3, v8], e3: [v3, v10], e4: [v9, v10], \
e5: [v2, v9], e6: [v2, v3], e7: [v0, v2], e8: [v2, v6], \
e9: [v0, v5], e10: [v5, v6], e11: [v6, v7], e12: [v9, v11], \
e13: [v0, v11], e14: [v4, v6], e15: [v1, v4], e16: [v3, v4]}
You want an output of âelemental polygons,â those that are not unions of other polygons, such as:
{p0: [v0, v11, v9, v2], p1: [v9, v10, v3, v2], p2: [v0, v2, v6, v5], p3: [v2, v3, v8, v1], p4: [v4, v3, v8, v1] \
p5: v6, v4, v1, v7]}
But not: p6: [v0, v2, v3, v4, v6, v5]
, because p6 is a union of p2 and p3.
Interesting to note that bpy.ops.mesh.edge_face_add()
identifies and fills all but p1 and p2. Could be worthwhile to look at its implementation, because it kind of, sort of, tries to solve your problem. These vertices are coplanar, so I donât thing the failure stems from face distortion.
On the other hand, bpy.ops.mesh.fill()
completely fills â but triangulates â as it goes. Could be something worthwhile in its implementation as well.
Insofar as working 2D v. 3D:
 The script I offered, of course, is unaware of either. It operates in the realm of nodes and connections between nodes and has no spatial concept.
 Given a projection chosen so that regionswherepolygonswouldbedonâtoverlap, (perhaps a
View
projection) one may cheerfully operate in 2D in the UV region working with a mesh projection. Of course, Blender would need polygons in the mesh in order to make a UV map for you. But you can also use your own projection â something simple like âflatten Zâ â and cast an image of the mesh using your own transforms. That way you can avail yourself of any 2D algorithm that suits.
@megalomaniak @grosgood Youâre right! bpy.ops.mesh.fill() does the job. I can then join the triangles to find the poly loops. Is it this ?
Looks like it, but Iâm not a blender dev so I can only speculate from the glance I took.
Yes. You tracked it down. Now, some nice rainy day, settle down with your favorite beverage and debugger, drop a break point at edbm_fill_exec()
and enjoy the show. Beforehand, in edit mode, select all of the edges/vertices and in the Python console, type bpy.ops.mesh.fill()
. You should hit the break point with a backtrace something like the attached. have fun!
edbm_fill_exec_bt.txt (6.3 KB)
[EditâŚ]
Addendum
Though, to be particular, the real show is a few frames more up the stack:
(gdb) bt
#0 bmo_triangle_fill_exec (bm=0x7fffce393538, op=0x7fffffffb710) at /home/gosg>
#1 0x00000000037b737a in BMO_op_exec (bm=0x7fffce393538, op=0x7fffffffb710) at>
#2 0x0000000004371d3a in edbm_fill_exec (C=0x7fffe522b838, op=0x7fff97a37938) >
See bmo_triangle_fill_exec. edbm_fill_exec()
is at the parameter and sanitychecking layer; not much to see on how the operator does what it does. Cheers!
[/Edit]