圆线交点

public static ArrayList getCircleLineIntersectionPoint(IntPoint pointA, IntPoint pointB, IntPoint center, int radius) { // returns a list of intersection points between a line which passes through given points, // pointA and pointB, and a circle described by given radius and center coordinate double disc, A, B, C, slope, c; double x1, x2, y1, y2; IntPoint point1, point2; ArrayList intersections = new ArrayList(); try{ slope = Util.calculateSlope(pointA, pointB); }catch (UndefinedSlopeException e){ C = Math.pow(center.y, 2) + Math.pow(pointB.x, 2) - 2 * pointB.x * center.x + Math.pow(center.x, 2) - Math.pow(radius, 2); B = -2 * center.y; A = 1; disc = Math.pow(B, 2) - 4 * 1 * C; if (disc  Util.euclideanDistance(pointA, point1)){ intersections.add(point1); } else{ intersections.add(point2); } return intersections; } if (slope == 0){ C = Math.pow(center.x, 2) + Math.pow(center.y, 2) + Math.pow(pointB.y, 2) - 2 * pointB.y * center.y - Math.pow(radius, 2); B = -2 * center.x; A = 1; disc = Math.pow(B, 2) - 4 * 1 * C; if (disc < 0){ return intersections; } else{ x1 = (-B + Math.sqrt(disc)) / (2*A); x2 = (-B - Math.sqrt(disc)) / (2*A); y1 = pointB.y; y2 = pointB.y; } } else{ c = slope * pointA.x + pointA.y; B = (2 * center.x + 2 * center.y * slope + 2 * c * slope); A = 1 + Math.pow(slope, 2); C = (Math.pow(center.x, 2) + Math.pow(c, 2) + 2 * center.y * c + Math.pow(center.y, 2) - Math.pow(radius, 2)); disc = Math.pow(B, 2) - (4 * A * C); if (disc  Util.euclideanDistance(pointA, point1)){ //if (Util.angleBetween(pointA, pointB, point1) < Math.PI/2){ intersections.add(point1); //} } else{ //if (Util.angleBetween(pointA, pointB, point1) < Math.PI/2){ intersections.add(point2); //} } return intersections; } 

我使用上面的算法来测试圆和线之间的交集。 它有时很好，但在其他时候失败。 该代码表示​​从圆和线方程(xa)^+(yb)^2=r^2和y = mx - mx1 + y1同时求解x得到的方程。 有没有人知道我在数学或其他地方出错了？

Answer 1

你的计算似乎很长，我没有看到你测试的不同情况的使用。 无论如何，因为我发现问题很有趣，我试图自己解决它并提出以下内容。 可以随意用int radius替换double radius并使用IntPoint ，但要注意每次进行转换时，如注释中所讨论的那样，不是精确整数交叉点的结果将会出错。

执行计算的背景是：从A点开始，矢量AB的缩放版本指向圆上的点。 该点与中心的距离半径。 因此，| AC + scalingFactor * AB | = r。

 import java.util.Arrays; import java.util.Collections; import java.util.List; public class CircleLine { public static List getCircleLineIntersectionPoint(Point pointA, Point pointB, Point center, double radius) { double baX = pointB.x - pointA.x; double baY = pointB.y - pointA.y; double caX = center.x - pointA.x; double caY = center.y - pointA.y; double a = baX * baX + baY * baY; double bBy2 = baX * caX + baY * caY; double c = caX * caX + caY * caY - radius * radius; double pBy2 = bBy2 / a; double q = c / a; double disc = pBy2 * pBy2 - q; if (disc < 0) { return Collections.emptyList(); } // if disc == 0 ... dealt with later double tmpSqrt = Math.sqrt(disc); double abScalingFactor1 = -pBy2 + tmpSqrt; double abScalingFactor2 = -pBy2 - tmpSqrt; Point p1 = new Point(pointA.x - baX * abScalingFactor1, pointA.y - baY * abScalingFactor1); if (disc == 0) { // abScalingFactor1 == abScalingFactor2 return Collections.singletonList(p1); } Point p2 = new Point(pointA.x - baX * abScalingFactor2, pointA.y - baY * abScalingFactor2); return Arrays.asList(p1, p2); } static class Point { double x, y; public Point(double x, double y) { this.x = x; this.y = y; } @Override public String toString() { return "Point [x=" + x + ", y=" + y + "]"; } } public static void main(String[] args) { System.out.println(getCircleLineIntersectionPoint(new Point(-3, -3), new Point(-3, 3), new Point(0, 0), 5)); System.out.println(getCircleLineIntersectionPoint(new Point(0, -2), new Point(1, -2), new Point(1, 1), 5)); System.out.println(getCircleLineIntersectionPoint(new Point(1, -1), new Point(-1, 0), new Point(-1, 1), 5)); System.out.println(getCircleLineIntersectionPoint(new Point(-3, -3), new Point(-2, -2), new Point(0, 0), Math.sqrt(2))); } 

Answer 2

这里有一个import javax.vecmath.Vector2d;的解决方案import javax.vecmath.Vector2d;

 static Vector2d[] circleLineIntersection1(Vector2d a, Vector2d b, Vector2d o, double radius) { Vector2d p1 = new Vector2d(a); Vector2d p2 = new Vector2d(b); p1.sub(o); p2.sub(o); Vector2d d = new Vector2d(); d.sub(p2, p1); double det = p1.x * p2.y - p2.x * p1.y; double dSq = d.lengthSquared(); double discrimant = radius * radius * dSq - det * det; if (discrimant < 0) { return new Vector2d[0]; } if (discrimant == 0) { Vector2d[] t = new Vector2d[1]; t[0] = new Vector2d(det * dy / dSq + ox, -det * dx / dSq + oy); return t; } double discSqrt = Math.sqrt(discrimant); double sgn = 1; if (dy < 0) { sgn = -1; } Vector2d[] t = new Vector2d[2]; t[0] = new Vector2d((det * dy + sgn * dx * discSqrt) / dSq + ox, (-det * dx + Math.abs(dy) * discSqrt) / dSq + oy); t[1] = new Vector2d((det * dy - sgn * dx * discSqrt) / dSq + ox, (-det * dx - Math.abs(dy) * discSqrt) / dSq + oy); return t; }