get the next search direction from two simplex points
763433
function getNextSearchDir( ptA, ptB, dir ){

        var ABdotB = ptB.normSq() - ptB.dot( ptA )
            ,ABdotA = ptB.dot( ptA ) - ptA.normSq()
            ;

        // if the origin is farther than either of these points
        // get the direction from one of those points to the origin
        if ( ABdotB < 0 ){

            return dir.clone( ptB ).negate();

        } else if ( ABdotA > 0 ){

            return dir.clone( ptA ).negate();

        // otherwise, use the perpendicular direction from the simplex
        } else {

            // dir = AB = B - A
            dir.clone( ptB ).vsub( ptA );
            // if (left handed coordinate system)
            // A cross AB < 0 then get perpendicular counterclockwise
            return dir.perp( (ptA.cross( dir ) > 0) );
        }
    }
1014598
def index_next_crossing(value, array, starting_index=0, direction=1):
    

    for n in range(starting_index, len(array)-1):
        if  (value-array[n]  )*direction >= 0         \
        and (value-array[n+1])*direction <  0: return n

    # no crossing found
    return -1
889805
private void findStartingPoint() {
    // Well, we already know the best Y value...
    final double bestY = minmaxY.getMin();
    double bestX = Double.POSITIVE_INFINITY;
    int bestI = -1;
    Iterator<double[]> iter = this.points.iterator();
    for(int i = 0; iter.hasNext(); i++) {
      double[] vec = iter.next();
      if(vec[1] == bestY && vec[0] < bestX) {
        bestX = vec[0];
        bestI = i;
      }
    }
    assert (bestI >= 0);
    // Bring the reference object to the head.
    if(bestI > 0) {
      points.add(0, points.remove(bestI));
    }
  }
514501
def next(self):
        """"""
        rv = self.current
        self.pos = (self.pos + 1) % len(self.items)
        return rv
1092790
def inxsearch(self, r, g, b):
        """"""
        dists = (self.colormap[:, :3] - np.array([r, g, b]))
        a = np.argmin((dists * dists).sum(1))
        return a
55464
def direction_vector(self, other: "Point2") -> "Point2":
        
        return self.__class__((_sign(other.x - self.x), _sign(other.y - self.y)))
492433
function getDirection(x, y) {
  if (x === y) {
    return DIRECTION_NONE;
  }

  if (abs(x) >= abs(y)) {
    return x > 0 ? DIRECTION_LEFT : DIRECTION_RIGHT;
  }
  return y > 0 ? DIRECTION_UP : DIRECTION_DOWN;
}
603540
def next(self):
        
        while True:
            x, y = next(self.scan)
            if self.predicate is not None and not self.predicate(x,y):
                if self.abort: raise StopIteration("Boundary crossed!")
            elif (x < self.minx or
                x > self.maxx or
                y < self.miny or
                y > self.maxy):
                if self.abort: raise StopIteration("Boundary crossed!")
            else:
                return x, y
627725
function (p1, p2) {
    let direction = p2.minus(p1)
    let labda = (this.w - this.normal.dot(p1)) / this.normal.dot(direction)
    if (isNaN(labda)) labda = 0
    if (labda > 1) labda = 1
    if (labda < 0) labda = 0
    let result = p1.plus(direction.times(labda))
    return result
  }
1131457
def find_next(start, stop, i2hits):
    
    if start not in i2hits and stop in i2hits:
        index = stop
    elif stop not in i2hits and start in i2hits:
        index = start
    elif start not in i2hits and stop not in i2hits:
        index = choice([start, stop])
        i2hits[index] = [[False]]
    else:
        A, B = i2hits[start][0], i2hits[stop][0]
        if B[10] <= A[10]:
            index = stop
        else:
            index = start
    if index == start:
        nstart = start - 1
        nstop = stop
    else:
        nstop = stop + 1
        nstart = start
    match = i2hits[index][0]
    rp = match[-1]
    return index, nstart, nstop, rp, match
167018
def direction(self):
        
        libfn = utils.get_lib_fn('getDirection%s'%self._libsuffix)
        return libfn(self.pointer)
653608
public static List<Point> getPath (
        TraversalPred tpred, Object trav, int longest,
        int ax, int ay, int bx, int by, boolean partial)
    {
        return getPath(tpred, new Stepper(), trav, longest, ax, ay, bx, by, partial);
    }
