Returns how many times rectangle stripe cross cubic curve or the are
intersect
434116
public static int intersectCubic (float x1, float y1, float cx1, float cy1,
                                      float cx2, float cy2, float x2, float y2,
                                      float rx1, float ry1, float rx2, float ry2) {
        // LEFT/RIGHT/UP
        if ((rx2 < x1 && rx2 < cx1 && rx2 < cx2 && rx2 < x2)
                || (rx1 > x1 && rx1 > cx1 && rx1 > cx2 && rx1 > x2)
                || (ry1 > y1 && ry1 > cy1 && ry1 > cy2 && ry1 > y2)) {
            return 0;
        }

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

        // INSIDE
        CubicCurveH c = new CubicCurveH(x1, y1, cx1, cy1, cx2, cy2, 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);

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

        float minX = px1 - DELTA;
        float maxX = px2 + DELTA;

        // Build bound --------------------------------------------------------
        float[] bound = new float[40];
        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.solveExtremeX(res2);
        bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2);
        rc2 = c.solveExtremeY(res2);
        bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 4);
        // Add start and end
        if (rx1 < x1 && x1 < rx2) {
            bound[bc++] = 0f;
            bound[bc++] = 0f;
            bound[bc++] = 0f;
            bound[bc++] = 6;
        }
        if (rx1 < x2 && x2 < rx2) {
            bound[bc++] = 1f;
            bound[bc++] = c.ax;
            bound[bc++] = c.ay;
            bound[bc++] = 7;
        }
        // End build bound ----------------------------------------------------

        int cross = crossBound(bound, bc, py1, py2);
        if (cross != UNKNOWN) {
            return cross;
        }
        return c.cross(res1, rc1, py1, py2);
    }
659101
private static boolean checkVerticesForIntersection_(
			MultiVertexGeometryImpl geom, RasterizedGeometry2D rgeom) {
		// Do a quick raster test for each point. If any point is inside, then
		// there is an intersection.
		int pointCount = geom.getPointCount();
		Point2D pt = new Point2D();
		for (int ipoint = 0; ipoint < pointCount; ipoint++) {
			geom.getXY(ipoint, pt);
			RasterizedGeometry2D.HitType hit = rgeom.queryPointInGeometry(pt.x,
					pt.y);
			if (hit == RasterizedGeometry2D.HitType.Inside) {
				return true;
			}
		}

		return false;
	}
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
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;
      }
1087258
public boolean intersects(Shape shape) {
        if(shape instanceof Rectangle) {
            Rectangle other = (Rectangle)shape;
    		if ((x > (other.x + other.width)) || ((x + width) < other.x)) {
    			return false;
    		}
    		if ((y > (other.y + other.height)) || ((y + height) < other.y)) {
    			return false;
    		}
            return true;
        }
        else if(shape instanceof Circle) {
            return intersects((Circle)shape);
        }
        else {
            return super.intersects(shape);
        }
	}
982668
function(w, degree, t, depth) {
		var left = [], right = [],
			left_count, right_count,
			left_t = [], right_t = [];

		switch (_getCrossingCount(w, degree)) {
			case 0 : {
				return 0;
			}
			case 1 : {
				if (depth >= maxRecursion) {
					t[0] = (w[0].x + w[degree].x) / 2.0;
					return 1;
				}
				if (_isFlatEnough(w, degree)) {
					t[0] = _computeXIntercept(w, degree);
					return 1;
				}
				break;
			}
		}
		_bezier(w, degree, 0.5, left, right);
		left_count  = _findRoots(left,  degree, left_t, depth+1);
		right_count = _findRoots(right, degree, right_t, depth+1);
		for (var i = 0; i < left_count; i++) t[i] = left_t[i];
		for (var i = 0; i < right_count; i++) t[i+left_count] = right_t[i];
		return (left_count+right_count);
	}
