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"]
code: def _split_intersecting_edges(self):
      # we can do all intersections at once, but this has excessive memory
      # overhead.
  
      # measure intersection point between all pairs of edges
      all_cuts = self._find_edge_intersections()
  
      # cut edges at each intersection
      add_pts = []
      add_edges = []
      for edge, cuts in all_cuts.items():
          if len(cuts) == 0:
              continue
  
          # add new points
          pt_offset = self.pts.shape[0] + len(add_pts)
          new_pts = [x[1] for x in cuts]
          add_pts.extend(new_pts)
  
          # list of point indexes for all new edges
          pt_indexes = list(range(pt_offset, pt_offset + len(cuts)))
          pt_indexes.append(self.edges[edge, 1])
  
          # modify original edge
          self.edges[edge, 1] = pt_indexes[0]
  
          # add new edges
          new_edges = [
              [pt_indexes[i - 1], pt_indexes[i]]
              for i in range(1, len(pt_indexes))
          ]
          add_edges.extend(new_edges)
  
      if add_pts:
          add_pts = np.array(add_pts, dtype=self.pts.dtype)
          self.pts = np.append(self.pts, add_pts, axis=0)
      if add_edges:
          add_edges = np.array(add_edges, dtype=self.edges.dtype)
          self.edges = np.append(self.edges, add_edges, axis=0)
  
imports: from __future__ import division, print_function
  from itertools import permutations
  import numpy
  from collections import OrderedDict
label_desc: Use image node_id 17 for calling the Triangulation obj's underlying member method code with example usage: obj._split_intersecting_edges() without return types