class_docstr: Constrained delaunay triangulation
  
  Implementation based on [1]_.
  
  Parameters
  ----------
  pts : array
      Nx2 array of points.
  edges : array
      Nx2 array of edges (dtype=int).
  
  Notes
  -----
  * Delaunay legalization is not yet implemented. This produces a proper
    triangulation, but adding legalisation would produce fewer thin
    triangles.
  * The pts and edges arrays may be modified.
  
  References
  ----------
  .. [1] Domiter, V. and Žalik, B. Sweep‐line algorithm for constrained
     Delaunay triangulation
class_docstr_tok: ["Constrained","delaunay","triangulation","Implementation","based","on","[","1","]","_.","Parameters","--","--","--","--","--","pts",":","array","Nx2","array","of","points",".","edges",":","array","Nx2","array","of","edges","(","dtype=int",")",".","Notes","--","--","-","*","Delaunay","legalization","is","not","yet","implemented",".","This","produces","a","proper","triangulation",",","but","adding","legalisation","would","produce","fewer","thin","triangles",".","*","The","pts","and","edges","arrays","may","be","modified",".","References","--","--","--","--","--","..","[","1","]","Domiter",",","V.","and","\u017dalik",",","B.","Sweep\u2010line","algorithm","for","constrained","Delaunay","triangulation"]
docstr: Do the triangulation.
docstr_tok: ["Do","the","triangulation","."]
code: def triangulate(self):
      """Do the triangulation."""
      self._initialize()
  
      pts = self.pts
      front = self._front
  
      # Begin sweep (sec. 3.4)
      for i in range(3, pts.shape[0]):
          pi = pts[i]
  
          # First, triangulate from front to new point
          # This applies to both "point events" (3.4.1)
          # and "edge events" (3.4.2).
  
          # get index along front that intersects pts[i]
          idx = 0
          while pts[front[idx + 1], 0] <= pi[0]:
              idx += 1
          pl = pts[front[idx]]
  
          # "(i) middle case"
          if pi[0] > pl[0]:
              # Add a single triangle connecting pi,pl,pr
              self._add_tri(front[idx], front[idx + 1], i)
              front.insert(idx + 1, i)
          # "(ii) left case"
          else:
              # Add triangles connecting pi,pl,ps and pi,pl,pr
              self._add_tri(front[idx], front[idx + 1], i)
              self._add_tri(front[idx - 1], front[idx], i)
              front[idx] = i
  
          # Continue adding triangles to smooth out front
          # (heuristics shown in figs. 9, 10)
          for direction in -1, 1:
              while True:
                  # Find point connected to pi
                  ind0 = front.index(i)
                  ind1 = ind0 + direction
                  ind2 = ind1 + direction
                  if ind2 < 0 or ind2 >= len(front):
                      break
  
                  # measure angle made with front
                  p1 = pts[front[ind1]]
                  p2 = pts[front[ind2]]
                  err = np.geterr()
                  np.seterr(invalid="ignore")
                  try:
                      angle = np.arccos(self._cosine(pi, p1, p2))
                  finally:
                      np.seterr(**err)
  
                  # if angle is < pi/2, make new triangle
                  if angle > np.pi / 2.0 or np.isnan(angle):
                      break
  
                  assert (
                      i != front[ind1]
                      and front[ind1] != front[ind2]
                      and front[ind2] != i
                  )
                  self._add_tri(i, front[ind1], front[ind2])
                  front.pop(ind1)
  
          # "edge event" (sec. 3.4.2)
          # remove any triangles cut by completed edges and re-fill
          # the holes.
          if i in self._tops:
              for j in self._bottoms[self._tops == i]:
                  # Make sure edge (j, i) is present in mesh
                  # because edge event may have created a new front list
                  self._edge_event(i, j)
                  front = self._front
  
      self._finalize()
  
      self.tris = np.array(list(self.tris.keys()), dtype=int)
  
imports: from __future__ import division, print_function
  from itertools import permutations
  import numpy
  from collections import OrderedDict
label_desc: Use image node_id 4 for calling the Triangulation obj's underlying member method code with example usage: obj.triangulate() without return types