233607
function getIntersectionRect (rect1, rect2) {
  const intersectRect = {
    topLeft: {},
    bottomRight: {}
  };

  if (!doesIntersect(rect1, rect2)) {
    return;
  }

  const rect1Points = rectToPoints(rect1);
  const rect2Points = rectToPoints(rect2);

  if (rect1.width >= 0) {
    if (rect2.width >= 0) {
      intersectRect.topLeft.x = Math.max(rect1Points.topLeft.x, rect2Points.topLeft.x);
      intersectRect.bottomRight.x = Math.min(rect1Points.bottomRight.x, rect2Points.bottomRight.x);
    } else {
      intersectRect.topLeft.x = Math.max(rect1Points.topLeft.x, rect2Points.bottomRight.x);
      intersectRect.bottomRight.x = Math.min(rect1Points.bottomRight.x, rect2Points.topLeft.x);
    }
  } else if (rect2.width >= 0) {
    intersectRect.topLeft.x = Math.min(rect1Points.topLeft.x, rect2Points.bottomRight.x);
    intersectRect.bottomRight.x = Math.max(rect1Points.bottomRight.x, rect2Points.topLeft.x);
  } else {
    intersectRect.topLeft.x = Math.min(rect1Points.topLeft.x, rect2Points.topLeft.x);
    intersectRect.bottomRight.x = Math.max(rect1Points.bottomRight.x, rect2Points.bottomRight.x);
  }

  if (rect1.height >= 0) {
    if (rect2.height >= 0) {
      intersectRect.topLeft.y = Math.max(rect1Points.topLeft.y, rect2Points.topLeft.y);
      intersectRect.bottomRight.y = Math.min(rect1Points.bottomRight.y, rect2Points.bottomRight.y);
    } else {
      intersectRect.topLeft.y = Math.max(rect1Points.topLeft.y, rect2Points.bottomRight.y);
      intersectRect.bottomRight.y = Math.min(rect1Points.bottomRight.y, rect2Points.topLeft.y);
    }
  } else if (rect2.height >= 0) {
    intersectRect.topLeft.y = Math.min(rect1Points.topLeft.y, rect2Points.bottomRight.y);
    intersectRect.bottomRight.y = Math.max(rect1Points.bottomRight.y, rect2Points.topLeft.y);
  } else {
    intersectRect.topLeft.y = Math.min(rect1Points.topLeft.y, rect2Points.topLeft.y);
    intersectRect.bottomRight.y = Math.max(rect1Points.bottomRight.y, rect2Points.bottomRight.y);
  }

  // Returns top-left and bottom-right points of intersected rectangle
  return intersectRect;

}
984569
function collides(element_one, element_two) {

	var result,
	    rect1,
	    rect2;

	if (element_one.nodeName) {
		rect1 = element_one.getBoundingClientRect();
	} else {
		rect1 = element_one;
	}

	if (element_two.nodeName) {
		rect2 = element_two.getBoundingClientRect();
	} else {
		rect2 = element_two;
	}

	result = !(
		rect1.top    > rect2.bottom ||
		rect1.right  < rect2.left ||
		rect1.bottom < rect2.top ||
		rect1.left   > rect2.right
	);

	return result;
}
518162
public boolean intersects(Rectangle2D r) {
		if(np==0)return false;
		Line2D line = new Line2D.Double(x[0],y[0],x[0],y[0]);
		for (int i = 1; i < np; i++) {
			line.setLine(x[i-1], y[i-1], x[i], y[i]);
			if(line.intersects(r))return true;
		}
		return false;
	}
279999
function ifIsectAddToOutput(ring0, edge0, ring1, edge1) {
    var start0 = coord[ring0][edge0];
    var end0 = coord[ring0][edge0+1];
    var start1 = coord[ring1][edge1];
    var end1 = coord[ring1][edge1+1];

    var isect = intersect(start0, end0, start1, end1);

    if (isect == null) return; // discard parallels and coincidence
    frac0, frac1;
    if (end0[0] != start0[0]) {
      var frac0 = (isect[0]-start0[0])/(end0[0]-start0[0]);
    } else {
      var frac0 = (isect[1]-start0[1])/(end0[1]-start0[1]);
    };
    if (end1[0] != start1[0]) {
      var frac1 = (isect[0]-start1[0])/(end1[0]-start1[0]);
    } else {
      var frac1 = (isect[1]-start1[1])/(end1[1]-start1[1]);
    };

    // There are roughly three cases we need to deal with.
    // 1. If at least one of the fracs lies outside [0,1], there is no intersection.
    if (isOutside(frac0) || isOutside(frac1)) {
      return; // require segment intersection
    }

    // 2. If both are either exactly 0 or exactly 1, this is not an intersection but just
    // two edge segments sharing a common vertex.
    if (isBoundaryCase(frac0) && isBoundaryCase(frac1)){
      if(! options.reportVertexOnVertex) return;
    }

    // 3. If only one of the fractions is exactly 0 or 1, this is
    // a vertex-on-edge situation.
    if (isBoundaryCase(frac0) || isBoundaryCase(frac1)){
      if(! options.reportVertexOnEdge) return;
    }

    var key = isect;
    var unique = !seen[key];
    if (unique) {
      seen[key] = true;
    }

    if (filterFn) {
      output.push(filterFn(isect, ring0, edge0, start0, end0, frac0, ring1, edge1, start1, end1, frac1, unique));
    } else {
      output.push(isect);
    }
  }
285865
def get_rectangles(vertical_lines, horizontal_lines):
    
    rectangles = []
    i = 0
    j = 0
    while i < len(horizontal_lines) and j < len(vertical_lines):
        if int(horizontal_lines[i][0]) == vertical_lines[j][0]:
            if int(horizontal_lines[i][1]) == int(vertical_lines[j][1]):
                h = horizontal_lines[i]
                v = vertical_lines[j]
                rectangles += [(v[0], h[1], v[2], h[3])]
                i += 1
                j += 1
            elif int(horizontal_lines[i][1]) < int(vertical_lines[j][1]):
                i += 1
            else:
                j += 1
        elif int(horizontal_lines[i][0]) < int(vertical_lines[j][0]):
            i += 1
        else:
            j += 1
    rectangles = [
        r
        for r in rectangles
        if ((r[2] - r[0]) > TOLERANCE and (r[3] - r[1]) > TOLERANCE)
    ]
    return rectangles
