円線交点点

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

私は上記のアルゴリズムを使用して円と線の交差をテストしています。それはうまく動作することがありますが、それ以外の時は失敗します。コードは、円と線の式(x-a)^+(y-b)^2=r^2とy = mx - mx1 + y1からxを同時に解いて得られる式を表します。誰かが私の数学や他の場所で間違っていると思っていますか？

Answer 1

あなたの計算はかなり長いように思えますが、私はあなたがテストしたさまざまなケースの使用を見ません。 とにかく面白い問題を発見したので、私はそれを自分で解決しようとして、次のことを考え出しました。 double radiusをint 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<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

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; 

}