Adapted from: http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/1968345#1968345
490139
function getIntersection(segment1, segment2) {
  var p0X = segment1[0][0];
  var p0Y = segment1[0][1];
  var p1X = segment1[1][0];
  var p1Y = segment1[1][1];
  var p2X = segment2[0][0];
  var p2Y = segment2[0][1];
  var p3X = segment2[1][0];
  var p3Y = segment2[1][1];

  var s1X, s1Y, s2X, s2Y;
  s1X = p1X - p0X;
  s1Y = p1Y - p0Y;
  s2X = p3X - p2X;
  s2Y = p3Y - p2Y;
  var s, t;
  s = (-s1Y * (p0X - p2X) + s1X * (p0Y - p2Y)) / (-s2X * s1Y + s1X * s2Y);
  t = (s2X * (p0Y - p2Y) - s2Y * (p0X - p2X)) / (-s2X * s1Y + s1X * s2Y);
  if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
    return {
      x: p0X + (t * s1X),
      y: p0Y + (t * s1Y)
    };
  }
  return null; // No collision
}
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;
}
1291833
function (intersections, iMap) {
                for (var i = 0; i < intersections.length - 1; i += 2) {
                    var i0 = intersections[i];
                    var i1 = intersections[i + 1];

                    var iEnd0 = iMap.get(i0.indexEnd);
                    var iStart0 = iMap.get(i0.indexStart);
                    var iEnd1 = iMap.get(i1.indexEnd);
                    var iStart1 = iMap.get(i1.indexStart);

                    iEnd0.linkTo = i1.indexStart;
                    iStart0.linkTo = i1.indexEnd;
                    iEnd1.linkTo = i0.indexStart;
                    iStart1.linkTo = i0.indexEnd;
                }
            }
1244216
private static Point getLinesIntersection(Line2D a,
                                              Line2D b) {
        double d = (a.getX1() - a.getX2()) * (b.getY2() - b.getY1()) - (a.getY1() - a.getY2()) * (b.getX2() - b.getX1());
        double da = (a.getX1() - b.getX1()) * (b.getY2() - b.getY1()) - (a.getY1() - b.getY1()) * (b.getX2() - b.getX1());
        double ta = da / d;
        Point p = new Point();
        p.setLocation(a.getX1() + ta * (a.getX2() - a.getX1()),
                      a.getY1() + ta * (a.getY2() - a.getY1()));
        return p;
    }
1000524
def find_last_intersection(edges, i, e)
	    intersection, intersection_at = nil, nil
	    for j in i..(edges.count-1)
		e2 = edges[j][:edge]
		next if !e2 || e.connected?(e2)
		_intersection = e.intersection(e2)
		intersection, intersection_at = _intersection, j if _intersection
	    end
	    [intersection, intersection_at]
	end
506646
def overlap?(other_segment)
      raise TypeError, 'Argument must be a JSS::NetworkSegment' unless \
        other_segment.is_a? JSS::NetworkSegment
      other_range = other_segment.range
      range.include?(other_range.begin) || range.include?(other_range.end)
    end
258312
def doesIntersect(self, other):
        '''
        

        '''
        otherType = type(other)

        if issubclass(otherType, Triangle):
            for s in self.segments.values():
                for q in other.segments.values():
                    if s.doesIntersect(q):
                        return True
            return False

        if issubclass(otherType, Line):
            for s in self.segments.values():
                if s.doesIntersect(other):
                    return True
            return False

        msg = "expecting Line or Triangle subclasses, got '{}'"

        raise TypeError(msg.format(otherType))
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.")
1155947
def is_intersect(line_a, line_b):
    
    # Find the four orientations needed for general and special cases
    orientation_1 = orientation(line_a.endpoint_a, line_a.endpoint_b,
                                line_b.endpoint_a)
    orientation_2 = orientation(line_a.endpoint_a, line_a.endpoint_b,
                                line_b.endpoint_b)
    orientation_3 = orientation(line_b.endpoint_a, line_b.endpoint_b,
                                line_a.endpoint_a)
    orientation_4 = orientation(line_b.endpoint_a, line_b.endpoint_b,
                                line_a.endpoint_b)

    # General case
    if (orientation_1 != orientation_2 and orientation_3 != orientation_4):
        return True

    # Special cases
    if (orientation_1 == 0 and on_segment(line_a.endpoint_a, line_b.endpoint_a,
                                          line_a.endpoint_b)):
        return True
    if (orientation_2 == 0 and on_segment(line_a.endpoint_a, line_b.endpoint_b,
                                          line_a.endpoint_b)):
        return True
    if (orientation_3 == 0 and on_segment(line_b.endpoint_a, line_a.endpoint_a,
                                          line_b.endpoint_b)):
        return True
    if (orientation_4 == 0 and on_segment(line_b.endpoint_a, line_a.endpoint_b,
                                          line_b.endpoint_b)):
        return True

    return False
