Find the next edge that intersects with e, starting at index i
19380
def find_next_intersection(edges, i, e)
	    for j in i..(edges.count-1)
		e2 = edges[j][:edge]
		next if !e2 || e.connected?(e2)
		intersection = e.intersection(e2)
		return [intersection, j] if intersection
	    end
	    nil
	end
261028
def _adjacent_tri(self, edge, i):
        
        if not np.isscalar(i):
            i = [x for x in i if x not in edge][0]

        try:
            pt1 = self._edges_lookup[edge]
            pt2 = self._edges_lookup[(edge[1], edge[0])]
        except KeyError:
            return None
            
        if pt1 == i:
            return (edge[1], edge[0], pt2)
        elif pt2 == i:
            return (edge[1], edge[0], pt1)
        else:
            raise RuntimeError("Edge %s and point %d do not form a triangle "
                               "in this mesh." % (edge, i))
393189
def get_index_nested(x, i):
    
    for ind in range(len(x)):
        if i == x[ind]:
            return ind
    return -1
1258468
public static int findEdge(Poly node, Poly neighbour, MeshData tile, MeshData neighbourTile) {
		// Compare indices first assuming there are no duplicate vertices
		for (int i = 0; i < node.vertCount; i++) {
			int j = (i + 1) % node.vertCount;
			for (int k = 0; k < neighbour.vertCount; k++) {
				int l = (k + 1) % neighbour.vertCount;
				if ((node.verts[i] == neighbour.verts[l] && node.verts[j] == neighbour.verts[k])
						|| (node.verts[i] == neighbour.verts[k] && node.verts[j] == neighbour.verts[l])) {
					return i;
				}
			}
		}
		// Fall back to comparing actual positions in case of duplicate vertices
		for (int i = 0; i < node.vertCount; i++) {
			int j = (i + 1) % node.vertCount;
			for (int k = 0; k < neighbour.vertCount; k++) {
				int l = (k + 1) % neighbour.vertCount;
				if ((samePosition(tile.verts, node.verts[i], neighbourTile.verts, neighbour.verts[l])
						&& samePosition(tile.verts, node.verts[j], neighbourTile.verts, neighbour.verts[k]))
						|| (samePosition(tile.verts, node.verts[i], neighbourTile.verts, neighbour.verts[k])
								&& samePosition(tile.verts, node.verts[j], neighbourTile.verts, neighbour.verts[l]))) {
					return i;
				}
			}
		}
		return -1;
	}
1210841
private int findBase(int index, List<Trie.Node> nodes) {
        int base = baseBuffer.get(index);
        if (base < 0) {
            return base;
        }

        while (true) {
            boolean collision = false; // already taken?
            for (Trie.Node node : nodes) {
                int nextIndex = index + base + node.getKey();
                maxBaseCheckIndex = Math.max(maxBaseCheckIndex, nextIndex);

                if (baseBuffer.capacity() <= nextIndex) {
                    extendBuffers(nextIndex);
                }

                if (baseBuffer.get(nextIndex) != 0) { // already taken
                    base++; // check next base value
                    collision = true;
                    break;
                }
            }

            if (!collision) {
                break; // if there is no collision, found proper base value. Break the while loop.
            }

        }

        for (Trie.Node node : nodes) {
            baseBuffer.put(index + base + node.getKey(), node.getKey() == TERMINATING_CHARACTER ? -1 : 1); // Set -1 if key is terminating character. Set default base value 1 if not.
        }

        return base;
    }
583369
def get_next_triangle(mesh, T, plane, intersection, dist_tol):
    
    if intersection[0] == INTERSECT_EDGE:
        tris = mesh.triangles_for_edge(intersection[2])
    elif intersection[0] == INTERSECT_VERTEX:
        tris = mesh.triangles_for_vert(intersection[2])
    else:
        assert False, 'Invalid intersection[0] value : %d' % intersection[0]

    # Knowing where we come from is not enough. If an edge of the triangle
    # lies exactly on the plane, i.e. :
    #
    #   /t1\
    # -v1---v2-
    #   \t2/
    #
    # With v1, v2 being the vertices and t1, t2 being the triangles, then
    # if you just try to go to the next connected triangle that intersect,
    # you can visit v1 -> t1 -> v2 -> t2 -> v1 .
    # Therefore, we need to limit the new candidates to the set of unvisited
    # triangles and once we've visited a triangle and decided on a next one,
    # remove all the neighbors of the visited triangle so we don't come
    # back to it

    T = set(T)
    for tid in tris:
        if tid in T:
            intersections = compute_triangle_plane_intersections(
                    mesh, tid, plane, dist_tol)
            if len(intersections) == 2:
                T = T.difference(tris)
                return tid, intersections, T
    return None, [], T
