2008年7月5日星期六

解析法计算两圆交点

中学解析几何知道圆的方程,因此计算两圆交点只需要将两个方程联立,解这个二元二次方程组即可。很容易降幂,化成二元一次方程和圆方程,几何意义是计算直线和圆的交点。下面是用Java实现的代码,可以直观验证解的正确性。
package chap9;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.Arrays;

import javax.swing.JFrame;

public class CrossPoint extends JFrame {
    private static final long serialVersionUID = 1L;

    public CrossPoint() {
        super("Cross Point");
        setSize(400, 500);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setVisible(true);
        play();
    }

    private double rnd(double k) {
        return Math.random() * k;
    }

    @Override
    public void paint(Graphics g) {
        g.clearRect(0, 0, getWidth(), getHeight());
        Circle c1 = new Circle(rnd(200), rnd(280), 100 + rnd(100));
        c1.drawOn(g);
        Circle c2 = new Circle(rnd(250), rnd(200), 100 + rnd(200));
        c2.drawOn(g);
        Point[] ps = c1.crossAt(c2);
        if (ps == null)
            System.out.println("not cross");
        else
            System.out.println(Arrays.toString(ps));
    }

    public static void main(String[] args) {
        new CrossPoint();
    }

    private void play() {
        addMouseMotionListener(new MouseAdapter() {
            @Override
            public void mouseMoved(MouseEvent e) {
                Point p = e.getPoint();
                setTitle(p.toString());
            }
        });
        addMouseListener(new MouseAdapter() {
            @Override
            public void mousePressed(MouseEvent e) {
                repaint();
            }
        });
    }

}

class Circle {
    double x, y, d;

    public Circle(double x, double y, double d) {
        super();
        this.x = x;
        this.y = y;
        this.d = d;
    }

    public void drawOn(Graphics g) {
        int r = (int) d / 2;
        g.setColor(Color.BLACK);
        g.drawOval((int) x - r, (int) y - r, (int) d, (int) d);
    }

    public double distanceTo(Circle c2) {
        return Point.distance(x, y, c2.x, c2.y);
    }

    public Point[] crossAt(Circle c2) {
        double r1 = d / 2;
        double r2 = c2.d / 2;
        double L = distanceTo(c2);
        if (L > r1 + r2)
            return null;
        double dx = x - c2.x;
        double dy = y - c2.y;
        double dr = (r2 * r2 - r1 * r1 - dx * dx - dy * dy) / 2;
        double a = dx * dx + dy * dy;
        double b, c, d, x01, x02, y01, y02;
        if (isZero(dx)) {
            b = -2 * dx * dr;
            c = dr * dr - r1 * r1 * dy * dy;
            d = Math.sqrt(b * b - 4 * a * c);
            x01 = (-b + d) / (2 * a);
            x02 = (-b - d) / (2 * a);
            y01 = (dr - x01 * dx) / dy;
            y02 = (dr - x02 * dx) / dy;
        } else {
            b = -2 * dy * dr;
            c = dr * dr - r1 * r1 * dx * dx;
            d = Math.sqrt(b * b - 4 * a * c);
            y01 = (-b + d) / (2 * a);
            y02 = (-b - d) / (2 * a);
            x01 = (dr - y01 * dy) / dx;
            x02 = (dr - y02 * dy) / dx;
        }
        return new Point[] { new Point((int) (x01 + x), (int) (y01 + y)),
                new Point((int) (x02 + x), (int) (y02 + y)) };
    }

    private boolean isZero(double dx) {
        return Math.abs(dx) < 0.001;
    }
}

没有评论: