Select the best 2,3, or 4 perpendicular vertexes to connect to. These are the output grid connections.
492183
void selectConnections( Vertex target ) {
		// There needs to be at least two corners
		if( target.perpendicular.size() <= 1 )
			return;

//		if( target.index == 16 ) {
//			System.out.println("ASDSAD");
//		}
//		System.out.println("======= Connecting "+target.index);

		double bestError = Double.MAX_VALUE;
		List<Edge> bestSolution = target.connections.edges;

		// Greedily select one vertex at a time to connect to. findNext() looks at all possible
		// vertexes it can connect too and minimizes an error function based on projectively invariant features
		for (int i = 0; i < target.perpendicular.size(); i++) {
			Edge e = target.perpendicular.get(i);
			solution.clear();
			solution.add(e);

			double sumDistance = solution.get(0).distance;
			double minDistance = sumDistance;

			if( !findNext(i,target.parallel,target.perpendicular,Double.NaN,results) ) {
				continue;
			}

			solution.add(target.perpendicular.get(results.index));
			sumDistance += solution.get(1).distance;
			minDistance = Math.min(minDistance,solution.get(1).distance);

			// Use knowledge that solution[0] and solution[2] form a line.
			// Lines are straight under projective distortion
			if( findNext(results.index,target.parallel,target.perpendicular,solution.get(0).direction,results) ) {
				solution.add(target.perpendicular.get(results.index));
				sumDistance += solution.get(2).distance;
				minDistance = Math.min(minDistance,solution.get(2).distance);

				// Use knowledge that solution[1] and solution[3] form a line.
				if( findNext(results.index,target.parallel,target.perpendicular,solution.get(1).direction,results) ) {
					solution.add(target.perpendicular.get(results.index));
					sumDistance += solution.get(3).distance;
					minDistance = Math.min(minDistance,solution.get(3).distance);
				}
			}

			// Prefer closer valid sets of edges and larger sets.
			// the extra + minDistance was needed to bias it against smaller sets which would be more likely
			// to have a smaller average error. Division by the square of set/solution size biases it towards larger sets
			double error = (sumDistance+minDistance)/(solution.size()*solution.size());

//			System.out.println("  first="+solution.get(0).dst.index+"  size="+solution.size()+" error="+error);

			if( error < bestError ) {
				bestError = error;
				bestSolution.clear();
				bestSolution.addAll(solution);
			}
		}
	}
874584
int checkNumberOfConnections( List<SquareNode> graph ) {
		int histogram[] = new int[5];

		for (int i = 0; i < graph.size(); i++) {
			histogram[ graph.get(i).getNumberOfConnections() ]++;
		}

		if( graph.size() == 1 ) {
			if( histogram[0] != 1 )
				return 0;

			return 1;
		} else if( histogram[1] == 2 ) {
			// line
			if( histogram[0] != 0 )
				return 0;
			if( histogram[2] != graph.size()-2 )
				return 0;
			if( histogram[3] != 0 )
				return 0;
			if( histogram[4] != 0 )
				return 0;

			return 1;
		} else {
			// grid
			if (histogram[0] != 0)
				return 0;
			if (histogram[1] != 0)
				return 0;
			if (histogram[2] != 4)
				return 0;
			return 2;
		}
	}
499207
def output_connections(self, name):
        
        for output_name in self._compound_children[name].outputs:
            src = name, output_name
            if src in self._compound_linkages:
                dests = self._compound_linkages[src]
                if isinstance(dests[0], six.string_types):
                    dests = zip(dests[0::2], dests[1::2])
                for dest in dests:
                    yield src, dest
1050549
void putIntoCanonical( SquareGrid grid ) {

		boolean rowOdd = grid.rows%2 == 1;
		boolean colOdd = grid.columns%2 == 1;

		if( colOdd == rowOdd ) {
			// if odd and square then 4 solutions.  Otherwise just two solution that are on
			// opposite sides on the grid
			if( rowOdd && grid.rows == grid.columns ) {
				int best = -1;
				double bestDistance = Double.MAX_VALUE;
				for (int i = 0; i < 4; i++) {
					SquareNode n = grid.getCornerByIndex(i);
					double d = n.center.normSq();
					if( d < bestDistance ) {
						best = i;
						bestDistance = d;
					}
				}

				for (int i = 0; i < best; i++) {
					tools.rotateCCW(grid);
				}
			} else {
				double first = grid.get(0,0).center.normSq();
				double last = grid.getCornerByIndex(2).center.normSq();

				if( last < first ) {
					tools.reverse(grid);
				}
			}
		}
		// if only one is odd then there is a unique solution.  Since uber is already in a legit
		// configuration nothing needs ot be done
	}