742483
def _edge_event(self, i, j):
        
        front_index = self._front.index(i)
        
        #debug("  == edge event ==")
        front = self._front

        # First just see whether this edge is already present
        # (this is not in the published algorithm)
        if (i, j) in self._edges_lookup or (j, i) in self._edges_lookup:
            #debug("    already added.")
            return
        #debug("    Edge (%d,%d) not added yet. Do edge event. (%s - %s)" % 
        #      (i, j, pts[i], pts[j]))
        
        # traverse in two different modes:
        #  1. If cutting edge is below front, traverse through triangles. These
        #     must be removed and the resulting hole re-filled. (fig. 12)
        #  2. If cutting edge is above the front, then follow the front until 
        #     crossing under again. (fig. 13)
        # We must be able to switch back and forth between these 
        # modes (fig. 14)

        # Collect points that draw the open polygons on either side of the 
        # cutting edge. Note that our use of 'upper' and 'lower' is not strict;
        # in some cases the two may be swapped.
        upper_polygon = [i]
        lower_polygon = [i]
        
        # Keep track of which section of the front must be replaced
        # and with what it should be replaced
        front_holes = []  # contains indexes for sections of front to remove
        
        next_tri = None   # next triangle to cut (already set if in mode 1)
        last_edge = None  # or last triangle edge crossed (if in mode 1)
        
        # Which direction to traverse front
        front_dir = 1 if self.pts[j][0] > self.pts[i][0] else -1
                
        # Initialize search state
        if self._edge_below_front((i, j), front_index):
            mode = 1  # follow triangles
            tri = self._find_cut_triangle((i, j))
            last_edge = self._edge_opposite_point(tri, i)
            next_tri = self._adjacent_tri(last_edge, i)
            assert next_tri is not None
            self._remove_tri(*tri)
            # todo: does this work? can we count on last_edge to be clockwise
            # around point i?
            lower_polygon.append(last_edge[1])
            upper_polygon.append(last_edge[0])
        else:
            mode = 2  # follow front

        # Loop until we reach point j
        while True:
            #debug("  == edge_event loop: mode %d ==" % mode)
            #debug("      front_holes:", front_holes, front)
            #debug("      front_index:", front_index)
            #debug("      next_tri:", next_tri)
            #debug("      last_edge:", last_edge)
            #debug("      upper_polygon:", upper_polygon)
            #debug("      lower_polygon:", lower_polygon)
            #debug("      =====")
            if mode == 1:
                # crossing from one triangle into another
                if j in next_tri:
                    #debug("    -> hit endpoint!")
                    # reached endpoint! 
                    # update front / polygons
                    upper_polygon.append(j)
                    lower_polygon.append(j)
                    #debug("    Appended to upper_polygon:", upper_polygon)
                    #debug("    Appended to lower_polygon:", lower_polygon)
                    self._remove_tri(*next_tri)
                    break
                else:
                    # next triangle does not contain the end point; we will
                    # cut one of the two far edges.
                    tri_edges = self._edges_in_tri_except(next_tri, last_edge)
                    
                    # select the edge that is cut
                    last_edge = self._intersected_edge(tri_edges, (i, j))
                    #debug("    set last_edge to intersected edge:", last_edge)
                    last_tri = next_tri
                    next_tri = self._adjacent_tri(last_edge, last_tri)
                    #debug("    set next_tri:", next_tri)
                    self._remove_tri(*last_tri)

                    # Crossing an edge adds one point to one of the polygons
                    if lower_polygon[-1] == last_edge[0]:
                        upper_polygon.append(last_edge[1])
                        #debug("    Appended to upper_polygon:", upper_polygon)
                    elif lower_polygon[-1] == last_edge[1]:
                        upper_polygon.append(last_edge[0])
                        #debug("    Appended to upper_polygon:", upper_polygon)
                    elif upper_polygon[-1] == last_edge[0]:
                        lower_polygon.append(last_edge[1])
                        #debug("    Appended to lower_polygon:", lower_polygon)
                    elif upper_polygon[-1] == last_edge[1]:
                        lower_polygon.append(last_edge[0])
                        #debug("    Appended to lower_polygon:", lower_polygon)
                    else:
                        raise RuntimeError("Something went wrong..")
                    
                    # If we crossed the front, go to mode 2
                    x = self._edge_in_front(last_edge)
                    if x >= 0:  # crossing over front
                        #debug("    -> crossed over front, prepare for mode 2")
                        mode = 2
                        next_tri = None
                        #debug("    set next_tri: None")
                        
                        # where did we cross the front?
                        # nearest to new point
                        front_index = x + (1 if front_dir == -1 else 0)
                        #debug("    set front_index:", front_index)
                        
                        # Select the correct polygon to be lower_polygon
                        # (because mode 2 requires this). 
                        # We know that last_edge is in the front, and 
                        # front[front_index] is the point _above_ the front. 
                        # So if this point is currently the last element in
                        # lower_polygon, then the polys must be swapped.
                        if lower_polygon[-1] == front[front_index]:
                            tmp = lower_polygon, upper_polygon
                            upper_polygon, lower_polygon = tmp
                            #debug('    Swap upper/lower polygons')
                        else:
                            assert upper_polygon[-1] == front[front_index]
                        
                    else:
                        assert next_tri is not None
                
            else:  # mode == 2
                # At each iteration, we require:
                #   * front_index is the starting index of the edge _preceding_
                #     the edge that will be handled in this iteration
                #   * lower_polygon is the polygon to which points should be
                #     added while traversing the front
                
                front_index += front_dir
                #debug("    Increment front_index: %d" % front_index)
                next_edge = (front[front_index], front[front_index+front_dir])
                #debug("    Set next_edge: %s" % repr(next_edge))
                
                assert front_index >= 0
                if front[front_index] == j:
                    # found endpoint!
                    #debug("    -> hit endpoint!")
                    lower_polygon.append(j)
                    upper_polygon.append(j)
                    #debug("    Appended to upper_polygon:", upper_polygon)
                    #debug("    Appended to lower_polygon:", lower_polygon)
                    break

                # Add point to lower_polygon. 
                # The conditional is because there are cases where the 
                # point was already added if we just crossed from mode 1.
                if lower_polygon[-1] != front[front_index]:
                    lower_polygon.append(front[front_index])
                    #debug("    Appended to lower_polygon:", lower_polygon)

                front_holes.append(front_index)
                #debug("    Append to front_holes:", front_holes)

                if self._edges_intersect((i, j), next_edge):
                    # crossing over front into triangle
                    #debug("    -> crossed over front, prepare for mode 1")
                    mode = 1
                    
                    last_edge = next_edge
                    #debug("    Set last_edge:", last_edge)
                    
                    # we are crossing the front, so this edge only has one
                    # triangle. 
                    next_tri = self._tri_from_edge(last_edge)
                    #debug("    Set next_tri:", next_tri)
                    
                    upper_polygon.append(front[front_index+front_dir])
                    #debug("    Appended to upper_polygon:", upper_polygon)
                #else:
                    #debug("    -> did not cross front..")
        
        #debug("Finished edge_event:")
        #debug("  front_holes:", front_holes)
        #debug("  upper_polygon:", upper_polygon)
        #debug("  lower_polygon:", lower_polygon)

        # (iii) triangluate empty areas
        
        #debug("Filling edge_event polygons...")
        for polygon in [lower_polygon, upper_polygon]:
            dist = self._distances_from_line((i, j), polygon)
            #debug("Distances:", dist)
            while len(polygon) > 2:
                ind = np.argmax(dist)
                #debug("Next index: %d" % ind)
                self._add_tri(polygon[ind], polygon[ind-1],
                              polygon[ind+1], legal=False, 
                              source='edge_event')
                polygon.pop(ind)
                dist.pop(ind)

        #debug("Finished filling edge_event polygons.")
        
        # update front by removing points in the holes (places where front 
        # passes below the cut edge)
        front_holes.sort(reverse=True)
        for i in front_holes:
            front.pop(i)
