圆线交点

public static ArrayList<IntPoint> 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<IntPoint> intersections = new ArrayList<IntPoint>(); 
    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 < 0){ 
      return intersections; 
     } 
     else{ 
      y1 = (-B + Math.sqrt(disc))/(2 * A); 
      y2 = (-B - Math.sqrt(disc))/(2 * A); 

      x1 = pointB.x; 
      x2 = pointB.x; 
     } 
     point1 = new IntPoint((int)x1, (int)y1); 
     point2 = new IntPoint((int)x2, (int)y2); 
     if (Util.euclideanDistance(pointA, point2) > 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 < 0){ 
      return intersections; 
     } 
     else{ 
      x1 = (-B + Math.sqrt(disc))/(2 * A); 
      x2 = (-B - Math.sqrt(disc))/(2 * A); 

      y1 = slope * x1 - c; 
      y2 = slope * x2 - c; 
     } 
    } 

    point1 = new IntPoint((int)x1, (int)y1); 
    point2 = new IntPoint((int)x2, (int)y2); 
    if (Util.euclideanDistance(pointA, point2) > 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; 
}

我正在使用上述算法来测试圆和直线之间的交集。它有时可以正常工作，但在其他时候失败。代码表示从圆和线方程式(x-a)^+(y-b)^2=r^2和y = mx - mx1 + y1同时求解x得出的方程式。有没有人知道我在数学或其他地方出错？圆线交点

来源

2012-10-24 cobie

一个解决方案，您能否给一些线条和导致失败界的例子吗？为什么你将x，y坐标转换为整数？ –

你可以尝试在你使用它们的地方声明你的变量，而不是完全在其他地方？给他们更有意义的名字？（尽管'斜坡'是一个很好的开始。）除此之外，我也不希望你想要的点有整数坐标，所以投射看起来非常可疑。 –

正在使用的IntPoint类由库提供，坐标必须在int – cobie

您的计算似乎很长，我没有看到您测试的不同情况的使用。无论如何，因为我发现这个问题很有趣，所以我试图自己解决这个问题，并提出了以下建议。请随意用int radius替换double radius并使用IntPoint s，但请注意，如您在评论中讨论的那样，每次投射时，不是精确的整数交点的结果都会出错。

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

import java.util.Arrays; 
import java.util.Collections; 
import java.util.List; 

public class CircleLine { 

    public static List<Point> 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))); 
    }

来源

2012-10-24 18:05:42

迄今为止的作品魅力...我必须说谢谢！ – cobie

请问你能否给出一些关于在这段代码 – cobie

中发生了什么的说明，'a'，b和'c'是解决二次方程的系数，尽管我更喜欢（1，）p和' q'。由于实际的b包含2作为一个因子，因此p也是如此，但p必须除以2，实际上我只使用b和p的一半作为中间变量。至于如何到达a，b和c ...那么，向量AC（从A到圆心）是什么？什么是AB？对上面给出的方程进行平方，变换... ;-) –

这里有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 * d.y/dSq + o.x, -det * d.x/dSq + o.y); 

     return t; 
    } 

    double discSqrt = Math.sqrt(discrimant); 

    double sgn = 1; 
    if (d.y < 0) { 
     sgn = -1; 
    } 

    Vector2d[] t = new Vector2d[2]; 
    t[0] = new Vector2d((det * d.y + sgn * d.x * discSqrt)/dSq + o.x, (-det * d.x + Math.abs(d.y) * discSqrt)/dSq + o.y); 
    t[1] = new Vector2d((det * d.y - sgn * d.x * discSqrt)/dSq + o.x, (-det * d.x - Math.abs(d.y) * discSqrt)/dSq + o.y); 
    return t; 

}

来源

2015-03-15 22:43:59

回答

相关问题