Cut edges along crossings/tjunctions
16804
function cutEdges (floatPoints, edges, crossings, junctions, useColor) {
  var i, e

  // Convert crossings into tjunctions by constructing rational points
  var ratPoints = floatPoints.map(function(p) {
      return [
          rat(p[0]),
          rat(p[1])
      ]
  })
  for (i = 0; i < crossings.length; ++i) {
    var crossing = crossings[i]
    e = crossing[0]
    var f = crossing[1]
    var ee = edges[e]
    var ef = edges[f]
    var x = solveIntersection(
      ratVec(floatPoints[ee[0]]),
      ratVec(floatPoints[ee[1]]),
      ratVec(floatPoints[ef[0]]),
      ratVec(floatPoints[ef[1]]))
    if (!x) {
      // Segments are parallel, should already be handled by t-junctions
      continue
    }
    var idx = floatPoints.length
    floatPoints.push([ratToFloat(x[0]), ratToFloat(x[1])])
    ratPoints.push(x)
    junctions.push([e, idx], [f, idx])
  }

  // Sort tjunctions
  junctions.sort(function (a, b) {
    if (a[0] !== b[0]) {
      return a[0] - b[0]
    }
    var u = ratPoints[a[1]]
    var v = ratPoints[b[1]]
    return ratCmp(u[0], v[0]) || ratCmp(u[1], v[1])
  })

  // Split edges along junctions
  for (i = junctions.length - 1; i >= 0; --i) {
    var junction = junctions[i]
    e = junction[0]

    var edge = edges[e]
    var s = edge[0]
    var t = edge[1]

    // Check if edge is not lexicographically sorted
    var a = floatPoints[s]
    var b = floatPoints[t]
    if (((a[0] - b[0]) || (a[1] - b[1])) < 0) {
      var tmp = s
      s = t
      t = tmp
    }

    // Split leading edge
    edge[0] = s
    var last = edge[1] = junction[1]

    // If we are grouping edges by color, remember to track data
    var color
    if (useColor) {
      color = edge[2]
    }

    // Split other edges
    while (i > 0 && junctions[i - 1][0] === e) {
      var junction = junctions[--i]
      var next = junction[1]
      if (useColor) {
        edges.push([last, next, color])
      } else {
        edges.push([last, next])
      }
      last = next
    }

    // Add final edge
    if (useColor) {
      edges.push([last, t, color])
    } else {
      edges.push([last, t])
    }
  }

  // Return constructed rational points
  return ratPoints
}
226848
function trimCanvasXY(xy) {
    if( xy.length === 0 ) return;
    var last = xy[xy.length-1], i, point;

    var c = 0;
    for( i = xy.length-2; i >= 0; i-- ) {
        point = xy[i];
        if( Math.abs(last.x - point.x) === 0 && Math.abs(last.y - point.y) === 0 ) {
            xy.splice(i, 1);
            c++;
        } else {
            last = point;
        }
    }

    if( xy.length <= 1 ) {
        xy.push(last);
        c--;
    }
}
483584
function removeEdge(vertex, edge) {
  var adj = vertex.adjacent
  var idx = elist.index(adj, edge)
  adj.splice(idx, 1)
  //Check if flag needs to be updated
  if(!((idx < adj.length && adj[idx].level === edge.level) ||
       (idx > 0 && adj[idx-1].level === edge.level))) {
    vertex.euler[edge.level].setFlag(false)
  }
}
2326
def remove_edges(self, from_idx, to_idx, symmetric=False, copy=False):
    ''''''
    flat_inds = self._pairs.dot((self._num_vertices, 1))
    # convert to sorted order and flatten
    to_remove = (np.minimum(from_idx, to_idx) * self._num_vertices
                 + np.maximum(from_idx, to_idx))
    mask = np.in1d(flat_inds, to_remove, invert=True)
    res = self.copy() if copy else self
    res._pairs = res._pairs[mask]
    res._offdiag_mask = res._offdiag_mask[mask]
    return res
1288571
def cross(v1, v2):
    '''
    '''
    return (
        v1[1] * v2[2] - v1[2] * v2[1],
        v1[2] * v2[0] - v1[0] * v2[2],
        v1[0] * v2[1] - v1[1] * v2[0],
    )