1069202
function Edge(u, v) {

			this.u = u;
			this.v = v;
			this.iterator = null;
			this.uiterator = null;
			this.viterator = null;
		}
596295
private int nextBoundaryAfter(int startIndex) {
        BreakIterator breakiterator = search_.breakIter();

        if (breakiterator == null) {
            breakiterator = search_.internalBreakIter_;
        }

        if (breakiterator != null) {
            return breakiterator.following(startIndex);
        }

        return startIndex;
    }
1309618
private static Node getNthSibling(Node first, int index) {
    Node sibling = first;
    while (index != 0 && sibling != null) {
      sibling = sibling.getNext();
      index--;
    }
    return sibling;
  }
661063
def find_edges(a):
    
    edges = a[1:] == a[:-1]
    tops = np.where(~edges)[0] + 1
    tops = np.append(0, tops)
    values = a[tops]

    return tops, values
346228
def find(self, i):
        '''
        
        '''
        current = i
        edge_list = []
        while len(self.get_neighbors(current)) != 0:
            successor = self.get_neighbors(current)[0]
            edge_list.append((current, successor))
            current = successor
        if self.optimize:
            for e in edge_list:
                if e[1] != current:
                    self.del_edge((e[0], e[1]))
                    self.add_edge(e[0], current)
        return current
