finds the intersection of a line and update the corner index
182506
boolean linesIntoCorners( int numLines, GrowQueue_I32 contourCorners ) {

		skippedCorners.reset();

		// this is the index in the contour of the previous corner.  When a new corner is found this is used
		// to see if the newly fit lines point to the same corner.  If that happens a corner is "skipped"
		int contourIndexPrevious = contourCorners.get(anchor0);
		for (int i = 1; i < numLines; i++) {
			LineGeneral2D_F64 line0 = lines.get(i - 1);
			LineGeneral2D_F64 line1 = lines.get(i);

			int cornerIndex = CircularIndex.addOffset(anchor0, i, contourCorners.size);
			boolean skipped = false;

//			System.out.println("  corner index "+cornerIndex);

			if (null == Intersection2D_F64.intersection(line0, line1, intersection)) {
				if( verbose ) System.out.println("  SKIPPING no intersection");
				// the two lines are parallel (or a bug earlier inserted NaN), so skip and remove one of them
				skipped = true;
			} else {

				int contourIndex = closestPoint(intersection);
				if( contourIndex != contourIndexPrevious ) {

					Point2D_I32 a = contour.get(contourIndexPrevious);
					Point2D_I32 b = contour.get(contourIndex);

					if( a.x == b.x && a.y == b.y ) {
						if( verbose ) System.out.println("  SKIPPING duplicate coordinate");
//						System.out.println("  duplicate "+a+" "+b);
						skipped = true;
					} else {
//						System.out.println("contourCorners[ "+cornerIndex+" ] = "+contourIndex);
						contourCorners.set(cornerIndex, contourIndex);
						contourIndexPrevious = contourIndex;
					}
				} else {
					if( verbose ) System.out.println("  SKIPPING duplicate corner index");
					skipped = true;
				}
			}

			if( skipped ) {
				skippedCorners.add( cornerIndex );
			}

		}
		// check the last anchor to see if there's a duplicate
		int cornerIndex = CircularIndex.addOffset(anchor0, numLines, contourCorners.size);
		Point2D_I32 a = contour.get(contourIndexPrevious);
		Point2D_I32 b = contour.get(contourCorners.get(cornerIndex));
		if( a.x == b.x && a.y == b.y ) {
			skippedCorners.add( cornerIndex );
		}

		// now handle all the skipped corners
		Arrays.sort(skippedCorners.data,0,skippedCorners.size);

		for (int i = skippedCorners.size-1; i >= 0; i--) {
			int index = skippedCorners.get(i);
			contourCorners.remove(index);

			if( anchor0 >= index ) {
				anchor0--;
			}
			if( anchor1 >= index ) {
				anchor1--;
			}
		}
//		cornerIndexes.size -= skippedCorners.size();

		numLines -= skippedCorners.size;
		for (int i = 0; i < numLines; i++) {
			int c0 = CircularIndex.addOffset(anchor0, i, contourCorners.size);
			int c1 = CircularIndex.addOffset(anchor0, i+1, contourCorners.size);
			a = contour.get(contourCorners.get(c0));
			b = contour.get(contourCorners.get(c1));

			if( a.x == b.x && a.y == b.y ) {
				throw new RuntimeException("Well I screwed up");
			}

		}

		return contourCorners.size()>=3;
	}
449886
private void intersectionMatrix(int[][] res, ArrayList<int[]> partsx, ArrayList<int[]> partsy, int gridsize) {
    for(int x = 0; x < gridsize; x++) {
      final int[] px = partsx.get(x);
      final int[] rowx = res[x];
      for(int y = 0; y < gridsize; y++) {
        int[] py = partsy.get(y);
        rowx[y] = intersectionSize(px, py);
      }
    }
  }
420503
def intersection_update(self, other):
        
        if not isinstance(other, Set):
            raise ValueError('other must be a Set instance')
        if self is other:
            return
        # we make a copy of the list so that we can remove items from
        # the list without breaking the iterator.
        for item in list(self.items):
            if item not in other.items:
                self.items.remove(item)