1000134
public void diagonalAxisScanXZY(int dimK, int dimL, int dimM) {
        // x min ->x max;left upper corner z+y max->min//1
        //logger.debug("	diagonalAxisScanXZY");
        if (dimM < dimL) {
            dimL = dimM;
        }
        //int gridPoints = 0;//Debugging
        List<Point3d> line = new ArrayList<Point3d>();
        int pspEvent = 0;
        int m = 0;
        for (int j = dimM; j >= 1; j--) {// z
            line.clear();
            pspEvent = 0;
            for (int k = 0; k <= dimK; k++) {// min -> max; x
                m = dimM;// m==y
                line.clear();
                pspEvent = 0;
                for (int l = dimL; l >= 0; l--) {// z
                    //gridPoints++;
                    if (grid[k][m][l] < 0) {
                        if (pspEvent < 2) {
                            line.clear();
                            pspEvent = 1;
                        } else if (pspEvent == 2) {
                            firePSPEvent(line);
                            line.clear();
                            pspEvent = 1;
                        }
                    } else {
                        if (pspEvent == 1 | pspEvent == 2) {
                            line.add(new Point3d(k, m, l));
                            pspEvent = 2;
                        }
                    }
                    m--;
                }// for l
            }
            dimL = j;
        }
        //logger.debug(" #gridPoints>" + gridPoints);
    }
1324338
def grid_coords_from_corners(upper_left_corner, lower_right_corner, size):
    '''  '''
    assert upper_left_corner.wkt == lower_right_corner.wkt
    geotransform = np.array([upper_left_corner.lon, -(upper_left_corner.lon - lower_right_corner.lon) / float(size[1]), 0,
                            upper_left_corner.lat, 0, -(upper_left_corner.lat - lower_right_corner.lat) / float(size[0])])
    return GridCoordinates(geotransform=geotransform,
                               wkt=upper_left_corner.wkt,
                               y_size=size[0],
                               x_size=size[1])
948803
def grid_2d_8graph(self, m, n):
        """"""
        me = nx.Graph()
        node = me.node
        add_node = me.add_node
        add_edge = me.add_edge
        for i in range(m):
            for j in range(n):
                add_node((i, j))
                if i > 0:
                    add_edge((i, j), (i-1, j))
                    if j > 0:
                        add_edge((i, j), (i-1, j-1))
                if j > 0:
                    add_edge((i, j), (i, j-1))
                if (i - 1, j + 1) in node:
                    add_edge((i, j), (i-1, j+1))
        return self.copy_from(me)
1291055
static int closestCorner4(Grid g ) {
		double bestDistance = g.get(0,0).center.normSq();
		int bestIdx = 0;

		double d = g.get(0,g.columns-1).center.normSq();
		if( d < bestDistance ) {
			bestDistance = d;
			bestIdx = 3;
		}
		d = g.get(g.rows-1,g.columns-1).center.normSq();
		if( d < bestDistance ) {
			bestDistance = d;
			bestIdx = 2;
		}
		d = g.get(g.rows-1,0).center.normSq();
		if( d < bestDistance ) {
			bestIdx = 1;
		}

		return bestIdx;
	}
1129561
@Override
	protected void putGridIntoCanonical(Grid g ) {
		// first put it into a plausible solution
		if( g.columns != numCols ) {
			rotateGridCCW(g);
		}

		if( g.get(0,0) == null ) {
			reverse(g);
		}

		// select the best corner for canonical
		if( g.columns%2 == 1 && g.rows%2 == 1) {
			// first make sure orientation constraint is maintained
			if( isClockWise(g)) {
				flipHorizontal(g);
			}

			int numRotationsCCW = closestCorner4(g);
			if( g.columns == g.rows ) {
				for (int i = 0; i < numRotationsCCW; i++) {
					rotateGridCCW(g);
				}
			} else if( numRotationsCCW == 2 ){
				// only two valid solutions.  rotate only if the other valid solution is better
				rotateGridCCW(g);
				rotateGridCCW(g);
			}
		} else if( g.columns%2 == 1 ) {
			// only two solutions.  Go with the one which maintains orientation constraint
			if( isClockWise(g)) {
				flipHorizontal(g);
			}
		} else if( g.rows%2 == 1 ) {
			// only two solutions.  Go with the one which maintains orientation constraint
			if( isClockWise(g)) {
				flipVertical(g);
			}
		}
	}