631763
def check_next_match(self, match, new_relations, subject_graph, one_match):
        """"""
        # avoid duplicate rings (order of traversal)
        if len(match) == 3:
            if match.forward[1] < match.forward[2]:
                #print "RingPattern.check_next_match: duplicate order", match.forward[1], match.forward[2]
                return False
        # avoid duplicate rings (starting point)
        for vertex1 in new_relations.values():
            if vertex1 < match.forward[0]:
                #print "RingPattern.check_next_match: duplicate start", vertex1, match.forward[0]
                return False
        # can this ever become a strong ring?
        for vertex1 in new_relations.values():
            paths = list(subject_graph.iter_shortest_paths(vertex1, match.forward[0]))
            if len(paths) != 1:
                #print "RingPattern.check_next_match: not strong 1"
                return False
            if len(paths[0]) != (len(match)+1)//2:
                #print "RingPattern.check_next_match: not strong 2"
                return False
        return True
413808
function closestPointnd(c, positions, x, result) {
  var D = numeric.rep([c.length, c.length], 0.0);
  var dvec = numeric.rep([c.length], 0.0);
  for(var i=0; i<c.length; ++i) {
    var pi = positions[c[i]];
    dvec[i] = numeric.dot(pi, x);
    for(var j=0; j<c.length; ++j) {
      var pj = positions[c[j]];
      D[i][j] = D[j][i] = numeric.dot(pi, pj);
    }
  }
  var A = numeric.rep([c.length, c.length+2], 0.0);
  var b = numeric.rep([c.length+2], 0.0);
  b[0] = 1.0-EPSILON;
  b[1] = -(1.0+EPSILON);
  for(var i=0; i<c.length; ++i) {
    A[i][0]   = 1;
    A[i][1]   = -1
    A[i][i+2] = 1;
  }
  for(var attempts=0; attempts<15; ++attempts) {
    var fortran_poop = numeric.solveQP(D, dvec, A, b);
    if(fortran_poop.message.length > 0) {
      //Quadratic form may be singular, perturb and resolve
      for(var i=0; i<c.length; ++i) {
        D[i][i] += 1e-8;
      }
      continue;
    } else if(isNaN(fortran_poop.value[0])) {
      break;
    } else {
      //Success!
      var solution = fortran_poop.solution;
      for(var i=0; i<x.length; ++i) {
        result[i] = 0.0;
        for(var j=0; j<solution.length; ++j) {
          result[i] += solution[j] * positions[c[j]][i];
        }
      }
      return 2.0 * fortran_poop.value[0] + numeric.dot(x,x);
    }
  }
  for(var i=0; i<x.length; ++i) {
    result[i] = Number.NaN;
  }
  return Number.NaN;
}
475288
function (bounds, vertex, next, orthogonal)
	{
		var x = bounds.x;
		var y = bounds.y;
		var w = bounds.width;
		var h = bounds.height;

		var cx = bounds.getCenterX();
		var cy = bounds.getCenterY();
		var px = next.x;
		var py = next.y;
		var dx = px - cx;
		var dy = py - cy;
		var alpha = -Math.atan2(dy, dx);
		var pi = Math.PI;
		var pi2 = Math.PI / 2;

		var result = new mxPoint(cx, cy);

		var direction = (vertex != null) ? mxUtils.getValue(
				vertex.style, mxConstants.STYLE_DIRECTION,
				mxConstants.DIRECTION_EAST) : mxConstants.DIRECTION_EAST;
		var vertical = direction == mxConstants.DIRECTION_NORTH
				|| direction == mxConstants.DIRECTION_SOUTH;
		var a = new mxPoint();
		var b = new mxPoint();

		//Only consider corrects quadrants for the orthogonal case.
		if ((px < x) && (py < y) || (px < x) && (py > y + h)
				|| (px > x + w) && (py < y) || (px > x + w) && (py > y + h))
		{
			orthogonal = false;
		}

		if (orthogonal)
		{
			if (vertical)
			{
				//Special cases where intersects with hexagon corners
				if (px == cx)
				{
					if (py <= y)
					{
						return new mxPoint(cx, y);
					}
					else if (py >= y + h)
					{
						return new mxPoint(cx, y + h);
					}
				}
				else if (px < x)
				{
					if (py == y + h / 4)
					{
						return new mxPoint(x, y + h / 4);
					}
					else if (py == y + 3 * h / 4)
					{
						return new mxPoint(x, y + 3 * h / 4);
					}
				}
				else if (px > x + w)
				{
					if (py == y + h / 4)
					{
						return new mxPoint(x + w, y + h / 4);
					}
					else if (py == y + 3 * h / 4)
					{
						return new mxPoint(x + w, y + 3 * h / 4);
					}
				}
				else if (px == x)
				{
					if (py < cy)
					{
						return new mxPoint(x, y + h / 4);
					}
					else if (py > cy)
					{
						return new mxPoint(x, y + 3 * h / 4);
					}
				}
				else if (px == x + w)
				{
					if (py < cy)
					{
						return new mxPoint(x + w, y + h / 4);
					}
					else if (py > cy)
					{
						return new mxPoint(x + w, y + 3 * h / 4);
					}
				}
				if (py == y)
				{
					return new mxPoint(cx, y);
				}
				else if (py == y + h)
				{
					return new mxPoint(cx, y + h);
				}

				if (px < cx)
				{
					if ((py > y + h / 4) && (py < y + 3 * h / 4))
					{
						a = new mxPoint(x, y);
						b = new mxPoint(x, y + h);
					}
					else if (py < y + h / 4)
					{
						a = new mxPoint(x - Math.floor(0.5 * w), y
								+ Math.floor(0.5 * h));
						b = new mxPoint(x + w, y - Math.floor(0.25 * h));
					}
					else if (py > y + 3 * h / 4)
					{
						a = new mxPoint(x - Math.floor(0.5 * w), y
								+ Math.floor(0.5 * h));
						b = new mxPoint(x + w, y + Math.floor(1.25 * h));
					}
				}
				else if (px > cx)
				{
					if ((py > y + h / 4) && (py < y + 3 * h / 4))
					{
						a = new mxPoint(x + w, y);
						b = new mxPoint(x + w, y + h);
					}
					else if (py < y + h / 4)
					{
						a = new mxPoint(x, y - Math.floor(0.25 * h));
						b = new mxPoint(x + Math.floor(1.5 * w), y
								+ Math.floor(0.5 * h));
					}
					else if (py > y + 3 * h / 4)
					{
						a = new mxPoint(x + Math.floor(1.5 * w), y
								+ Math.floor(0.5 * h));
						b = new mxPoint(x, y + Math.floor(1.25 * h));
					}
				}

			}
			else
			{
				//Special cases where intersects with hexagon corners
				if (py == cy)
				{
					if (px <= x)
					{
						return new mxPoint(x, y + h / 2);
					}
					else if (px >= x + w)
					{
						return new mxPoint(x + w, y + h / 2);
					}
				}
				else if (py < y)
				{
					if (px == x + w / 4)
					{
						return new mxPoint(x + w / 4, y);
					}
					else if (px == x + 3 * w / 4)
					{
						return new mxPoint(x + 3 * w / 4, y);
					}
				}
				else if (py > y + h)
				{
					if (px == x + w / 4)
					{
						return new mxPoint(x + w / 4, y + h);
					}
					else if (px == x + 3 * w / 4)
					{
						return new mxPoint(x + 3 * w / 4, y + h);
					}
				}
				else if (py == y)
				{
					if (px < cx)
					{
						return new mxPoint(x + w / 4, y);
					}
					else if (px > cx)
					{
						return new mxPoint(x + 3 * w / 4, y);
					}
				}
				else if (py == y + h)
				{
					if (px < cx)
					{
						return new mxPoint(x + w / 4, y + h);
					}
					else if (py > cy)
					{
						return new mxPoint(x + 3 * w / 4, y + h);
					}
				}
				if (px == x)
				{
					return new mxPoint(x, cy);
				}
				else if (px == x + w)
				{
					return new mxPoint(x + w, cy);
				}

				if (py < cy)
				{
					if ((px > x + w / 4) && (px < x + 3 * w / 4))
					{
						a = new mxPoint(x, y);
						b = new mxPoint(x + w, y);
					}
					else if (px < x + w / 4)
					{
						a = new mxPoint(x - Math.floor(0.25 * w), y + h);
						b = new mxPoint(x + Math.floor(0.5 * w), y
								- Math.floor(0.5 * h));
					}
					else if (px > x + 3 * w / 4)
					{
						a = new mxPoint(x + Math.floor(0.5 * w), y
								- Math.floor(0.5 * h));
						b = new mxPoint(x + Math.floor(1.25 * w), y + h);
					}
				}
				else if (py > cy)
				{
					if ((px > x + w / 4) && (px < x + 3 * w / 4))
					{
						a = new mxPoint(x, y + h);
						b = new mxPoint(x + w, y + h);
					}
					else if (px < x + w / 4)
					{
						a = new mxPoint(x - Math.floor(0.25 * w), y);
						b = new mxPoint(x + Math.floor(0.5 * w), y
								+ Math.floor(1.5 * h));
					}
					else if (px > x + 3 * w / 4)
					{
						a = new mxPoint(x + Math.floor(0.5 * w), y
								+ Math.floor(1.5 * h));
						b = new mxPoint(x + Math.floor(1.25 * w), y);
					}
				}
			}

			var tx = cx;
			var ty = cy;

			if (px >= x && px <= x + w)
			{
				tx = px;
				
				if (py < cy)
				{
					ty = y + h;
				}
				else
				{
					ty = y;
				}
			}
			else if (py >= y && py <= y + h)
			{
				ty = py;
				
				if (px < cx)
				{
					tx = x + w;
				}
				else
				{
					tx = x;
				}
			}

			result = mxUtils.intersection(tx, ty, next.x, next.y, a.x, a.y, b.x, b.y);
		}
		else
		{
			if (vertical)
			{
				var beta = Math.atan2(h / 4, w / 2);

				//Special cases where intersects with hexagon corners
				if (alpha == beta)
				{
					return new mxPoint(x + w, y + Math.floor(0.25 * h));
				}
				else if (alpha == pi2)
				{
					return new mxPoint(x + Math.floor(0.5 * w), y);
				}
				else if (alpha == (pi - beta))
				{
					return new mxPoint(x, y + Math.floor(0.25 * h));
				}
				else if (alpha == -beta)
				{
					return new mxPoint(x + w, y + Math.floor(0.75 * h));
				}
				else if (alpha == (-pi2))
				{
					return new mxPoint(x + Math.floor(0.5 * w), y + h);
				}
				else if (alpha == (-pi + beta))
				{
					return new mxPoint(x, y + Math.floor(0.75 * h));
				}

				if ((alpha < beta) && (alpha > -beta))
				{
					a = new mxPoint(x + w, y);
					b = new mxPoint(x + w, y + h);
				}
				else if ((alpha > beta) && (alpha < pi2))
				{
					a = new mxPoint(x, y - Math.floor(0.25 * h));
					b = new mxPoint(x + Math.floor(1.5 * w), y
							+ Math.floor(0.5 * h));
				}
				else if ((alpha > pi2) && (alpha < (pi - beta)))
				{
					a = new mxPoint(x - Math.floor(0.5 * w), y
							+ Math.floor(0.5 * h));
					b = new mxPoint(x + w, y - Math.floor(0.25 * h));
				}
				else if (((alpha > (pi - beta)) && (alpha <= pi))
						|| ((alpha < (-pi + beta)) && (alpha >= -pi)))
				{
					a = new mxPoint(x, y);
					b = new mxPoint(x, y + h);
				}
				else if ((alpha < -beta) && (alpha > -pi2))
				{
					a = new mxPoint(x + Math.floor(1.5 * w), y
							+ Math.floor(0.5 * h));
					b = new mxPoint(x, y + Math.floor(1.25 * h));
				}
				else if ((alpha < -pi2) && (alpha > (-pi + beta)))
				{
					a = new mxPoint(x - Math.floor(0.5 * w), y
							+ Math.floor(0.5 * h));
					b = new mxPoint(x + w, y + Math.floor(1.25 * h));
				}
			}
			else
			{
				var beta = Math.atan2(h / 2, w / 4);

				//Special cases where intersects with hexagon corners
				if (alpha == beta)
				{
					return new mxPoint(x + Math.floor(0.75 * w), y);
				}
				else if (alpha == (pi - beta))
				{
					return new mxPoint(x + Math.floor(0.25 * w), y);
				}
				else if ((alpha == pi) || (alpha == -pi))
				{
					return new mxPoint(x, y + Math.floor(0.5 * h));
				}
				else if (alpha == 0)
				{
					return new mxPoint(x + w, y + Math.floor(0.5 * h));
				}
				else if (alpha == -beta)
				{
					return new mxPoint(x + Math.floor(0.75 * w), y + h);
				}
				else if (alpha == (-pi + beta))
				{
					return new mxPoint(x + Math.floor(0.25 * w), y + h);
				}

				if ((alpha > 0) && (alpha < beta))
				{
					a = new mxPoint(x + Math.floor(0.5 * w), y
							- Math.floor(0.5 * h));
					b = new mxPoint(x + Math.floor(1.25 * w), y + h);
				}
				else if ((alpha > beta) && (alpha < (pi - beta)))
				{
					a = new mxPoint(x, y);
					b = new mxPoint(x + w, y);
				}
				else if ((alpha > (pi - beta)) && (alpha < pi))
				{
					a = new mxPoint(x - Math.floor(0.25 * w), y + h);
					b = new mxPoint(x + Math.floor(0.5 * w), y
							- Math.floor(0.5 * h));
				}
				else if ((alpha < 0) && (alpha > -beta))
				{
					a = new mxPoint(x + Math.floor(0.5 * w), y
							+ Math.floor(1.5 * h));
					b = new mxPoint(x + Math.floor(1.25 * w), y);
				}
				else if ((alpha < -beta) && (alpha > (-pi + beta)))
				{
					a = new mxPoint(x, y + h);
					b = new mxPoint(x + w, y + h);
				}
				else if ((alpha < (-pi + beta)) && (alpha > -pi))
				{
					a = new mxPoint(x - Math.floor(0.25 * w), y);
					b = new mxPoint(x + Math.floor(0.5 * w), y
							+ Math.floor(1.5 * h));
				}
			}

			result = mxUtils.intersection(cx, cy, next.x, next.y, a.x, a.y, b.x, b.y);
		}
		
		if (result == null)
		{
			return new mxPoint(cx, cy);
		}
		
		return result;
	}
