def get_triangulation_edges(Fp, D, debug):
  # Appends to {D} the diagonals of a face that triangulate it.
  #
  # Assumes that {Fp[0..deg-1]} are the vertices of the face, in
  # either order around the border.
  # 
  # Assumes that each vertext is a tuple {(X, Y, Z, kv, lab, nd)}
  # where {kv} is the vertex's index in the OBJ file, {kab} is the "{key}:{iv}" name, and {nd}
  # is the number of triangulation diagonals that end at that vertex.
  #
  # On return the {nd} items will be all zeroed.
  
  deg = len(Fp)  # Vertices in the original polygon.
  assert deg >= 3

  if deg > 3:
    stack = [ iv for iv in range(deg) if Fp[iv][5] == 0 ]     # The vertices with zero {nd} are {stack[0..]}

    # Creates a doubly-linked list of all vertices:
    inext = [ (iv + 1) % deg for iv in range(deg) ]
    iprev = [ (iv - 1) % deg for iv in range(deg) ]
    np = deg  # Cont of vertices in area still not triangulated.
    hv = 0    # Index into {Fp} of some vertex still in the list.

    while np > 3:
      # At this point the /remaining region/ that is still to be
      # triangulated has the vertices linked by {inext} and {iprev}
      # starting at {hv}. The {nd} field of every vertex in
      # {Fp[0..deg-1]} is the number of diagonals incident to that
      # vertex that remains to be collected. The vertices
      # in that set with zero {nd} are in {stack[0..]}.
      
      if debug:
        # Print the current region:
        iv = stack[0]
        jv = iv
        sys.stderr.write(f"  np = {np:3d}")
        while True:
          p = Fp[jv]
          sys.stderr.write(f" {p[4]}")
          if p[5] != 0: sys.stderr.write(f"({p[5]})")
          jv = inext[jv]
          if jv == iv: break
        sys.stderr.write("\n")
      
      # Get a vertex with {nd=0}
      assert len(stack) > 0, "inconsitent {nd} fields"
      iv = stack.pop()
      assert Fp[iv][5] == 0
      
      # Trim that vertex off by a diagonal between the adjacent vertices:
      iv_org = iprev[iv]
      iv_dst = inext[iv]
      assert iv_org != iv_dst
      assert iv_org != iv and iv_dst != iv
      nd_org = Fp[iv_org][5]
      nd_dst = Fp[iv_dst][5]
      assert nd_org > 0 and nd_dst > 0
      
      kv_org = Fp[iv_org][3]
      kv_dst = Fp[iv_dst][3]
      assert kv_org >= 1 and kv_dst >= 1 and kv_org != kv_dst
      D.append(( kv_org, kv_dst ))
      
      # Decrement the {nd} fields of the two vertices:
      Fp[iv_org] = Fp[iv_org][:5] + ( nd_org - 1, )
      Fp[iv_dst] = Fp[iv_dst][:5] + ( nd_dst - 1, )
      
      #  If either became zero, stack them:
      if nd_org == 1: stack.append(iv_org)
      if nd_dst == 1: stack.append(iv_dst)
      
      # Exclude {iv} from the lists:
      inext[iv_org] = inext[iv]
      iprev[iv_dst] = iprev[iv]
      if hv == iv: hv = iv_dst
      
      np = np - 1
  
    assert len(stack) == 3