1122511
function getIntersectionPoints(circles) {
        var ret = [];
        for (var i = 0; i < circles.length; ++i) {
            for (var j = i + 1; j < circles.length; ++j) {
                var intersect = circleCircleIntersection(circles[i],
                                                              circles[j]);
                for (var k = 0; k < intersect.length; ++k) {
                    var p = intersect[k];
                    p.parentIndex = [i,j];
                    ret.push(p);
                }
            }
        }
        return ret;
    }
54473
function calculateDiff() {
    // we need to take 2 pointers
    // and travel progressively between them ...
    var newFirst = [
      [].concat(array1Extract[0]),
      [].concat(array1Extract[1])
    ];
    var newSecond = [
      [].concat(array2Extract[0]),
      [].concat(array2Extract[1])
    ];
    var array1Length = array1Extract[0] ? array1Extract[0].length : 0;
    var array2Length = array2Extract[0] ? array2Extract[0].length : 0;

    var pos1 = 0;
    var pos2 = 0;
    var previous2 = 0;
    while (pos1 < array1Length) {
      var diff = newFirst[0][pos1] - array2Extract[0][pos2];
      if (Math.abs(diff) < widthBottom) { // there is some overlap
        var overlap;
        if (options.trapezoid) {
          overlap = getOverlapTrapezoid(newFirst[0][pos1], newFirst[1][pos1], newSecond[0][pos2], newSecond[1][pos2], widthTop, widthBottom);
        } else {
          overlap = getOverlap(newFirst[0][pos1], newFirst[1][pos1], newSecond[0][pos2], newSecond[1][pos2], widthTop, widthBottom);
        }
        newFirst[1][pos1] -= overlap;
        newSecond[1][pos2] -= overlap;
        if (pos2 < (array2Length - 1)) {
          pos2++;
        } else {
          pos1++;
          pos2 = previous2;
        }
      } else {
        if (diff > 0 && pos2 < (array2Length - 1)) {
          pos2++;
          previous2 = pos2;
        } else {
          pos1++;
          pos2 = previous2;
        }
      }
    }
    return newSecond;
  }
1092239
function rectIntersect(r1, r2) {
    var right1 = r1.x + r1.width;
    var bottom1 = r1.y + r1.height;
    var right2 = r2.x + r2.width;
    var bottom2 = r2.y + r2.height;

    var x = Math.max(r1.x, r2.x);
    var y = Math.max(r1.y, r2.y);
    var w = Math.max(Math.min(right1, right2) - x, 0);
    var h = Math.max(Math.min(bottom1, bottom2) - y, 0);
    return {x: x, y: y, width: w, height: h};
}
1363806
function rectshift(a, b) {
	if(a.x > b.x + b.width ||
		a.x + a.width < b.x ||
		a.y > b.y + b.height ||
		a.y + a.height < b.y) {
		return 0;
	} else {
		var overlap = b.x + b.width - a.x;
		return overlap;
	}
}
93049
def SLIT_RECTANGULAR(x,g):
    
    index_inner = abs(x) <= g/2
    index_outer = ~index_inner
    y = zeros(len(x))
    y[index_inner] = 1/g
    y[index_outer] = 0
    return y
1332320
function sampleCubicBézier(x0, y0, x1, y1, x2, y2, x3, y3) {
		// Calculate all the mid-points of the line segments
		const x01   = (x0 + x1) / 2,
		      y01   = (y0 + y1) / 2,
		      x12   = (x1 + x2) / 2,
		      y12   = (y1 + y2) / 2,
		      x23   = (x2 + x3) / 2,
		      y23   = (y2 + y3) / 2,
		      x012  = (x01 + x12) / 2,
		      y012  = (y01 + y12) / 2,
		      x123  = (x12 + x23) / 2,
		      y123  = (y12 + y23) / 2,
		      x0123 = (x012 + x123) / 2,
		      y0123 = (y012 + y123) / 2;

		// Try to approximate the full cubic curve by a single straight line
		const dx = x3-x0,
		      dy = y3-y0;

		const d1 = Math.abs(((x1-x3)*dy - (y1-y3)*dx)),
		      d2 = Math.abs(((x2-x3)*dy - (y2-y3)*dx));

		if (((d1+d2)*(d1+d2)) < (tolerance2 * (dx*dx + dy*dy))) add(x0123,y0123);
		else { // Continue subdivision
		  sampleCubicBézier(x0, y0, x01, y01, x012, y012, x0123, y0123); 
		  sampleCubicBézier(x0123, y0123, x123, y123, x23, y23, x3, y3); 
		}
   }