line intersection helper function: does line segment (p1,p2) intersect segment (p3,p4) ?
190125
function(p1,p2,p3,p4) {
      var denom = (p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y);
      if(denom===0.0) { return false; } // parallel lines
      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.0&&ua<1.0&&ub>0.0&&ub<1.0) {
        var up = new Vec(p1.x+ua*(p2.x-p1.x), p1.y+ua*(p2.y-p1.y));
        return {ua:ua, ub:ub, up:up}; // up is intersection point
      }
      return false;
    }
7658
function lineIntersects(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {
  // if the lines intersect, the result contains the x and y of the intersection (treating the lines as infinite) and booleans for whether line segment 1 or line segment 2 contain the point
  var denominator, a, b, numerator1, numerator2,
    result = {
      x: null,
      y: null,
      onLine1: false,
      onLine2: false
    };
  denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
  if (denominator === 0) {
    if (result.x !== null && result.y !== null) {
      return result;
    } else {
      return false;
    }
  }
  a = line1StartY - line2StartY;
  b = line1StartX - line2StartX;
  numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
  numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
  a = numerator1 / denominator;
  b = numerator2 / denominator;

  // if we cast these lines infinitely in both directions, they intersect here:
  result.x = line1StartX + (a * (line1EndX - line1StartX));
  result.y = line1StartY + (a * (line1EndY - line1StartY));

  // if line1 is a segment and line2 is infinite, they intersect if:
  if (a > 0 && a < 1) {
    result.onLine1 = true;
  }
  // if line2 is a segment and line1 is infinite, they intersect if:
  if (b > 0 && b < 1) {
    result.onLine2 = true;
  }
  // if line1 and line2 are segments, they intersect if both of the above are true
  if (result.onLine1 && result.onLine2) {
    return [result.x, result.y];
  } else {
    return false;
  }
}
219393
private Point intersection(int x1, int y1, int x2, int y2, DesktopWindowRect rect) {
    Point
        bottom =
        intersection(x1, y1, x2, y2, rect.getX(), rect.getY(), rect.getX() + rect.getHeight(),
                     rect.getY());
    if (bottom != null) {
      return bottom;
    }

    Point
        right =
        intersection(x1, y1, x2, y2, rect.getX() + rect.getWidth(), rect.getY(),
                     rect.getX() + rect.getWidth(), rect.getY() + rect.getHeight());
    if (right != null) {
      return right;
    }

    Point
        top =
        intersection(x1, y1, x2, y2, rect.getX(), rect.getY() + rect.getHeight(),
                     rect.getX() + rect.getWidth(), rect.getY() + rect.getHeight());
    if (top != null) {
      return top;
    }

    Point
        left =
        intersection(x1, y1, x2, y2, rect.getX(), rect.getY(), rect.getX(),
                     rect.getY() + rect.getHeight());
    if (left != null) {
      return left;
    }

    return null;
  }
319710
@Pure   
	private static boolean intersectEdgeEdge(
			int i0, int i1, int con, double Ax, double Ay, double[] v, double[] u1, double[] u2) {
		// [v,b] is the segment that contains the point v
		// [c,d] is the segment [u1,u2]

		// A is the vector (v,b)
		// B is the vector (d,c)
		// C is the vector (c,v)

		double Bx = u1[i0] - u2[i0];
		double By = u1[i1] - u2[i1];
		double Cx = v[i0]  - u1[i0];
		double Cy = v[i1]  - u1[i1];

		// 

		double f = Ay * Bx - Ax * By;
		double d = By * Cx - Bx * Cy; // Line equation: V+d*A

		boolean up = false;
		boolean down = false;

		if (f>0) {
			switch(con) {
			case 1: // First point must be ignored
				down = (d>0);
				up = (d<=f);
				break;
			case 2: // Second point must be ignored
				down = (d>=0);
				up = (d<f);
				break;
			case 3: // First and Second points must be ignored
				down = (d>0);
				up = (d<f);
				break;
			default:
				down = (d>=0);
				up = (d<=f);
			}
		}
		else if (f<0) {
			switch(con) {
			case 1: // First point must be ignored
				down = (d>=f);
				up = (d<0);
				break;
			case 2: // Second point must be ignored
				down = (d>f);
				up = (d<=0);
				break;
			case 3: // First and Second points must be ignored
				down = (d>f);
				up = (d<0);
				break;
			default:
				down = (d>=f);
				up = (d<=0);
			}
		}

		if (up&&down) {
			double e = Ax * Cy - Ay * Cx;
			if (f>=0) return ((e>=0)&&(e<=f));
			return ((e>=f)&&(e<=0));
		}

		return false;
	}
1335180
public static int intersectPath (PathIterator p, float x, float y, float w, float h) {
        int cross = 0;
        int count;
        float mx, my, cx, cy;
        mx = my = cx = cy = 0f;
        float[] coords = new float[6];

        float rx1 = x;
        float ry1 = y;
        float rx2 = x + w;
        float ry2 = y + h;

        while (!p.isDone()) {
            count = 0;
            switch (p.currentSegment(coords)) {
            case PathIterator.SEG_MOVETO:
                if (cx != mx || cy != my) {
                    count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
                }
                mx = cx = coords[0];
                my = cy = coords[1];
                break;
            case PathIterator.SEG_LINETO:
                count = intersectLine(cx, cy, cx = coords[0], cy = coords[1], rx1, ry1, rx2, ry2);
                break;
            case PathIterator.SEG_QUADTO:
                count = intersectQuad(cx, cy, coords[0], coords[1], cx = coords[2], cy = coords[3],
                        rx1, ry1, rx2, ry2);
                break;
            case PathIterator.SEG_CUBICTO:
                count = intersectCubic(cx, cy, coords[0], coords[1], coords[2], coords[3],
                        cx = coords[4], cy = coords[5], rx1, ry1, rx2, ry2);
                break;
            case PathIterator.SEG_CLOSE:
                if (cy != my || cx != mx) {
                    count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
                }
                cx = mx;
                cy = my;
                break;
            }
            if (count == CROSSING) {
                return CROSSING;
            }
            cross += count;
            p.next();
        }
        if (cy != my) {
            count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2);
            if (count == CROSSING) {
                return CROSSING;
            }
            cross += count;
        }
        return cross;
    }
