最小覆盖(外接)圆算法,java版

最近在学习算法和数据结构,刚好公司有了一个需要算法应用的场景。
需求时一个最小覆盖圆问题。 在LBS相关的应用中,可能存在这样的场景, 给定n个点的经纬度,求一个最小的,覆盖所有这n个点的圆的圆心。 地球时球形,经纬度不同于二维平面上的xy坐标。但是当几个点的距离不那么遥远的时候,二者近似。

这个算法并不简单。借助于google,找到了2篇参考文章。下面是参考地址:
http://wenku.baidu.com/view/47c0c1758e9951e79b8927b3.html
http://web.nmsu.edu/~xiumin/project/smallest_enclosing_circle/

下面是实现代码:

package cycle;

import java.util.ArrayList;
import java.util.List;



public class MinCycle2 {

    public static void main(String[] args) {

        List<Point> list = new ArrayList<Point>();

//        list.add(new Point(0, 0));
//        list.add(new Point(10, 10));
//        list.add(new Point(30, 40));
//        list.add(new Point(18, 6));

//        list.add(new Point(-5, 0));
//        list.add(new Point(0, -5));
//        list.add(new Point(5, 0));
//        list.add(new Point(0, 5));

        list.add(new Point(2, 2));
        list.add(new Point(3, 4));
        list.add(new Point(20, 100));
        list.add(new Point(1, 2));
        list.add(new Point(90, 40));
        list.add(new Point(4, 2));
        list.add(new Point(0, 0));
        list.add(new Point(10, 18));

        long t1 = System.currentTimeMillis();
        new MinCycle2().work(list);
        long t2 = System.currentTimeMillis();

        System.out.println(t2 - t1);
    }


    public void work(List<Point> list) {
        ArrayList<Point> sList = new ArrayList<Point>();
        ArrayList<Point> rList = new ArrayList<Point>();


        Cycle cycle = new Cycle(0, 0, 0);
        for (int i = 0; i < list.size(); i++) {
            Point point = list.get(i);
            if (!this.enclose(cycle, point)) {
                sList.add(point);
                cycle = mc(sList, sList.size(), rList, 0);
            }
        }

        System.out.println("result : " + cycle);


    }

    public Cycle mc(ArrayList<Point> sList, int n,  ArrayList<Point> rList, int m) {

        Cycle cycle = new Cycle(0, 0, 0);

        if (m == 1) {
            cycle = getCycle(rList.get(0));
        } else if (m == 2) {
            cycle = getCycle(rList.get(0), rList.get(1));
        } else if (m == 3) {
            cycle = getCycle(rList.get(0), rList.get(1), rList.get(2));
            return cycle;
        }

        for (int i = 0; i < n; i++) {
            Point p = sList.get(i);
            boolean enclose = this.enclose(cycle, p);
            if (!enclose) {
                rList.add(m, p);
                cycle = mc(sList, i, rList, m+1);
            }
        }

        return cycle;
    }

    private Cycle getCycle(Point point) {
        return new Cycle(point.x, point.y, 0);
    }

    private Cycle getCycle(Point p1, Point p2) {
        double x = (p1.x + p2.x) / 2;
        double y = (p1.y + p2.y) / 2;

        double distance = (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
        double r = Math.sqrt(distance) / 2;

        return new Cycle(x, y, r);
    }

    private Cycle getCycle(Point a, Point b, Point c) {
        double a1=b.x-a.x, b1=b.y-a.y, c1=(a1*a1+b1*b1)/2;
        double a2=c.x-a.x, b2=c.y-a.y, c2=(a2*a2+b2*b2)/2;
        double d = a1*b2 - a2*b1;

        double x = a.x + (c1*b2-c2*b1)/d;
        double y = a.y + (a1*c2-a2*c1)/d;

        double distance = (x - a.x) * (x - a.x) + (y - a.y) * (y - a.y);
        double r = Math.sqrt(distance) / 2;

        return new Cycle(x, y, r);
    }


    private boolean enclose(Cycle cycle, Point point) {
        boolean result = ((cycle.x - point.x) * (cycle.x - point.x) + (cycle.y - point.y) * (cycle.y - point.y)) <= (cycle.r * cycle.r);
        return result;
    }


}

(全文完)

发表评论

电子邮件地址不会被公开。 必填项已用*标注