1246165
function FindMaxSeparation(poly1, xf1, poly2, xf2) {
  var count1 = poly1.m_count;
  var count2 = poly2.m_count;
  var n1s = poly1.m_normals;
  var v1s = poly1.m_vertices;
  var v2s = poly2.m_vertices;
  var xf = Transform.mulTXf(xf2, xf1);

  var bestIndex = 0;
  var maxSeparation = -Infinity;
  for (var i = 0; i < count1; ++i) {
    // Get poly1 normal in frame2.
    var n = Rot.mulVec2(xf.q, n1s[i]);
    var v1 = Transform.mulVec2(xf, v1s[i]);

    // Find deepest point for normal i.
    var si = Infinity;
    for (var j = 0; j < count2; ++j) {
      var sij = Vec2.dot(n, v2s[j]) - Vec2.dot(n, v1);
      if (sij < si) {
        si = sij;
      }
    }

    if (si > maxSeparation) {
      maxSeparation = si;
      bestIndex = i;
    }
  }

  // used to keep last FindMaxSeparation call values
  FindMaxSeparation._maxSeparation = maxSeparation;
  FindMaxSeparation._bestIndex = bestIndex;
}
1291535
function(seq1, seq2, eq){

    var N = seq1.length,
        M = seq2.length,
        MAX = N + M,
        stepMap = Array.apply(null, {length: M+N+1}).map(function(){return [];}),
        furthestReaching = [],
        dist = -1;

    eq = eq || defaultEqual;

    furthestReaching[MAX + 1] = 0;

    // caculate min distance & log each step
    for(var D = 0; D <= MAX && dist === -1; D++){
        for(var k = -D, x, y, step; k <= D && dist === -1; k+=2){
            if(k === -D || (k !== D && furthestReaching[k - 1 + MAX] < furthestReaching[k + 1 + MAX])){
                x = furthestReaching[k + 1 + MAX];
                step = STEP_INSERT;
            }else{
                x = furthestReaching[k - 1 + MAX] + 1;
                step = STEP_REMOVE;
            }

            y = x - k;
            stepMap[x][y] = step;

            while(x < N && y < M && eq(seq1[x], seq2[y])){
                x++;
                y++;
                stepMap[x][y] = STEP_NOCHANGE;
            }

            furthestReaching[k + MAX] = x;

            if(x >= N && y >= M){
                dist = D;
            }
        }
    }

    return stepMap;
}