834691
function intersection(xArr, yArr, xFilter, yFilter, invert) {
        var i, j, n, filteredX, filteredY, out = invert ? [].concat(xArr) : [];

        for (i = 0, n = xArr.length; i < xArr.length; i++) {
            filteredX = xFilter ? xFilter(xArr[i]) : xArr[i];

            for (j = 0; j < yArr.length; j++) {
                filteredY = yFilter ? yFilter(yArr[j]) : yArr[j];

                if (angular.equals(filteredX, filteredY, xArr, yArr, i, j)) {
                    invert ? out.splice(i + out.length - n, 1) : out.push(yArr[j]);
                    break;
                }
            }
        }
        return out;
    }
736983
function intersection (frame, otherFrame) {
  var x = Math.max(frame.x, otherFrame.x);
  var width = Math.min(frame.x + frame.width, otherFrame.x + otherFrame.width);
  var y = Math.max(frame.y, otherFrame.y);
  var height = Math.min(frame.y + frame.height, otherFrame.y + otherFrame.height);
  if (width >= x && height >= y) {
    return make(x, y, width - x, height - y);
  }
  return null;
}
1370609
def update_line(self, t, x, y, panel='top', **kws):
        
        panel = self.get_panel(panel)
        panel.update_line(t, x, y, **kws)
147305
def bezier_by_line_intersections(bezier, line):
    """"""
    # The method here is to translate (shift) then rotate the complex plane so
    # that line starts at the origin and proceeds along the positive real axis.
    # After this transformation, the intersection points are the real roots of
    # the imaginary component of the bezier for which the real component is
    # between 0 and abs(line[1]-line[0])].
    assert len(line[:]) == 2
    assert line[0] != line[1]
    if not any(p != bezier[0] for p in bezier):
        raise ValueError("bezier is nodal, use "
                         "bezier_by_line_intersection(bezier[0], line) "
                         "instead for a bool to be returned.")

    # First let's shift the complex plane so that line starts at the origin
    shifted_bezier = [z - line[0] for z in bezier]
    shifted_line_end = line[1] - line[0]
    line_length = abs(shifted_line_end)

    # Now let's rotate the complex plane so that line falls on the x-axis
    rotation_matrix = line_length/shifted_line_end
    transformed_bezier = [rotation_matrix*z for z in shifted_bezier]

    # Now all intersections should be roots of the imaginary component of
    # the transformed bezier
    transformed_bezier_imag = [p.imag for p in transformed_bezier]
    coeffs_y = bezier2polynomial(transformed_bezier_imag)
    roots_y = list(polyroots01(coeffs_y))  # returns real roots 0 <= r <= 1

    transformed_bezier_real = [p.real for p in transformed_bezier]
    intersection_list = []
    for bez_t in set(roots_y):
        xval = bezier_point(transformed_bezier_real, bez_t)
        if 0 <= xval <= line_length:
            line_t = xval/line_length
            intersection_list.append((bez_t, line_t))
    return intersection_list
714619
function(pos) {
            var obj, i, intersectionOffset, shape;

            if(this.hitGraphEnabled() && this.isVisible()) {
                for (i=0; i<INTERSECTION_OFFSETS_LEN; i++) {
                    intersectionOffset = INTERSECTION_OFFSETS[i];
                    obj = this._getIntersection({
                        x: pos.x + intersectionOffset.x,
                        y: pos.y + intersectionOffset.y
                    });
                    shape = obj.shape;
                    if (shape) {
                        return shape;
                    }
                    else if (!obj.antialiased) {
                        return null;
                    }
                }
            }
            else {
                return null;
            }
        }
451345
def cornersphere(self, x):
        """"""
        nconstr = len(x) - 0
        if any(x[:nconstr] < 1):
            return np.NaN
        return sum(x**2) - nconstr