851718
public void process(List<ChessboardCorner> corners ) {
		this.corners = corners;

		// reset internal data structures
		vertexes.reset();
		edges.reset();
		clusters.reset();

		// Create a vertex for each corner
		for (int idx = 0; idx < corners.size(); idx++) {
			Vertex v = vertexes.grow();
			v.reset();
			v.index = idx;
		}

		// Initialize nearest-neighbor search.
		nn.setPoints(corners,true);

		// Connect corners to each other based on relative distance on orientation
		for (int i = 0; i < corners.size(); i++) {
			findVertexNeighbors(vertexes.get(i),corners);
		}

		// If more than one vertex's are near each other, pick one and remove the others
		handleAmbiguousVertexes(corners);
//		printDualGraph();

		// Prune connections which are not mutual
		for (int i = 0; i < vertexes.size; i++) {
			Vertex v = vertexes.get(i);
			v.pruneNonMutal(EdgeType.PARALLEL);
			v.pruneNonMutal(EdgeType.PERPENDICULAR);
		}
//		printDualGraph();

		// Select the final 2 to 4 connections from perpendicular set
		// each pair of adjacent perpendicular edge needs to have a matching parallel edge between them
		// Use each perpendicular edge as a seed and select the best one
		for (int idx = 0; idx < vertexes.size(); idx++) {
			selectConnections(vertexes.get(idx));
		}
//		printConnectionGraph();

		// Connects must be mutual to be accepted. Keep track of vertexes which were modified
		dirtyVertexes.clear();
		for (int i = 0; i < vertexes.size; i++) {
			Vertex v = vertexes.get(i);
			int before = v.connections.size();
			v.pruneNonMutal(EdgeType.CONNECTION);
			if( before != v.connections.size() ) {
				dirtyVertexes.add(v);
				v.marked = true;
			}
		}

//		printConnectionGraph();
		// attempt to recover from poorly made decisions in the past from the greedy algorithm
		repairVertexes();

		// Prune non-mutual edges again. Only need to consider dirty edges since it makes sure that the new
		// set of connections is a super set of the old
		for (int i = 0; i < dirtyVertexes.size(); i++) {
			dirtyVertexes.get(i).pruneNonMutal(EdgeType.CONNECTION);
			dirtyVertexes.get(i).marked = false;
		}

		// Final clean up to return just valid grids
		disconnectInvalidVertices();

		// Name says it all
		convertToOutput(corners);
	}
1235288
def _build_vertex_data(self):
        
        grid = self._grid
        w = 1.0 / grid[1]
        h = 1.0 / grid[0]

        quad = np.array([[0, 0, 0], [w, 0, 0], [w, h, 0],
                         [0, 0, 0], [w, h, 0], [0, h, 0]],
                        dtype=np.float32)
        quads = np.empty((grid[1], grid[0], 6, 3), dtype=np.float32)
        quads[:] = quad

        mgrid = np.mgrid[0.:grid[1], 0.:grid[0]].transpose(1, 2, 0)
        mgrid = mgrid[:, :, np.newaxis, :]
        mgrid[..., 0] *= w
        mgrid[..., 1] *= h

        quads[..., :2] += mgrid
        tex_coords = quads.reshape(grid[1]*grid[0]*6, 3)
        tex_coords = np.ascontiguousarray(tex_coords[:, :2])
        vertices = tex_coords * self.size

        self._subdiv_position.set_data(vertices.astype('float32'))
        self._subdiv_texcoord.set_data(tex_coords.astype('float32'))
1195991
private SquareGrid assembleGrid( List<List<SquareNode>> listRows) {
		SquareGrid grid = grids.grow();
		grid.reset();

		List<SquareNode> row0 = listRows.get(0);
		List<SquareNode> row1 = listRows.get(1);

		int offset = row0.get(0).getNumberOfConnections() == 1 ? 0 : 1;

		grid.columns = row0.size() + row1.size();
		grid.rows = listRows.size();

		// initialize grid to null
		for (int i = 0; i < grid.columns * grid.rows; i++) {
			grid.nodes.add(null);
		}

		// fill in the grid
		for (int row = 0; row < listRows.size(); row++) {
			List<SquareNode> list = listRows.get(row);
			int startCol = offset - row%2 == 0 ? 0 : 1;
			// make sure there is the expected number of elements in the row
			int adjustedLength = grid.columns-startCol;
			if( (adjustedLength)-adjustedLength/2 != list.size() ) {
				return null;
			}
			int listIndex = 0;
			for (int col = startCol; col < grid.columns; col += 2) {
				grid.set(row,col,list.get(listIndex++));
			}
		}
		return grid;
	}