1355197
function getIntersection(x0, y0, r0, x1, y1, r1) {
	var dx = x1 - x0,
		dy = y1 - y0,
		d = sqrt(pow(dx, 2) + pow(dy, 2)),
		a = (pow(d, 2) + pow(r0, 2) - pow(r1, 2)) / (2 * d),
		x2 = x0 + (dx * a / d),
		y2 = y0 + (dy * a / d),
		h = sqrt(pow(r0, 2) - pow(a, 2)),
		rx = -dy * (h / d),
		ry = dx * (h / d),
		xi = x2 + rx,
		yi = y2 + ry;

	// Check if circles do not intersect or overlap completely
	if (d > (r0 + r1) || d < Math.abs(r0 - r1)) {
		return false;
	}
	return [xi, yi];
}
118936
function(p) {

        var start = this.start;
        var end = this.end;

        if (start.cross(p, end) !== 0) return false;
        // else: cross product of 0 indicates that this line and the vector to `p` are collinear

        var length = this.length();
        if ((new g.Line(start, p)).length() > length) return false;
        if ((new g.Line(p, end)).length() > length) return false;
        // else: `p` lies between start and end of the line

        return true;
    }
80774
def line_of_sight?(x1, y1, x2, y2)
      !line_of_sight_blocked_at(x1, y1, x2, y2)
    end
210181
public static boolean lineIntersectsRect (double x1, double y1, double x2, double y2,
                                              double rx, double ry, double rw, double rh) {
        double rr = rx + rw, rb = ry + rh;
        return (rx <= x1 && x1 <= rr && ry <= y1 && y1 <= rb)
            || (rx <= x2 && x2 <= rr && ry <= y2 && y2 <= rb)
            || linesIntersect(rx, ry, rr, rb, x1, y1, x2, y2)
            || linesIntersect(rr, ry, rx, rb, x1, y1, x2, y2);
    }
