return points defining a refined triangulation obtained by bisection of all edges
        in the triangulation connected to any of the vertices in the list provided
178654
def midpoint_refine_triangulation_by_vertices(self, vertices):
        

        xi, yi = self.segment_midpoints_by_vertices(vertices=vertices)

        x_v1 = np.concatenate((self.x, xi), axis=0)
        y_v1 = np.concatenate((self.y, yi), axis=0)

        return x_v1, y_v1
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
990455
def uniformly_refine_triangulation(self, faces=False, trisect=False):
        

        if faces:
            x_v1, y_v1 = self._add_face_centroids()

        else:
            if not trisect:
                x_v1, y_v1 = self._add_midpoints()
            else:
                x_v1, y_v1 = self._add_tripoints(ratio=0.333333)

        return x_v1, y_v1
1313800
private List<Triangle> findConnectedTriangles(Vector3 point) {

		// Getting one of the neigh
		Triangle triangle = find(point);

		// Validating find results.
		if (!triangle.isCorner(point)) {
			System.err.println("findConnectedTriangles: Could not find connected vertices since the first found triangle doesn't" +
					" share the given point.");
			return null;
		}

		return findTriangleNeighborhood(triangle, point);
	}
854401
def _graph_reduction(adj, x, g, f):
    
    as_list = set()
    as_nodes = {v for v in adj if len(adj[v]) <= f and is_almost_simplicial(adj, v)}
    while as_nodes:
        as_list.union(as_nodes)
        for n in as_nodes:

            # update g and f
            dv = len(adj[n])
            if dv > g:
                g = dv
            if g > f:
                f = g

            # eliminate v
            x.append(n)
            _elim_adj(adj, n)

        # see if we have any more simplicial nodes
        as_nodes = {v for v in adj if len(adj[v]) <= f and is_almost_simplicial(adj, v)}

    return g, f, as_list
143300
def iter_points(self):
        ""
        if not self.is_discrete():
            raise ValueError("Patch is not discrete")
        names = sorted(self.sets.keys())
        icoords = [self.sets[name].iter_members() for name in names]
        for coordinates in product(*icoords):
            yield tuple(zip(names,coordinates))
89758
def triangulate(self):
        
        self._initialize()
        
        pts = self.pts
        front = self._front
        
        ## Begin sweep (sec. 3.4)
        for i in range(3, pts.shape[0]):
            pi = pts[i]
            #debug("========== New point %d: %s ==========" % (i, pi))
            
            # 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]
            l = 0
            while pts[front[l+1], 0] <= pi[0]:
                l += 1
            pl = pts[front[l]]
            
            # "(i) middle case"
            if pi[0] > pl[0]:  
                #debug("  mid case")
                # Add a single triangle connecting pi,pl,pr
                self._add_tri(front[l], front[l+1], i)
                front.insert(l+1, i)
            # "(ii) left case"
            else:
                #debug("  left case")
                # Add triangles connecting pi,pl,ps and pi,pl,pr
                self._add_tri(front[l], front[l+1], i)
                self._add_tri(front[l-1], front[l], i)
                front[l] = i
            
            #debug(front)
                
            # Continue adding triangles to smooth out front
            # (heuristics shown in figs. 9, 10)
            #debug("Smoothing front...")
            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
                    #debug("Smooth angle:", pi, p1, p2, angle)
                    if angle > np.pi/2. 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],
                                  source='smooth1')
                    front.pop(ind1)
            #debug("Finished smoothing front.")
            
            # "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)
1296468
def transitively_reduce(self):
        
        removals = set()

        for from_node, neighbors in self._edges.items():
            childpairs = \
                [(c1, c2) for c1 in neighbors for c2 in neighbors if c1 != c2]

            for child1, child2 in childpairs:
                if self.has_path(child1, child2) \
                   and not self.has_path(child1, from_node):
                    removals.add((from_node, child2))

        for edge in removals:
            self.remove_edge(edge[0], edge[1])
1040092
def _edge_opposite_point(self, tri, i):
        
        ind = tri.index(i)
        return (tri[(ind+1) % 3], tri[(ind+2) % 3])
1222388
function snapRound (points, edges, useColor) {
  // 1. find edge crossings
  var edgeBounds = boundEdges(points, edges)
  var crossings = getCrossings(points, edges, edgeBounds)

  // 2. find t-junctions
  var vertBounds = boundPoints(points)
  var tjunctions = getTJunctions(points, edges, edgeBounds, vertBounds)

  // 3. cut edges, construct rational points
  var ratPoints = cutEdges(points, edges, crossings, tjunctions, useColor)

  // 4. dedupe verts
  var labels = dedupPoints(points, ratPoints, vertBounds)

  // 5. dedupe edges
  dedupEdges(edges, labels, useColor)

  // 6. check termination
  if (!labels) {
    return (crossings.length > 0 || tjunctions.length > 0)
  }

  // More iterations necessary
  return true
}
405546
def vertices(self):
        
        if self._v_out is None:
            output = qhalf('Fp', self.halfspaces, self.interior_point)
            pts = []
            for l in output[2:]:
                pt = []
                for c in l.split():
                    c = float(c)
                    if c != 10.101 and c != -10.101:
                        pt.append(c)
                    else:
                        pt.append(np.inf)
                pts.append(pt)
            self._v_out = np.array(pts)
        return self._v_out
658439
def get_all_edge_nodes(self):
        """"""
        edge_nodes = set(e for es in self.edges for e in es)
        for edges in self.edges_rel.values():
            rel_nodes = set(e for es in edges for e in es)
            edge_nodes.update(rel_nodes)
        return edge_nodes
