射线与多圆碰撞检测求解失败问题求助

项目背景 #

我正在编写一个计算直线与圆交点的方法，作为光线投射（ray casting）Demo的第一步。计算出交点后，会选取距离起点最近的交点作为碰撞点，再从该碰撞点出发重复射线投射流程。这个Demo的灵感来自一个激光碰撞不同圆形的视频。

该方法的参数包括：射线角度、起点坐标、窗口尺寸、圆形半径、圆心坐标数组，以及JavaFX的GraphicsContext对象。

我用两个布尔变量判断是否发生碰撞，并用ArrayList存储后续要在JavaFX Canvas上绘制的碰撞点。在while循环内，以y = m*x + b的形式定义直线方程，随后通过计算圆心到直线的距离判断是否发生碰撞；当圆心到直线的距离小于圆半径时，联立直线方程与圆方程得到二次方程，判别式满足条件时取最近的交点作为碰撞点，再根据圆心、碰撞点和起点计算新的射线角度，更新射线后重复循环；若未检测到与圆形的碰撞，则计算射线与窗口边界的碰撞。最后通过for循环绘制所有碰撞线段。

核心问题 #

圆心到直线的最短距离计算存在错误，导致后续代码无法验证。我试过多种距离计算方法，当前选用的方法虽易于理解但效果不佳，怀疑可能和JavaFX的坐标系（x轴向右递增，y轴向下递增）有关，但不确定，目前陷入瓶颈。

代码及测试用例 #

主方法代码 #

private void extendPoint(double angle, Point origin, double x, double y, double radius, ArrayList<Point> pointList) {
    
    double newAngle = angle; // 定义直线方向的角度
    
    // 用于处理射线未击中圆的情况
    double angle11 = Math.atan2(origin.getY(), origin.getX());
    double angle_11 = Math.atan2(origin.getY(), -origin.getX());
    double angle_1_1 = angle11 + Math.PI;
    double angle1_1 = angle_11 + Math.PI;

    boolean noCollision = true; // 未击中圆时为true
    boolean repeat = true; // 控制while循环，无碰撞时停止
    Point currentPoint = Point.copy(origin); // (x0, y0)
    Point collision = new Point(-1,-1); // 存储碰撞点
    Point newDirection = new Point(-1,-1); // 碰撞后的新方向，返回向量的(模长, 角度)
    ArrayList <Point> collisionList = new ArrayList<>(); // 存储后续要绘制的碰撞点
    collisionList.add(origin); // 起点加入列表用于绘制
    
    while(repeat == true) {
        // 过某点且指定角度的直线方程：y = a*x - a*x0 + y0 -> y = m*x + b
        double m = Math.tan(-newAngle);
        double a = m;
        double b = -m*currentPoint.getX() + (currentPoint.getY());

        for(int i = 0; i < pointList.size(); i++) {
            Point gridPoint = pointList.get(i); // (x1, y1)
            
            // 参考点到直线的距离公式：直线Ax+By+C=0
            double A = gridPoint.getY()-currentPoint.getY();
            double B = gridPoint.getX()-currentPoint.getX(); 
            double C = -currentPoint.getY()*B + currentPoint.getX()*A;
//          double d_cp_gp = Math.abs(m*gridPoint.getX()-b*(gridPoint.getY()))/(Math.sqrt(m*m + 1));
            double d_cp_gp = Math.abs(A + B + C)/Math.sqrt(A*A + B*B);

            if(d_cp_gp < radius) {
                System.out.println("距离 " + d_cp_gp);
                // 直线与圆的交点计算：圆方程(x-x1)^2 + (y-y1)^2 = r^2
                // 代入直线方程y = a*x + b得到二次方程
                double p2 = 1 + a*a;
                double p1 = -2*gridPoint.getX() + 2*a*b;
                double p0 = gridPoint.getX()*gridPoint.getX() + b*b - radius*radius;
                double p0_ = 4*p0*p2;
                System.out.println(p1*p1 + " " + p0_);
                // 判断二次方程是否有实根
                if(p1*p1 >= p0_) {
                    System.out.println("存在交点");
                    // 计算根
                    double root = Math.sqrt(p1*p1 - p0_);
                    double sol1x = (-p1 + root)/(2*p2);
                    double sol2x = (-p1 - root)/(2*p2);
                    double sol1y = a*sol1x - a*currentPoint.getX() + currentPoint.getY();
                    double sol2y = a*sol1x - a*currentPoint.getX() + currentPoint.getY();
                    
                    // 选距离当前点最近的交点
                    double distSol1 = Math.sqrt(Math.pow(currentPoint.getX()- sol1x, 2) + 
                            Math.pow(currentPoint.getY() - sol1y, 2));
                    double distSol2 = Math.sqrt(Math.pow(currentPoint.getX()- sol2x, 2) + 
                            Math.pow(currentPoint.getY() - sol2y, 2));
                    
                    if(distSol1 < distSol2) {
                        collision.setXY(sol1x, sol1y);
                    }
                    else {
                        collision.setXY(sol2x, sol2y);
                    }

                    // 计算碰撞后的新角度
                    newDirection = newAngle(currentPoint, gridPoint, collision, radius);
                    currentPoint = collision;
                    
                    // 更新直线方程参数
                    m = Math.tan(-newDirection.getY());
                    a = m;
                    b = -m*collision.getX() + (collision.getY());
                    collisionList.add(collision);
                    System.out.println("碰撞点计算完成: " + collision.toString());
                    
                    noCollision= false;
                }
            }

            // 遍历完所有圆都无碰撞则退出循环
            if(i == pointList.size() - 1 && noCollision == true) {
                repeat = false;
            }
        }
        // 无圆碰撞时计算与窗口边界的碰撞
        if(noCollision == true && repeat == false) {

            if(angle<angle11 || angle > angle1_1) {
                collision.setXY(x, m*x + b);
            }
            else if(angle > angle11 && angle < angle_11){
                collision.setXY((0 - b)/m, 0);
            }
            else if(angle > angle_1_1 && angle < angle_1_1) {
                collision.setXY(0, m*0 + b);
            }
            else if(angle> angle_1_1 && angle < angle1_1) {
                collision.setXY((y - b)/m, y);
            }

            collisionList.add(collision);
        }
        
    }
    
    System.out.println("碰撞次数: " + (int)(collisionList.size() - 1));
}

