Circle Line Punti di intersezione

Question

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; 
} 

Sto utilizzando l'algoritmo di cui sopra per verificare l'intersezione tra un cerchio e una linea. Funziona bene a volte ma altre volte fallisce. Il codice rappresenta l'equazione che deriva dalla risoluzione di x simultaneamente dalle equazioni di cerchio e di linea (x-a)^+(y-b)^2=r^2 e y = mx - mx1 + y1. Qualcuno ha avuto un'idea di dove sbaglio o nella mia matematica o altrove?

Answer 1

I calcoli sembrano abbastanza lunghi e non vedo l'uso dei diversi casi testati. Comunque, dal momento che ho trovato il problema interessante, ho tentato di risolverlo da solo e ho scoperto quanto segue. Sentiti libero di sostituire double radius per int radius e usa IntPoint s, ma ricorda che ogni volta che lanci, come discusso nei commenti, i risultati che non sono punti di intersezione interi esatti diventeranno errati.

Lo sfondo dei calcoli eseguiti è questo: Dal punto A, una versione in scala del vettore AB punta a un punto sul cerchio. Quel punto ha raggio di distanza dal centro. Quindi, | AC + fattore di scala * 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))); 
    } 

Answer 2

Ecco una soluzione con 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; 

}