1226185
def write_grid_to_vtk(fname, nodes, edges, node_flag=None, edge_flag=None):
    

    if node_flag is None:
        node_flag = np.ones([nodes.shape[0]], dtype=np.bool)
    if edge_flag is None:
        edge_flag = np.ones([edges.shape[0]], dtype=np.bool)
    nodes = make_nodes_3d(nodes)
    f = open(fname, "w")

    f.write("# vtk DataFile Version 2.6\n")
    f.write("output file\nASCII\nDATASET UNSTRUCTURED_GRID\n")

    idxs = nm.where(node_flag > 0)[0]
    nnd = len(idxs)
    aux = -nm.ones(node_flag.shape, dtype=nm.int32)
    aux[idxs] = nm.arange(nnd, dtype=nm.int32)
    f.write("\nPOINTS %d float\n" % nnd)
    for ndi in idxs:
        f.write("%.6f %.6f %.6f\n" % tuple(nodes[ndi, :]))

    idxs = nm.where(edge_flag > 0)[0]
    ned = len(idxs)
    f.write("\nCELLS %d %d\n" % (ned, ned * 3))
    for edi in idxs:
        f.write("2 %d %d\n" % tuple(aux[edges[edi, :]]))

    f.write("\nCELL_TYPES %d\n" % ned)
    for edi in idxs:
        f.write("3\n")
199237
def find_connection(v1, v2)
      raise "not a vertex" unless v1.is_a?(Vertex) && v2.is_a?(Vertex)
      raise "Vertices not connected" if !is_connected?(v1, v2)
      connection = v1.edges.select {|edge| edge.connection.include?(v2)}
      raise "Error finding connection" if connection.length > 1
      connection.first
    end
683250
public Result<Tupple2<float[], float[]>> getOffMeshConnectionPolyEndPoints(long prevRef, long polyRef) {
        if (polyRef == 0) {
            return Result.invalidParam("polyRef = 0");
        }

        // Get current polygon
        int[] saltitip = decodePolyId(polyRef);
        int salt = saltitip[0];
        int it = saltitip[1];
        int ip = saltitip[2];
        if (it >= m_maxTiles) {
            return Result.invalidParam("Invalid tile ID > max tiles");
        }
        if (m_tiles[it].salt != salt || m_tiles[it].data.header == null) {
            return Result.invalidParam("Invalid salt or missing tile header");
        }
        MeshTile tile = m_tiles[it];
        if (ip >= tile.data.header.polyCount) {
            return Result.invalidParam("Invalid poly ID > poly count");
        }
        Poly poly = tile.data.polys[ip];

        // Make sure that the current poly is indeed off-mesh link.
        if (poly.getType() != Poly.DT_POLYTYPE_OFFMESH_CONNECTION) {
            return Result.invalidParam("Invalid poly type");
        }

        // Figure out which way to hand out the vertices.
        int idx0 = 0, idx1 = 1;

        // Find link that points to first vertex.
        for (int i = poly.firstLink; i != DT_NULL_LINK; i = tile.links.get(i).next) {
            if (tile.links.get(i).edge == 0) {
                if (tile.links.get(i).ref != prevRef) {
                    idx0 = 1;
                    idx1 = 0;
                }
                break;
            }
        }
        float[] startPos = new float[3];
        float[] endPos = new float[3];
        vCopy(startPos, tile.data.verts, poly.verts[idx0] * 3);
        vCopy(endPos, tile.data.verts, poly.verts[idx1] * 3);
        return Result.success(new Tupple2<>(startPos, endPos));

    }
679933
def _get_connected_subgraphs(vertices, vertices_neighbours):
    
    remaining_vertices = set(vertices)
    subgraphs = []
    while remaining_vertices:
        subgraph = set(_dfs(remaining_vertices.pop(), vertices_neighbours))
        remaining_vertices.difference_update(subgraph)
        subgraphs.append(subgraph)

    return subgraphs
210781
def outputConnections(self, cls=None):
        
        scene = self.scene()
        if not scene:
            return []
        
        if not cls:
            cls = XNodeConnection
        
        output = []
        for item in scene.items():
            if not isinstance(item, cls):
                continue
            
            if item.outputNode() == self:
                output.append(item)
        
        return output