1369841
public static int intersectQuad (float x1, float y1, float cx, float cy, float x2,
                                     float y2, float rx1, float ry1, float rx2, float ry2) {
        // LEFT/RIGHT/UP ------------------------------------------------------
        if ((rx2 < x1 && rx2 < cx && rx2 < x2) || (rx1 > x1 && rx1 > cx && rx1 > x2) ||
            (ry1 > y1 && ry1 > cy && ry1 > y2)) {
            return 0;
        }

        // DOWN ---------------------------------------------------------------
        if (ry2 < y1 && ry2 < cy && ry2 < y2 && rx1 != x1 && rx1 != x2) {
            if (x1 < x2) {
                return x1 < rx1 && rx1 < x2 ? 1 : 0;
            }
            return x2 < rx1 && rx1 < x1 ? -1 : 0;
        }

        // INSIDE -------------------------------------------------------------
        QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2);
        float px1 = rx1 - x1;
        float py1 = ry1 - y1;
        float px2 = rx2 - x1;
        float py2 = ry2 - y1;

        float[] res1 = new float[3];
        float[] res2 = new float[3];
        int rc1 = c.solvePoint(res1, px1);
        int rc2 = c.solvePoint(res2, px2);

        // INSIDE-LEFT/RIGHT
        if (rc1 == 0 && rc2 == 0) {
            return 0;
        }

        // Build bound --------------------------------------------------------
        float minX = px1 - DELTA;
        float maxX = px2 + DELTA;
        float[] bound = new float[28];
        int bc = 0;
        // Add roots
        bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0);
        bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1);
        // Add extremal points
        rc2 = c.solveExtreme(res2);
        bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2);
        // Add start and end
        if (rx1 < x1 && x1 < rx2) {
            bound[bc++] = 0f;
            bound[bc++] = 0f;
            bound[bc++] = 0f;
            bound[bc++] = 4;
        }
        if (rx1 < x2 && x2 < rx2) {
            bound[bc++] = 1f;
            bound[bc++] = c.ax;
            bound[bc++] = c.ay;
            bound[bc++] = 5;
        }
        // End build bound ----------------------------------------------------

        int cross = crossBound(bound, bc, py1, py2);
        if (cross != UNKNOWN) {
            return cross;
        }
        return c.cross(res1, rc1, py1, py2);
    }
168663
def has_intersection(self, other):
        
        return bool(lib.SDL_HasIntersection(self._ptr, other._ptr))
692749
function boolIntersects(coords1,coords2) {
    
  
    // if (coords1.length !== 2)throw new Error("<intersects> line1 must only contain 2 coordinates");
    // if (coords2.length !== 2)throw new Error("<intersects> line2 must only contain 2 coordinates");
    const x1 = coords1[0][0];
    const y1 = coords1[0][1];
    const x2 = coords1[1][0];
    const y2 = coords1[1][1];
    const x3 = coords2[0][0];
    const y3 = coords2[0][1];
    const x4 = coords2[1][0];
    const y4 = coords2[1][1];
    const denom = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));
    const numeA = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
    const numeB = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3));

    if (denom === 0) return null;
    
    const uA = numeA / denom;
    const uB = numeB / denom;

    if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1)return true;
    return null;
}
101612
def line_intersection(self, point1, point2, tolerance=1e-8):
        
        b1 = self.bary_coords(point1)
        b2 = self.bary_coords(point2)
        l = b1 - b2
        # don't use barycentric dimension where line is parallel to face
        valid = np.abs(l) > 1e-10
        # array of all the barycentric coordinates on the line where
        # one of the values is 0
        possible = b1 - (b1[valid] / l[valid])[:, None] * l
        barys = []
        for p in possible:
            # it's only an intersection if its in the simplex
            if (p >= -tolerance).all():
                found = False
                # don't return duplicate points
                for b in barys:
                    if np.all(np.abs(b - p) < tolerance):
                        found = True
                        break
                if not found:
                    barys.append(p)
        assert len(barys) < 3
        return [self.point_from_bary_coords(b) for b in barys]
1279991
function intersectsPolygon (data, start, a, b) {
  var node = start
  do {
    var p1 = node.i,
      p2 = node.next.i

    if (p1 !== a && p2 !== a && p1 !== b && p2 !== b && intersects(data, p1, p2, a, b)) {
      return true
    }

    node = node.next
  } while (node !== start)

  return false
}
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]));
            }
        }
    }
963842
function (/*Point*/ p, /*Point*/ p1, /*Point*/ p2) {
		return (p2.y - p.y) * (p1.x - p.x) > (p1.y - p.y) * (p2.x - p.x);
	}
1154546
def intersect(self, other_seg, tol=1e-12):
        """"""
        if isinstance(other_seg, Line):
            return bezier_by_line_intersections(self, other_seg)
        elif (isinstance(other_seg, QuadraticBezier) or
              isinstance(other_seg, CubicBezier)):
            assert self != other_seg
            longer_length = max(self.length(), other_seg.length())
            return bezier_intersections(self, other_seg,
                                        longer_length=longer_length,
                                        tol=tol, tol_deC=tol)
        elif isinstance(other_seg, Arc):
            t2t1s = other_seg.intersect(self)
            return [(t1, t2) for t2, t1 in t2t1s]
        elif isinstance(other_seg, Path):
            raise TypeError(
                "other_seg must be a path segment, not a Path object, use "
                "Path.intersect().")
        else:
            raise TypeError("other_seg must be a path segment.")