Finds corners in list 1 which match corners in list 0. If the feature in list 0 has already been
seen then the feature in list 1 will be marked as seen. Otherwise the feature which is the most intense
is marked as first.
559801
void markSeenAsFalse(FastQueue<ChessboardCorner> corners0 , FastQueue<ChessboardCorner> corners1 ) {
		nn.setPoints(corners1.toList(),false);
		// radius of the blob in the intensity image is 2*kernelRadius
		int radius = detector.shiRadius *2+1;
		for (int i = 0; i < corners0.size; i++) {
			ChessboardCorner c0 = corners0.get(i);
			nnSearch.findNearest(c0,radius,5,nnResults);
			// TODO does it ever find multiple matches?

			// Could make this smarter by looking at the orientation too
			for (int j = 0; j < nnResults.size; j++) {
				ChessboardCorner c1 = nnResults.get(j).point;

				// if the current one wasn't first then none of its children can be first
				if( !c0.first ) {
					c1.first = false;
				} else if( c1.intensity < c0.intensity ) {
					// keeping the one with the best intensity score seems to help. Formally test this idea
					c1.first = false;
				} else {
					c0.first = false;
				}
			}
		}
	}
264194
function(p1, p2, check_walls, check_items) {
        var minres = false;
        
        // collide with walls
        if(check_walls) {
          for(var i=0,n=this.walls.length;i<n;i++) {
            var wall = this.walls[i];
            var res = line_intersect(p1, p2, wall.p1, wall.p2);
            if(res) {
              res.type = 0; // 0 is wall
              if(!minres) { minres=res; }
              else {
                // check if its closer
                if(res.ua < minres.ua) {
                  // if yes replace it
                  minres = res;
                }
              }
            }
          }
        }
        
        // collide with items
        if(check_items) {
          for(var i=0,n=this.items.length;i<n;i++) {
            var it = this.items[i];
            var res = line_point_intersect(p1, p2, it.p, it.rad);
            if(res) {
              res.type = it.type; // store type of item
              if(!minres) { minres=res; }
              else { if(res.ua < minres.ua) { minres = res; }
              }
            }
          }
        }
        
        return minres;
      }
761668
boolean fitLinesUsingCorners( int numLines , GrowQueue_I32 cornerIndexes) {
		for (int i = 1; i <= numLines; i++) {
			int index0 = cornerIndexes.get(CircularIndex.addOffset(anchor0, i - 1, cornerIndexes.size));
			int index1 = cornerIndexes.get(CircularIndex.addOffset(anchor0, i, cornerIndexes.size));

			if( index0 == index1 )
				return false;

			if (!fitLine(index0, index1, lines.get(i - 1))) {
				// TODO do something more intelligent here.  Just leave the corners as is?
				return false;
			}
			LineGeneral2D_F64 l = lines.get(i-1);
			if( Double.isNaN(l.A) || Double.isNaN(l.B) || Double.isNaN(l.C)) {
				throw new RuntimeException("This should be impossible");
			}
		}
		return true;
	}
855661
def p_feature_contains(self, t):
        """"""

        t[0] = Feature(t[1], t[2], Features(t[4]), line=t.lineno(1))
