11 
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とから x を同時に解くことで得られる方程式を表しy = mx - mx1 + y1ます。数学や他の場所で私が間違っている場所を誰かが知っていますか?

4

2 に答える 2

30

あなたの計算はかなり長いようで、あなたがテストしたさまざまなケースの使用は見られません。とにかく、私は問題が面白いと思ったので、自分で解決しようと試み、次のことを思いつきました。自由に置き換えdouble radiusてsint radiusを使用IntPointしてください。ただし、コメントで説明されているように、キャストするたびに、正確な整数交点ではない結果が間違ったものになることに注意してください。

実行される計算の背景は次のとおりです。点 A から、ベクトル AB のスケーリングされたバージョンが円上の点を指します。その点は中心から距離半径を持っています。したがって、|AC + スケーリング係数 * 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-24T18:05:42.667 に答える