1089903
public boolean intersect(Line other, boolean limit, Vector2f result) {
		float dx1 = end.getX() - start.getX();
		float dx2 = other.end.getX() - other.start.getX();
		float dy1 = end.getY() - start.getY();
		float dy2 = other.end.getY() - other.start.getY();
		float denom = (dy2 * dx1) - (dx2 * dy1);

		if (denom == 0) {
			return false;
		}

		float ua = (dx2 * (start.getY() - other.start.getY()))
				- (dy2 * (start.getX() - other.start.getX()));
		ua /= denom;
		float ub = (dx1 * (start.getY() - other.start.getY()))
				- (dy1 * (start.getX() - other.start.getX()));
		ub /= denom;

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

		float u = ua;

		float ix = start.getX() + (u * (end.getX() - start.getX()));
		float iy = start.getY() + (u * (end.getY() - start.getY()));

		result.set(ix, iy);
		return true;
	}
207574
def lines_touch_2D(ab, cd):
    '''
    
    '''
    return lines_colinear(ab, cd) | np.isfinite(line_intersection_2D(ab, cd)[0])
526104
def intersects_segment(self, seg):
		
		return any(value.intersects_segment(seg) for value in self.itervalues())
1289874
private static boolean polylineOverlapsEnvelope_(Polyline polyline_a,
			Envelope envelope_b, double tolerance,
			ProgressTracker progress_tracker) {
		Envelope2D env_a = new Envelope2D(), env_b = new Envelope2D();
		polyline_a.queryEnvelope2D(env_a);
		envelope_b.queryEnvelope2D(env_b);

		if (envelopeInfContainsEnvelope_(env_a, env_b, tolerance)
				|| envelopeInfContainsEnvelope_(env_b, env_a, tolerance))
			return false;

		if (envelopeInfContainsEnvelope_(env_b, env_a, tolerance))
			return false;

		if (env_b.getHeight() > tolerance && env_b.getWidth() > tolerance)
			return false; // lines cannot overlap areas

		if (env_b.getHeight() <= tolerance && env_b.getWidth() <= tolerance)
			return false; // lines cannot overlap points

		// Treat as polyline
		Polyline polyline_b = new Polyline();
		Point p = new Point();
		envelope_b.queryCornerByVal(0, p);
		polyline_b.startPath(p);
		envelope_b.queryCornerByVal(2, p);
		polyline_b.lineTo(p);
		return linearPathOverlapsLinearPath_(polyline_a, polyline_b, tolerance);
	}
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;
      }
893607
def guess_segments_lines(segments, lines, nearline_tolerance=5.0):
    
    ys = segments[:, 1]
    closeness = numpy.abs(numpy.subtract.outer(ys, lines))  # each row a y, each collumn a distance to each line
    line_of_y = numpy.argmin(closeness, axis=1)
    distance = numpy.min(closeness, axis=1)
    bad = distance > numpy.mean(distance) + nearline_tolerance * numpy.std(distance)
    line_of_y[bad] = -1
    return line_of_y
214941
public static int find(
		MemorySegment[] segments1, int offset1, int numBytes1,
		MemorySegment[] segments2, int offset2, int numBytes2) {
		if (numBytes2 == 0) { // quick way 1.
			return offset1;
		}
		if (inFirstSegment(segments1, offset1, numBytes1) &&
			inFirstSegment(segments2, offset2, numBytes2)) {
			byte first = segments2[0].get(offset2);
			int end = numBytes1 - numBytes2 + offset1;
			for (int i = offset1; i <= end; i++) {
				// quick way 2: equal first byte.
				if (segments1[0].get(i) == first &&
					segments1[0].equalTo(segments2[0], i, offset2, numBytes2)) {
					return i;
				}
			}
			return -1;
		} else {
			return findInMultiSegments(segments1, offset1, numBytes1, segments2, offset2, numBytes2);
		}
	}