549629
private void intersectShape (List<Edge> edges, double[] coords1, int length1,
                                 double[] coords2, int length2, Edge initEdge) {
        int areaOfEdge1, areaOfEdge2;
        int initBegin, initEnd;
        int addBegin, addEnd;
        double x1, y1, x2, y2, x3, y3, x4, y4;
        double[] point = new double[2];
        Edge edge;

        if (initEdge.areaNumber == 0) {
            x1 = coords1[2 * initEdge.begIndex];
            y1 = coords1[2 * initEdge.begIndex + 1];
            x2 = coords1[2 * initEdge.endIndex];
            y2 = coords1[2 * initEdge.endIndex + 1];
            areaOfEdge1 = 0;
        } else {
            x1 = coords2[2 * initEdge.begIndex];
            y1 = coords2[2 * initEdge.begIndex + 1];
            x2 = coords2[2 * initEdge.endIndex];
            y2 = coords2[2 * initEdge.endIndex + 1];
            areaOfEdge1 = 1;
        }

        for (Iterator<Edge> iter = edges.iterator(); iter.hasNext();) {
            edge = iter.next();

            if (edge.areaNumber == 0) {
                x3 = coords1[2 * edge.begIndex];
                y3 = coords1[2 * edge.begIndex + 1];
                x4 = coords1[2 * edge.endIndex];
                y4 = coords1[2 * edge.endIndex + 1];
                areaOfEdge2 = 0;
            } else {
                x3 = coords2[2 * edge.begIndex];
                y3 = coords2[2 * edge.begIndex + 1];
                x4 = coords2[2 * edge.endIndex];
                y4 = coords2[2 * edge.endIndex + 1];
                areaOfEdge2 = 1;
            }

            if ((areaOfEdge1 != areaOfEdge2) &&
                (GeometryUtil.intersectLines(x1, y1, x2, y2, x3, y3, x4, y4, point) == 1) &&
                (!containsPoint(point))) {

                if (initEdge.areaNumber == 0) {
                    initBegin = initEdge.begIndex;
                    initEnd = initEdge.endIndex;
                    addBegin = edge.begIndex;
                    addEnd = edge.endIndex;
                } else {
                    initBegin = edge.begIndex;
                    initEnd = edge.endIndex;
                    addBegin = initEdge.begIndex;
                    addEnd = initEdge.endIndex;
                }

                if (((initEnd == length1 - 1) && (initBegin == 0 && initEnd > initBegin)) ||
                    (((initEnd != length1 - 1) || (initBegin != 0)) &&
                     ((initBegin != length1 - 1) || (initEnd != 0)) && (initBegin > initEnd))) {
                    int temp = initBegin;
                    initBegin = initEnd;
                    initEnd = temp;
                }

                if (((addEnd == length2 - 1) && (addBegin == 0) && (addEnd > addBegin)) ||
                    (((addEnd != length2 - 1) || (addBegin != 0)) &&
                     ((addBegin != length2 - 1) || (addEnd != 0)) && (addBegin > addEnd))) {
                    int temp = addBegin;
                    addBegin = addEnd;
                    addEnd = temp;
                }

                IntersectPoint ip;
                for (Iterator<IntersectPoint> i = isectPoints.iterator(); i.hasNext();) {
                    ip = i.next();
                    if ((initBegin == ip.begIndex(true)) && (initEnd == ip.endIndex(true))) {
                        if (compare(ip.x(), ip.y(), point[0], point[1]) > 0) {
                            initEnd = -(isectPoints.indexOf(ip) + 1);
                            ip.setBegIndex1(-(isectPoints.size() + 1));
                        } else {
                            initBegin = -(isectPoints.indexOf(ip) + 1);
                            ip.setEndIndex1(-(isectPoints.size() + 1));
                        }
                    }

                    if ((addBegin == ip.begIndex(false)) && (addEnd == ip.endIndex(false))) {
                        if (compare(ip.x(), ip.y(), point[0], point[1]) > 0) {
                            addEnd = -(isectPoints.indexOf(ip) + 1);
                            ip.setBegIndex2(-(isectPoints.size() + 1));
                        } else {
                            addBegin = -(isectPoints.indexOf(ip) + 1);
                            ip.setEndIndex2(-(isectPoints.size() + 1));
                        }
                    }
                }

                isectPoints.add(new IntersectPoint(initBegin, initEnd, addBegin, addEnd,
                                                   point[0], point[1]));
            }
        }
    }
882492
public void queryCorners(Point2D[] corners) {
		if ((corners == null) || (corners.length < 4))
			throw new IllegalArgumentException();
		if (corners[0] != null)
			corners[0].setCoords(xmin, ymin);
		else
			corners[0] = new Point2D(xmin, ymin);

		if (corners[1] != null)
			corners[1].setCoords(xmin, ymax);
		else
			corners[1] = new Point2D(xmin, ymax);

		if (corners[2] != null)
			corners[2].setCoords(xmax, ymax);
		else
			corners[2] = new Point2D(xmax, ymax);

		if (corners[3] != null)
			corners[3].setCoords(xmax, ymin);
		else
			corners[3] = new Point2D(xmax, ymin);
	}
489456
def match_positions(shape, list_of_coords):
    
    match_array = np.zeros(shape)
    try:
        # excpetion hit on this line if nothing in list_of_coords- i.e. no matches
        match_array[list_of_coords[:,0],list_of_coords[:,1]] = 1
        labelled = label(match_array)
        objects = find_objects(labelled[0])
        coords = [{'x':(slice_x.start, slice_x.stop),'y':(slice_y.start, slice_y.stop)} for (slice_y,slice_x) in objects]
        final_positions = [(int(np.mean(coords[i]['x'])),int(np.mean(coords[i]['y']))) for i in range(len(coords))]
        return final_positions
    except IndexError:
        print 'no matches found'
        # this error occurs if no matches are found
        return []
1205351
def check_boundary_lines_similar(l_1, l_2):
    
    num_matches = 0
    if (type(l_1) != list) or (type(l_2) != list) or (len(l_1) != len(l_2)):
        # these 'boundaries' are not similar
        return 0

    num_elements = len(l_1)
    for i in xrange(0, num_elements):
        if l_1[i].isdigit() and l_2[i].isdigit():
            # both lines are integers
            num_matches += 1
        else:
            l1_str = l_1[i].lower()
            l2_str = l_2[i].lower()
            if (l1_str[0] == l2_str[0]) and \
                    (l1_str[len(l1_str) - 1] == l2_str[len(l2_str) - 1]):
                num_matches = num_matches + 1
    if (len(l_1) == 0) or (float(num_matches) / float(len(l_1)) < 0.9):
        return 0
    else:
        return 1
848009
def find_close_value(self, LIST, value):
        '''
        
        '''
        diff = inf
        for a in LIST:
            if abs(value - a) < diff:
                diff = abs(value - a)
                result = a
        return(result)