Point类定义 #

public class Point {
    private double x;
    private double y;
    
    public Point(double x, double y) {
        this.x = x;
        this.y = y;}
    public double getX() {
        return x;}
    public double getY() {
        return y;}
    public void setX(double x) {
        this.x = x;}
    public void setY(double y) {
        this.y = y;}
    public void setXY(double x, double y) {
        this.x = x;
        this.y = y;}
    
    @Override
    public String toString() {
        return("(" + this.x + "," + this.y + ")");
    }
    public static Point copy(Point a) {
        return new Point(a.getX(), a.getY());
    }
}

Vector类定义 #

public class Vector {
    private double vx; 
    private double vy; 
    private double ptoApX; 
    private double ptoApY; 
    private double angle;
    private double modulo;
    
    
    public Vector(double vx, double vy) {
        this.vx = vx;
        this.vy = vy;
        this.ptoApX = 0;
        this.ptoApY = 0;
        this.angle = angle(vx,vy);
        this.modulo = modulo(vx,vy);
    }
    // Getters
    public double getVx() {
        return this.vx;
    }
    public double getVy() {
        return this.vy;
    }
    public double getPtoApX() {
        return this.ptoApX;
    }
    public double getPtoApY() {
        return this.ptoApY;
    }
    public double getAngle() {
        return this.angle;
    }
    public double getModulo() {
        return this.modulo;
    }
    
    // Setters
    public void setVx(double vx) {
        this.vx = vx;
    }
    public void setVy(double vy) {
        this.vy = vy;
    }
    public void setPtoApX(double ptoApX) {
        this.ptoApX = ptoApX;
    }
    public void setPtoApY(double ptoApY) {
        this.ptoApY = ptoApY;
    }
    public void setAngle(double angle) {
        this.angle = angle;
    }
    public void setModulo(double modulo) {
        this.modulo = modulo;
    }
    
    // To String
    @Override
    public String toString() {
        return "("+this.getVx()+","+this.getVy()+")";
    }
    
    
    public static double dotProduct(Vector a, Vector b) {
        return a.getVx()*b.getVx() + a.getVy()*b.getVy();
    }
    public static Vector escalarProduct(Vector v, double n) {
        return new Vector(n*v.getVx(), n*v.getVy());
    }
    public static Vector vectorWith2Points(Point a, Point b) {
        Point p = Point.resta(a,b);
        return new Vector(p.getX(),p.getY());
    }
    public static Vector vectorPointAngle(Point a, double angle, double modulo) {
        double angleRadians = Math.toRadians(angle);
        Point b = new Point(Math.cos(angleRadians)*modulo, Math.sin(angleRadians)*modulo);
        return vectorWith2Points(a,b);
    }
    public static double modulo(double vx, double vy) {
        return Math.sqrt(vx*vx + vy*vy);
    }
    public static double angle(double vx, double vy) {
        return Math.atan2(vy, vx);
    }
    public static Vector normalize(Vector v) {
        return new Vector(v.getVx()/v.getModulo(),v.getVy()/v.getModulo());
    }
    public static double angle2vectors(Vector u, Vector v) {
        double argument = dotProduct(u,v)/(u.getModulo()*v.getModulo());
        return Math.acos(argument);
    }
    public static Point polar2cart(double r, double angle) {
        return new Point(r*Math.cos(angle), r*Math.sin(angle));
    }
    public static Point cart2polar(Point p) {
        return new Point(modulo(p.getX(), p.getY()), angle(p.getX(), p.getY()));
    }
    
}

碰撞后新角度计算方法 #

private Point newAngle(Point origin, Point center, Point c, double radius) {
    // 法向量
    Vector n = Vector.vectorWith2Points(c, center);
    Vector nNorm = Vector.normalize(n);

    // 入射向量
    Vector d = Vector.vectorWith2Points(c, origin);
    // 切向量
    Vector tg = new Vector(-nNorm.getVy(), nNorm.getVx());
    
    // 反射向量
    double product = Vector.dotProduct(d,tg);
    Vector r = new Vector(d.getVx()-2*product*tg.getVx(),
                                d.getVy() - 2*product*tg.getVy());
    return new Point(r.getModulo(), r.getAngle());
}

测试用例 #

double x = 600;
double y = 400;
double radius = 10;
Point origin = new Point(x/2, y/2);
ArrayList<Point> pointList = new ArrayList<>();
pointList.add(new Point(40,40));
pointList.add(new Point(500,100));
pointList.add(new Point(40,330));
pointList.add(new Point(450,300));
// 应该检测到碰撞
extendPoint(0.4363323129985824, origin, x, y, radius, pointList);
extendPoint(2.6179938779914944, origin, x, y, radius, pointList);

// 不应检测到碰撞但实际返回了碰撞
extendPoint(1.5707963267948966, origin, x, y, radius, pointList);
extendPoint(-1.5707963267948966, origin, x, y, radius, pointList);

内容的提问来源于stack exchange，提问作者sushiwithoutsushi