274831
private static boolean diagonalie(int i, int j, int n, int[] verts, int[] indices) {
        int d0 = (indices[i] & 0x0fffffff) * 4;
        int d1 = (indices[j] & 0x0fffffff) * 4;

        // For each edge (k,k+1) of P
        for (int k = 0; k < n; k++) {
            int k1 = next(k, n);
            // Skip edges incident to i or j
            if (!((k == i) || (k1 == i) || (k == j) || (k1 == j))) {
                int p0 = (indices[k] & 0x0fffffff) * 4;
                int p1 = (indices[k1] & 0x0fffffff) * 4;

                if (vequal(verts, d0, p0) || vequal(verts, d1, p0) || vequal(verts, d0, p1) || vequal(verts, d1, p1))
                    continue;

                if (intersect(verts, d0, d1, p0, p1))
                    return false;
            }
        }
        return true;
    }
515930
function intersectEdge(x0, y0, x1, y1, x, y) {
    if ((y > y0 && y > y1) || (y < y0 && y < y1)) {
        return -Infinity;
    }
    // Ignore horizontal line
    if (y1 === y0) {
        return -Infinity;
    }
    var dir = y1 < y0 ? 1 : -1;
    var t = (y - y0) / (y1 - y0);

    // Avoid winding error when intersection point is the connect point of two line of polygon
    if (t === 1 || t === 0) {
        dir = y1 < y0 ? 0.5 : -0.5;
    }

    var x_ = t * (x1 - x0) + x0;

    return x_;
}
445789
function findHoleBridge(hole, outerNode) {
       var p = outerNode,
           hx = hole.x,
           hy = hole.y,
           qx = -Infinity,
           m;

       // find a segment intersected by a ray from the hole's leftmost point to the left;
       // segment's endpoint with lesser x will be potential connection point
       do {
           if (hy <= p.y && hy >= p.next.y && p.next.y !== p.y) {
               var x = p.x + (hy - p.y) * (p.next.x - p.x) / (p.next.y - p.y);
               if (x <= hx && x > qx) {
                   qx = x;
                   if (x === hx) {
                       if (hy === p.y) return p;
                       if (hy === p.next.y) return p.next;
                   }
                   m = p.x < p.next.x ? p : p.next;
               }
           }
           p = p.next;
       } while (p !== outerNode);

       if (!m) return null;

       if (hx === qx) return m.prev; // hole touches outer segment; pick lower endpoint

       // look for points inside the triangle of hole point, segment intersection and endpoint;
       // if there are no points found, we have a valid connection;
       // otherwise choose the point of the minimum angle with the ray as connection point

       var stop = m,
           mx = m.x,
           my = m.y,
           tanMin = Infinity,
           tan;

       p = m.next;

       while (p !== stop) {
           if (hx >= p.x && p.x >= mx && hx !== p.x &&
                   pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p.x, p.y)) {

               tan = Math.abs(hy - p.y) / (hx - p.x); // tangential

               if ((tan < tanMin || (tan === tanMin && p.x > m.x)) && locallyInside(p, hole)) {
                   m = p;
                   tanMin = tan;
               }
           }

           p = p.next;
       }

       return m;
   }
1351452
def find_start_point(self):
        
        for i, row in enumerate(self.data):
            for j, _ in enumerate(row):
                if self.data[i, j] != 0:  # or not np.isfinite(self.data[i,j]):
                    return i, j
1025622
def intersects(self, e):
    
    if self.chrom != e.chrom:
      return False

    if e.start >= self.start and e.start < self.end:
      return True
    if e.end > self.start and e.end <= self.end:
      return True
    if e.start < self.start and e.end > self.end:
      return True
    return False