From x,y point cast a ray to right. and intersect with edge x0, y0, x1, y1; Return x value of intersect point
515930
function intersectEdge(x0, y0, x1, y1, x, y) {
    if ((y > y0 && y > y1) || (y < y0 && y < y1)) {
        return -Infinity;
    }
    // Ignore horizontal line
    if (y1 === y0) {
        return -Infinity;
    }
    var dir = y1 < y0 ? 1 : -1;
    var t = (y - y0) / (y1 - y0);

    // Avoid winding error when intersection point is the connect point of two line of polygon
    if (t === 1 || t === 0) {
        dir = y1 < y0 ? 0.5 : -0.5;
    }

    var x_ = t * (x1 - x0) + x0;

    return x_;
}
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;
    }
19078
function(x, y) {
    x = (x - this.viewport[0]) / this.viewport[2];
    y = 1 - (y - this.viewport[1]) / this.viewport[3];
    var ray0 = Vector.lerp(this.ray00, this.ray10, x);
    var ray1 = Vector.lerp(this.ray01, this.ray11, x);
    return Vector.lerp(ray0, ray1, y).unit();
  }
264572
def ceil(self):
    """"""
    return Point(int(math.ceil(self.x)), int(math.ceil(self.y)))
600439
private Point intersection(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    double dem = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);

    // Solve the intersect point
    double xi = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / dem;
    double yi = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / dem;

    // Check the point isn't off the ends of the lines
    if ((x1 - xi) * (xi - x2) >= 0 && (x3 - xi) * (xi - x4) >= 0 && (y1 - yi) * (yi - y2) >= 0
        && (y3 - yi) * (yi - y4) >= 0) {
      return new Point((int) xi, (int) yi);
    }
    return null;
  }
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;
    }
744023
public int selectPoint( double x, double y ) {
        double mind = Double.POSITIVE_INFINITY;
        selection = -1;
        for( int i = 0; i < pts.size(); i++ ) {
            Coordinate coordinate = pts.get(i);

            double d = sqr(coordinate.x - x) + sqr(coordinate.y - y);
            if (d < mind && d < EPSILON) {
                mind = d;
                selection = i;
            }
        }
        return selection;
    }
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;
  }
}
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};
}
283929
public static int intersectShape (IShape s, float x, float y, float w, float h) {
        if (!s.bounds().intersects(x, y, w, h)) {
            return 0;
        }
        return intersectPath(s.pathIterator(null), x, y, w, h);
    }
1050146
function(point, angle, range) {
    var sin = Math.sin(angle);
    var cos = Math.cos(angle);

    return this.ray(sin, cos, range, {
      x: point.x,
      y: point.y,
      height: 0,
      dist: 0
    });
  }
675326
function getCrossings (points, edges, edgeBounds) {
  var result = []
  boxIntersect(edgeBounds, function (i, j) {
    var e = edges[i]
    var f = edges[j]
    if (e[0] === f[0] || e[0] === f[1] ||
      e[1] === f[0] || e[1] === f[1]) {
      return
    }
    var a = points[e[0]]
    var b = points[e[1]]
    var c = points[f[0]]
    var d = points[f[1]]
    if (segseg(a, b, c, d)) {
      result.push([i, j])
    }
  })
  return result
}
279208
def point(self, x, y):
        """"""
        shapeType = POINT
        pointShape = Shape(shapeType)
        pointShape.points.append([x, y])
        self.shape(pointShape)
509697
function pointInTriangle(px, py, ax, ay, bx, by, cx, cy)
{
    var v0x = cx-ax;
    var v0y = cy-ay;
    var v1x = bx-ax;
    var v1y = by-ay;
    var v2x = px-ax;
    var v2y = py-ay;

    var dot00 = v0x*v0x+v0y*v0y;
    var dot01 = v0x*v1x+v0y*v1y;
    var dot02 = v0x*v2x+v0y*v2y;
    var dot11 = v1x*v1x+v1y*v1y;
    var dot12 = v1x*v2x+v1y*v2y;

    var invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
    var u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    var v = (dot00 * dot12 - dot01 * dot02) * invDenom;

    // Check if point is in triangle
    return (u >= 0) && (v >= 0) && (u + v < 1);
}
1048977
def cart2spher(x, y, z):
    """"""
    hxy = np.hypot(x, y)
    r = np.hypot(hxy, z)
    theta = np.arctan2(z, hxy)
    phi = np.arctan2(y, x)
    return r, theta, phi
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]