259218
function cornerTangents(x0, y0, x1, y1, r1, rc, cw) {
  var x01 = x0 - x1,
      y01 = y0 - y1,
      lo = (cw ? rc : -rc) / sqrt(x01 * x01 + y01 * y01),
      ox = lo * y01,
      oy = -lo * x01,
      x11 = x0 + ox,
      y11 = y0 + oy,
      x10 = x1 + ox,
      y10 = y1 + oy,
      x00 = (x11 + x10) / 2,
      y00 = (y11 + y10) / 2,
      dx = x10 - x11,
      dy = y10 - y11,
      d2 = dx * dx + dy * dy,
      r = r1 - rc,
      D = x11 * y10 - x10 * y11,
      d = (dy < 0 ? -1 : 1) * sqrt(max(0, r * r * d2 - D * D)),
      cx0 = (D * dy - dx * d) / d2,
      cy0 = (-D * dx - dy * d) / d2,
      cx1 = (D * dy + dx * d) / d2,
      cy1 = (-D * dx + dy * d) / d2,
      dx0 = cx0 - x00,
      dy0 = cy0 - y00,
      dx1 = cx1 - x00,
      dy1 = cy1 - y00;

  // Pick the closer of the two intersection points.
  // TODO Is there a faster way to determine which intersection to use?
  if (dx0 * dx0 + dy0 * dy0 > dx1 * dx1 + dy1 * dy1) { cx0 = cx1, cy0 = cy1; }

  return {
    cx: cx0,
    cy: cy0,
    x01: -ox,
    y01: -oy,
    x11: cx0 * (r1 / r - 1),
    y11: cy0 * (r1 / r - 1)
  };
}
1365571
function intersect_line_line(p1, p2, p3, p4) {
		var denom = ((p4.y - p3.y)*(p2.x - p1.x) - (p4.x - p3.x)*(p2.y - p1.y));

		// lines are parallel
		if (denom === 0) {
			return false;
		}

		var ua = ((p4.x - p3.x)*(p1.y - p3.y) - (p4.y - p3.y)*(p1.x - p3.x)) / denom;
		var ub = ((p2.x - p1.x)*(p1.y - p3.y) - (p2.y - p1.y)*(p1.x - p3.x)) / denom;

		if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {
			return false;
		}

		return new Springy.Vector(p1.x + ua * (p2.x - p1.x), p1.y + ua * (p2.y - p1.y));
	}
768536
function(obj) {
    if (!this.intersects(obj)) { return null; }
    if (obj.direction) {
      // obj is a line
      var A = obj.anchor.elements, D = obj.direction.elements,
          P = this.anchor.elements, N = this.normal.elements;
      var multiplier = (N[0]*(P[0]-A[0]) + N[1]*(P[1]-A[1]) + N[2]*(P[2]-A[2])) / (N[0]*D[0] + N[1]*D[1] + N[2]*D[2]);
      return Vector.create([A[0] + D[0]*multiplier, A[1] + D[1]*multiplier, A[2] + D[2]*multiplier]);
    } else if (obj.normal) {
      // obj is a plane
      var direction = this.normal.cross(obj.normal).toUnitVector();
      // To find an anchor point, we find one co-ordinate that has a value
      // of zero somewhere on the intersection, and remember which one we picked
      var N = this.normal.elements, A = this.anchor.elements,
          O = obj.normal.elements, B = obj.anchor.elements;
      var solver = Matrix.Zero(2,2), i = 0;
      while (solver.isSingular()) {
        i++;
        solver = Matrix.create([
          [ N[i%3], N[(i+1)%3] ],
          [ O[i%3], O[(i+1)%3]  ]
        ]);
      }
      // Then we solve the simultaneous equations in the remaining dimensions
      var inverse = solver.inverse().elements;
      var x = N[0]*A[0] + N[1]*A[1] + N[2]*A[2];
      var y = O[0]*B[0] + O[1]*B[1] + O[2]*B[2];
      var intersection = [
        inverse[0][0] * x + inverse[0][1] * y,
        inverse[1][0] * x + inverse[1][1] * y
      ];
      var anchor = [];
      for (var j = 1; j <= 3; j++) {
        // This formula picks the right element from intersection by
        // cycling depending on which element we set to zero above
        anchor.push((i == j) ? 0 : intersection[(j + (5 - i)%3)%3]);
      }
      return Line.create(anchor, direction);
    }
  }