77221
def _internal_get_cut_vertex_list(graph):
    
    list_of_cut_vertices = set()
    if graph.num_nodes() == 0:
        return list(list_of_cut_vertices)

    dfs_count = 0
    root_dfs_count = 1
    dfs_stack = deque()
    visited = defaultdict(lambda: False)
    parent = defaultdict(lambda: None)
    children = defaultdict(lambda: [])
    depth = {}
    low = {}
    preorder_processed = defaultdict(lambda: False)
    postorder_processed = defaultdict(lambda: False)

    # We're simulating a recursive DFS with an explicit stack, since Python has a really small function stack
    unvisited_nodes = set(graph.get_all_node_ids())
    while len(unvisited_nodes) > 0:
        # --Initialize the first stack frame, simulating the DFS call on the root node
        u = unvisited_nodes.pop()
        parent[u] = u
        stack_frame = {
            'u': u,
            'v': None,
            'remaining_children': graph.neighbors(u)
        }
        dfs_stack.appendleft(stack_frame)

        while len(dfs_stack) > 0:
            frame = dfs_stack.popleft()
            u = frame['u']
            v = frame['v']

            if not visited[u]:
                if u in unvisited_nodes:
                    unvisited_nodes.remove(u)
                visited[u] = True
                dfs_count += 1
                depth[u] = dfs_count
                low[u] = depth[u]
                if len(frame['remaining_children']) > 0:
                    v = frame['remaining_children'].pop()
                    frame['v'] = v

            if v is None:
                # --u has no neighbor nodes
                continue

            if not preorder_processed[v]:
                # --This is the preorder processing, done for each neighbor node ''v'' of u
                parent[v] = u
                children[u].append(v)
                preorder_processed[v] = True
                # print 'preorder for {}'.format(v)
                dfs_stack.appendleft(frame)

                # --Simulate the recursion to call the DFS on v
                new_frame = {
                    'u': v,
                    'v': None,
                    'remaining_children': graph.neighbors(v)
                }
                dfs_stack.appendleft(new_frame)
                continue

            elif not postorder_processed[v] and u == parent[v]:
                # --This is the postorder processing, done for each neighbor node ''v'' of u
                if low[v] >= depth[u] and depth[u] > 1:
                    list_of_cut_vertices.add(u)
                low[u] = min(low[u], low[v])
                postorder_processed[v] = True
                # print 'postorder for {}'.format(v)

            elif visited[v] and (parent[u] != v) and (depth[v] < depth[u]):
                # (u,v) is a backedge from u to its ancestor v
                low[u] = min(low[u], depth[v])

            if len(frame['remaining_children']) > 0:
                # --Continue onto the next neighbor node of u
                v = frame['remaining_children'].pop()
                frame['v'] = v
                dfs_stack.appendleft(frame)

    # The root node gets special treatment; it's a cut vertex iff it has multiple children
    if len(children[root_dfs_count]) > 1:
        for node_id, dfs in list(depth.items()):
            if dfs == root_dfs_count:
                list_of_cut_vertices.add(node_id)
                break

    return list(list_of_cut_vertices)
684941
def _getImpliedEdges(roots):
        
        #Get nodes in job graph
        nodes = set()
        for root in roots:
            root._dfs(nodes)

        ##For each follow-on edge calculate the extra implied edges
        #Adjacency list of implied edges, i.e. map of jobs to lists of jobs
        #connected by an implied edge
        extraEdges = dict([(n, []) for n in nodes])
        for job in nodes:
            if len(job._followOns) > 0:
                #Get set of jobs connected by a directed path to job, starting
                #with a child edge
                reacheable = set()
                for child in job._children:
                    child._dfs(reacheable)
                #Now add extra edges
                for descendant in reacheable:
                    extraEdges[descendant] += job._followOns[:]
        return extraEdges
1107051
private void triangulateFeatures(List<AssociatedTriple> inliers,
									 DMatrixRMaj P1, DMatrixRMaj P2, DMatrixRMaj P3) {
		List<DMatrixRMaj> cameraMatrices = new ArrayList<>();
		cameraMatrices.add(P1);
		cameraMatrices.add(P2);
		cameraMatrices.add(P3);

		// need elements to be non-empty so that it can use set().  probably over optimization
		List<Point2D_F64> triangObs = new ArrayList<>();
		triangObs.add(null);
		triangObs.add(null);
		triangObs.add(null);

		Point4D_F64 X = new Point4D_F64();
		for (int i = 0; i < inliers.size(); i++) {
			AssociatedTriple t = inliers.get(i);

			triangObs.set(0,t.p1);
			triangObs.set(1,t.p2);
			triangObs.set(2,t.p3);

			// triangulation can fail if all 3 views have the same pixel value. This has been observed in
			// simulated 3D scenes
			if( triangulator.triangulate(triangObs,cameraMatrices,X)) {
				structure.points[i].set(X.x,X.y,X.z,X.w);
			} else {
				throw new RuntimeException("Failed to triangulate a point in the inlier set?! Handle if this is common");
			}
		}
	}
954056
def build_edges(self):
        
        self.edges = [
            edge if isinstance(edge, Edge) else Edge(*edge)
            for node in self.nodes.values()
            for edge in getattr(node, "edges", [])
            if edge[0] in self.nodes and edge[1] in self.nodes
        ]
        return self
146385
def edges(self):
        
        canonical_edges = set()
        for v1, neighbours in self._vertices.items():
            for v2 in neighbours:
                edge = self.canonical_order((v1, v2))
                canonical_edges.add(edge)
        return canonical_edges