52560
def findViewsContainingPoint(self, (x, y), _filter=None):
        '''
        
        '''

        if not _filter:
            _filter = lambda v: True

        return [v for v in self.views if (v.containsPoint((x,y)) and _filter(v))]
1069705
def _find_edge_intersections(self):
        
        edges = self.pts[self.edges]
        cuts = {}  # { edge: [(intercept, point), ...], ... }
        for i in range(edges.shape[0]-1):
            # intersection of edge i onto all others
            int1 = self._intersect_edge_arrays(edges[i:i+1], edges[i+1:])
            # intersection of all edges onto edge i
            int2 = self._intersect_edge_arrays(edges[i+1:], edges[i:i+1])
        
            # select for pairs that intersect
            err = np.geterr()
            np.seterr(divide='ignore', invalid='ignore')
            try:
                mask1 = (int1 >= 0) & (int1 <= 1)
                mask2 = (int2 >= 0) & (int2 <= 1)
                mask3 = mask1 & mask2  # all intersections
            finally:
                np.seterr(**err)
            
            # compute points of intersection
            inds = np.argwhere(mask3)[:, 0]
            if len(inds) == 0:
                continue
            h = int2[inds][:, np.newaxis]
            pts = (edges[i, 0][np.newaxis, :] * (1.0 - h) + 
                   edges[i, 1][np.newaxis, :] * h)
            
            # record for all edges the location of cut points
            edge_cuts = cuts.setdefault(i, [])
            for j, ind in enumerate(inds):
                if 0 < int2[ind] < 1:
                    edge_cuts.append((int2[ind], pts[j]))
                if 0 < int1[ind] < 1:
                    other_cuts = cuts.setdefault(ind+i+1, [])
                    other_cuts.append((int1[ind], pts[j]))
        
        # sort all cut lists by intercept, remove duplicates
        for k, v in cuts.items():
            v.sort(key=lambda x: x[0])
            for i in range(len(v)-2, -1, -1):
                if v[i][0] == v[i+1][0]:
                    v.pop(i+1)
        return cuts
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);
	}
1311612
private void matchInstances(@NonNull ArrayMap<View, TransitionValues> unmatchedStart,
                                @NonNull ArrayMap<View, TransitionValues> unmatchedEnd) {
        for (int i = unmatchedStart.size() - 1; i >= 0; i--) {
            View view = unmatchedStart.keyAt(i);
            if (view != null && isValidTarget(view)) {
                TransitionValues end = unmatchedEnd.remove(view);
                if (end != null && isValidTarget(end.view)) {
                    TransitionValues start = unmatchedStart.removeAt(i);
                    mStartValuesList.add(start);
                    mEndValuesList.add(end);
                }
            }
        }
    }
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
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
882323
void sortEdgesCCW(FastQueue<Node> corners) {
		for (int nodeIdx = 0; nodeIdx < corners.size; nodeIdx++) {
			Node na = corners.get(nodeIdx);

			// reference node to do angles relative to.
			double ref = Double.NaN;
			int count = 0;
			for (int i = 0; i < 4; i++) {
				order[i] = i;
				tmpEdges[i] = na.edges[i];
				if( na.edges[i] == null ) {
					directions[i] = Double.MAX_VALUE;
				} else {
					Node nb = na.edges[i];
					double angleB = Math.atan2(nb.y-na.y,nb.x-na.x);
					if( Double.isNaN(ref) ) {
						ref = angleB;
						directions[i] = 0;
					} else {
						directions[i] = UtilAngle.distanceCCW(ref,angleB);
					}
					count++;
				}
			}

			sorter.sort(directions,0,4,order);
			for (int i = 0; i < 4; i++) {
				na.edges[i] = tmpEdges[ order[i] ];
			}
			if( count == 2 ) {
				// If there are only two then we define the order to be defined by the one which minimizes
				// CCW direction
				if( directions[order[1]] > Math.PI ) {
					na.edges[0] = tmpEdges[ order[1] ];
					na.edges[1] = tmpEdges[ order[0] ];
				} else {
					na.edges[0] = tmpEdges[ order[0] ];
					na.edges[1] = tmpEdges[ order[1] ];
				}
			} else if( count == 3 ) {
				// Edges need to point along the 4 possible directions, in the case of 3 edges, there might
				// need to be a gap at a different location than at the end
				int selected = -1;
				double largestAngle = 0;
				for (int i = 0,j=2; i < 3; j=i,i++) {
					double ccw = UtilAngle.distanceCCW(directions[order[j]],directions[order[i]]);
					if( ccw > largestAngle ) {
						largestAngle = ccw;
						selected = j;
					}
				}

				for (int i = 2; i > selected; i--) {
					na.edges[i+1] = na.edges[i];
				}
				na.edges[selected+1]=null;

			}
		}
	}
165784
def overlap(listA, listB):
    
    if (listA is None) or (listB is None):
        return []
    else:
        return list(set(listA) & set(listB))