192743
def _edges_intersect(self, edge1, edge2):
        
        h12 = self._intersect_edge_arrays(self.pts[np.array(edge1)], 
                                          self.pts[np.array(edge2)])
        h21 = self._intersect_edge_arrays(self.pts[np.array(edge2)], 
                                          self.pts[np.array(edge1)])
        err = np.geterr()
        np.seterr(divide='ignore', invalid='ignore')
        try:
            out = (0 < h12 < 1) and (0 < h21 < 1)
        finally:
            np.seterr(**err)
        return out
642879
def clip_slices(r, region, scale=1):
    ''''''
    t = []
    for ch in r:
        a1 = intersection(ch[0], region[0], scale=scale)
        if a1 is None:
            continue
        a2 = intersection(ch[1], region[1], scale=scale)
        if a2 is None:
            continue

        t.append((a1, a2))

    return t
875208
def path2edges(path):
    """"""
    node_a, node_b = tee(path)
    next(node_b, None)
    return zip(node_a, node_b)
1220255
def Cross(width=3, color=0):
    
    return Overlay(Line("h", width, color), Line("v", width, color))
61979
def chk_edges(self):
        """"""
        goids = set(self.go2obj)
        self.chk_edges_nodes(self.edges, goids, "is_a")
        for reltype, edges in self.edges_rel.items():
            self.chk_edges_nodes(edges, goids, reltype)
172137
private void cascadingCut(Node<K, V> y) {
        Node<K, V> z;
        while ((z = y.parent) != null) {
            if (!y.mark) {
                y.mark = true;
                break;
            }
            cut(y, z);
            y = z;
        }
    }
330752
function intersectTriangle (out, pt, dir, tri) {
  var EPSILON = 0.000001
  var edge1 = [0, 0, 0]
  var edge2 = [0, 0, 0]
  var tvec = [0, 0, 0]
  var pvec = [0, 0, 0]
  var qvec = [0, 0, 0]

  vec3.subtract(edge1, tri[1], tri[0])
  vec3.subtract(edge2, tri[2], tri[0])

  vec3.cross(pvec, dir, edge2)
  var det = vec3.dot(edge1, pvec)

  if (det < EPSILON) return null
  vec3.subtract(tvec, pt, tri[0])
  var u = vec3.dot(tvec, pvec)
  if (u < 0 || u > det) return null
  vec3.cross(qvec, tvec, edge1)
  var v = vec3.dot(dir, qvec)
  if (v < 0 || u + v > det) return null

  var t = vec3.dot(edge2, qvec) / det
  out[0] = pt[0] + t * dir[0]
  out[1] = pt[1] + t * dir[1]
  out[2] = pt[2] + t * dir[2]
  return t
}
1336544
def cross(v, w):
    
    x = v[1] * w[2] - v[2] * w[1]
    y = v[2] * w[0] - v[0] * w[2]
    z = v[0] * w[1] - v[1] * w[0]
    return [x, y, z]
107756
function findLineIntersections(line, crossCheckLines) {
        return util.toArray(crossCheckLines).reduce(function(res, crossCheckLine) {
            var intersection = line.intersection(crossCheckLine);
            if (intersection) {
                res.push(intersection);
            }
            return res;
        }, []);
    }
557688
def segments_touch_2D(ab, cd):
    '''
    
    '''
    return segments_colinear(ab, cd) | np.isfinite(segment_intersection_2D(ab, cd)[0])
1042205
def _adjacency_to_edges(adjacency):
    """"""
    edges = set()
    for u in adjacency:
        for v in adjacency[u]:
            try:
                edge = (u, v) if u <= v else (v, u)
            except TypeError:
                # Py3 does not allow sorting of unlike types
                if (v, u) in edges:
                    continue
                edge = (u, v)

            edges.add(edge)
    return edges
127260
private List<PathEdge> combine(final List<PathEdge> edges, final int x) {

        final int n = edges.size();
        final List<PathEdge> reduced = new ArrayList<PathEdge>(n);

        for (int i = 0; i < n; i++) {
            PathEdge e = edges.get(i);
            for (int j = i + 1; j < n; j++) {
                PathEdge f = edges.get(j);
                if (e.disjoint(f)) reduced.add(new ReducedEdge(e, f, x));
            }
        }

        return reduced;
    }