1103579
def lines_intersect(pt1_p, pt2_p, pt1_q, pt2_q):
    '''
    '''
    #
    # The idea here is to do the cross-product of the vector from
    # point 1 to point 2 of one segment against the cross products from 
    # both points of the other segment. If any of the cross products are zero,
    # the point is colinear with the line. If the cross products differ in
    # sign, then one point is on one side of the line and the other is on
    # the other. If that happens for both, then the lines must cross.
    #
    for pt1_a, pt2_a, pt1_b, pt2_b in ((pt1_p, pt2_p, pt1_q, pt2_q),
                                       (pt1_q, pt2_q, pt1_p, pt2_p)):
        v_a = pt2_a-pt1_a
        cross_a_1b = np.cross(v_a, pt1_b-pt2_a)
        if cross_a_1b == 0 and colinear_intersection_test(pt1_a, pt2_a, pt1_b):
            return True
        cross_a_2b = np.cross(v_a, pt2_b-pt2_a)
        if cross_a_2b == 0 and colinear_intersection_test(pt1_a, pt2_a, pt2_b):
            return True
        if (cross_a_1b < 0) == (cross_a_2b < 0):
            return False
    return True
1039047
function(obj) {
                if (!this.line.intersects(obj)) { return null; }
                var P = this.line.intersectionWith(obj);
                return (this.contains(P) ? P : null);
              }
1090512
def segment_intersection1(start0, end0, start1, end1, s):
    """"""
    if NO_IMAGES:
        return

    line0 = bezier.Curve.from_nodes(stack1d(start0, end0))
    line1 = bezier.Curve.from_nodes(stack1d(start1, end1))
    ax = line0.plot(2)
    line1.plot(256, ax=ax)
    (x_val,), (y_val,) = line0.evaluate(s)
    ax.plot([x_val], [y_val], color="black", marker="o")
    ax.axis("scaled")
    save_image(ax.figure, "segment_intersection1.png")
330752
function intersectTriangle (out, pt, dir, tri) {
  var EPSILON = 0.000001
  var edge1 = [0, 0, 0]
  var edge2 = [0, 0, 0]
  var tvec = [0, 0, 0]
  var pvec = [0, 0, 0]
  var qvec = [0, 0, 0]

  vec3.subtract(edge1, tri[1], tri[0])
  vec3.subtract(edge2, tri[2], tri[0])

  vec3.cross(pvec, dir, edge2)
  var det = vec3.dot(edge1, pvec)

  if (det < EPSILON) return null
  vec3.subtract(tvec, pt, tri[0])
  var u = vec3.dot(tvec, pvec)
  if (u < 0 || u > det) return null
  vec3.cross(qvec, tvec, edge1)
  var v = vec3.dot(dir, qvec)
  if (v < 0 || u + v > det) return null

  var t = vec3.dot(edge2, qvec) / det
  out[0] = pt[0] + t * dir[0]
  out[1] = pt[1] + t * dir[1]
  out[2] = pt[2] + t * dir[2]
  return t
}
1330928
void updateCornerLeft() {

        if (m_corner != null) {
            int popupLeft = popup.getPopupLeft();
            int dif = (getAbsoluteLeft() - popupLeft) + OFFSET;
            m_corner.getStyle().setLeft(dif, Unit.PX);
        }
    }