750837
private void calculateIntersectPoints() {
        intersectPoints.clear();

        /** order intersect points clockwise **/
        //left edge
        if (center.x - menuBounds.left < expandedRadius) {
            int dy = (int) Math.sqrt(Math.pow(expandedRadius, 2) - Math.pow(center.x - menuBounds.left, 2));
            if (center.y - dy > menuBounds.top) {
                intersectPoints.add(new Point(menuBounds.left, center.y - dy));
            }

            if (center.y + dy < menuBounds.bottom) {
                intersectPoints.add(new Point(menuBounds.left, center.y + dy));
            }

        }
        //top edge
        if (center.y - menuBounds.top < expandedRadius) {
            int dx = (int) Math.sqrt(Math.pow(expandedRadius, 2) - Math.pow(center.y - menuBounds.top, 2));
            if (center.x + dx < menuBounds.right) {
                intersectPoints.add(new Point(center.x + dx, menuBounds.top));
            }
            if (center.x - dx > menuBounds.left) {
                intersectPoints.add(new Point(center.x - dx, menuBounds.top));
            }
        }

        //right edge
        if (menuBounds.right - center.x < expandedRadius) {
            int dy = (int) Math.sqrt(Math.pow(expandedRadius, 2) - Math.pow(menuBounds.right - center.x, 2));

            if (center.y - dy > menuBounds.top) {
                intersectPoints.add(new Point(menuBounds.right, center.y - dy));
            }
            if (center.y + dy < menuBounds.bottom) {
                intersectPoints.add(new Point(menuBounds.right, center.y + dy));
            }

        }
        //bottom edge
        if (menuBounds.bottom - center.y < expandedRadius) {
            int dx = (int) Math.sqrt(Math.pow(expandedRadius, 2) - Math.pow(menuBounds.bottom - center.y, 2));
            if (center.x + dx < menuBounds.right) {
                intersectPoints.add(new Point(center.x + dx, menuBounds.bottom));
            }
            if (center.x - dx > menuBounds.left) {
                intersectPoints.add(new Point(center.x - dx, menuBounds.bottom));
            }
        }


        //find the maximum arc in menuBounds
        int size = intersectPoints.size();
        if (size == 0) {
            fromAngle = 0;
            toAngle = 360;
            return;
        }
        int indexA = size - 1;
        double maxAngle = arcAngle(center, intersectPoints.get(0), intersectPoints.get(indexA), menuBounds, expandedRadius);
        for (int i = 0; i < size - 1; i++) {
            Point a = intersectPoints.get(i);
            Point b = intersectPoints.get(i + 1);
            double angle = arcAngle(center, a, b, menuBounds, expandedRadius);
            Point midnormalPoint = findMidnormalPoint(center, a, b, menuBounds, expandedRadius);

            //if the arc(a->midnormalPoint->b) is in menuBounds and the angle is bigger, select it
            int pointerIndex = i;
            int endIndex = indexA + 1;
            if (!isClockwise(center, a, midnormalPoint)) {
                int tmpIndex = pointerIndex;
                pointerIndex = endIndex;
                endIndex = tmpIndex;
            }
            if (pointerIndex == intersectPoints.size() - 1) {
                pointerIndex = 0;
            } else {
                pointerIndex++;
            }

            if (pointerIndex == endIndex && angle > maxAngle) {
                indexA = i;
                maxAngle = angle;
            }
        }

        Point a = intersectPoints.get(indexA);
        Point b = intersectPoints.get(indexA + 1 >= size ? 0 : indexA + 1);
        Point midnormalPoint = findMidnormalPoint(center, a, b, menuBounds, expandedRadius);

        Point x = new Point(menuBounds.right, center.y);
        if (!isClockwise(center, a, midnormalPoint)) {
            Point tmp = a;
            a = b;
            b = tmp;
        }

        fromAngle = pointAngleOnCircle(center, a, x);
        toAngle = pointAngleOnCircle(center, b, x);
        toAngle = toAngle <= fromAngle ? 360 + toAngle : toAngle;
    }