dvr.java~282~

一个新的voronoi算法实现

        }

    }

    public void constructrchc(Vector<dpoint> rchc, dpoint dtemp) { //rchc construct
        Vector<dpoint> newrchc = new Vector<dpoint>();
        double dx = dtemp.x;
        double dy = dtemp.y;
        int up = -1;
        int down = -1;
        if (dtemp.y >= rchc.elementAt(0).y) {
            for (int i = 0; i < rchc.size(); i++) {
                if (i < rchc.size() - 1) {
                    double ax = rchc.elementAt(i).x - dx;
                    double ay = rchc.elementAt(i).y - dy;

                    double bx = rchc.elementAt(i + 1).x -
                                rchc.elementAt(i).x;
                    double by = rchc.elementAt(i + 1).y -
                                rchc.elementAt(i).y;
                    double f1 = ax * by - bx * ay;
                    if (f1 <= 0) {
                        up = i;
                        break;
                    }

                } else {
                    up = rchc.size() - 1;
                    break;
                }

            }
            if (up != rchc.size() - 1) {

                newrchc.add(dtemp);
                for (int i = up; i < rchc.size(); i++) {
                    dpoint t = rchc.elementAt(i);
                    newrchc.add(t);
                }
            } else {
                newrchc.add(dtemp);
                newrchc.add(rchc.lastElement());
            }

        } else if (dtemp.y <= rchc.lastElement().y) {
            for (int i = 0; i < rchc.size(); i++) {
                if (i != rchc.size() - 1) {
                    double k1 = (rchc.elementAt(i + 1).y -
                                 rchc.elementAt(i).y) /
                                (rchc.elementAt(i + 1).x -
                                 rchc.elementAt(i).x);
                    double k2 = ( -rchc.elementAt(i).y + dy) /
                                ( -rchc.elementAt(i).x + dx);
                    if (k1 < 0 & k2 < 0 & Math.abs(k2) < Math.abs(k1)) {
                        down = i;
                        break;
                    } else if (k1 > 0) {
                        down = i;
                        break;
                    }

                } else {
                    down = rchc.size() - 1;
                    break;
                }
            }

            if (down == rchc.size() - 1) {
                for (int i = 0; i < rchc.size(); i++) {
                    dpoint t = rchc.elementAt(i);
                    newrchc.add(t);
                }
                newrchc.add(dtemp);
            } else {
                for (int i = 0; i <= down; i++) {
                    dpoint t = rchc.elementAt(i);
                    newrchc.add(t);
                }
                newrchc.add(dtemp);
            }

        } else {

            for (int i = 0; i < rchc.size(); i++) {
                double k1 = (rchc.elementAt(i + 1).y - rchc.elementAt(i).y) /
                            (rchc.elementAt(i + 1).x - rchc.elementAt(i).x);
                double k2 = ( -rchc.elementAt(i).y + dy) /
                            ( -rchc.elementAt(i).x + dx);

                if (k1 > 0) {
                    down = i;
                    break;
                } else if (k1 < 0 & Math.abs(k2) < Math.abs(k1)) {
                    down = i;
                    break;
                }

            }
            for (int i = down; i < rchc.size(); i++) {
                if (i != rchc.size() - 1) {
                    double ax = rchc.elementAt(i).x - dx;
                    double ay = rchc.elementAt(i).y - dy;

                    double bx = rchc.elementAt(i + 1).x -
                                rchc.elementAt(i).x;
                    double by = rchc.elementAt(i + 1).y -
                                rchc.elementAt(i).y;
                    double f1 = ax * by - bx * ay;
                    if (f1 <= 0) {
                        up = i;
                        break;
                    }

                } else {
                    up = rchc.size() - 1;
                    break;

                }

            }

            for (int i = 0; i <= down; i++) {
                dpoint t = rchc.elementAt(i);
                newrchc.add(t);

            }
            newrchc.add(dtemp);
            for (int i = up; i < rchc.size(); i++) {
                dpoint t = rchc.elementAt(i);
                newrchc.add(t);
            }

        }
        rchc.removeAllElements();
        for (int i = 0; i < newrchc.size(); i++) {
            dpoint t = newrchc.elementAt(i);
            rchc.add(t);
        }

    }

    public Vector<dpoint> findpos(Vector<dpoint> rchc, dpoint np) { //rchc search

        Vector<dpoint> pos = new Vector<dpoint>();
        double x = np.x;
        double y = np.y;
        int min = 0;
        int max = rchc.size() - 1;
        while (true) {
            if (max == 1) {
                min = 0;
                max = 1;
                double x1 = rchc.elementAt(min).x;
                double y1 = rchc.elementAt(min).y;
                double x2 = rchc.elementAt(max).x;
                double y2 = rchc.elementAt(max).y;
                double f = 0;
                double f1 = 0;
                f = y - y1 + (x1 - x2) / (y1 - y2) * (x - x1);
                f1 = y - y2 + (x2 - x1) / (y2 - y1) * (x - x2);
                double y0 = y1 - (x1 - x2) / (y1 - y2) * (x - x1);
                if (f > 0) {
                    pos.add(rchc.elementAt(0));
                    //                  System.out.println("点 ： " + 0);
                } else if (f <= 0 & f1 >= 0) {
                    pos.add(rchc.elementAt(0));
                    pos.add(rchc.elementAt(1));
                    //                  System.out.println("边 ： " + " 0  1");
                } else if (f1 < 0) {
                    pos.add(rchc.elementAt(1));
                    //                   System.out.println("点 : " + 1);
                }
                return pos;

            } else {
                int mid = (int) (min + max) / 2;
                int midup = mid + 1;
                if (midup < rchc.size()) {

                    double x1 = rchc.elementAt(mid).x;
                    double y1 = rchc.elementAt(mid).y;
                    double x2 = rchc.elementAt(midup).x;
                    double y2 = rchc.elementAt(midup).y;
                    double f = 0;
                    f = y - y1 + (x1 - x2) / (y1 - y2) * (x - x1);
                    double y0 = y1 - (x1 - x2) / (y1 - y2) * (x - x1);
                    if (f > 0 & (max - min) != 1) { //np down
                        max = mid;

                    } else if (f < 0 & (max - min) != 1) { //np up

                        min = mid;
                    } else if (f == 0 || (max - min) == 1) { //np equal

                        break;
                    }
                    /*
                     System.out.println("max  :" + max);
                     System.out.println("mid  :" + mid);
                     System.out.println("min  :" + min);
                     */
                } else if (midup == rchc.size()) {
                    max = rchc.size() - 1;
                    min = rchc.size() - 2;
                    break;

                }
                if (max - min == 1) {

                    double x1 = rchc.elementAt(max).x;
                    double y1 = rchc.elementAt(max).y;
                    double x2 = rchc.elementAt(min).x;
                    double y2 = rchc.elementAt(min).y;
                    double f1 = 0;
                    f1 = y - y1 + (x1 - x2) / (y1 - y2) * (x - x1);
                    if (f1 < 0) { //up
                        //                      System.out.println("点  : " + max);
                        dpoint t = rchc.elementAt(max);
                        pos.add(t);
                    } else if (f1 >= 0) {
                        //                       System.out.println(" 线：  min  : " + min + "   max:  " +
                        //                                          max);
                        dpoint t = rchc.elementAt(min);
                        pos.add(t);
                        t = rchc.elementAt(max);
                        pos.add(t);
                    }
                    break;

                } else {

                }

            }

        }
        return pos;

    }

    public double[] createarray(Vector<dpoint> dpointlist) {
        double[] a = new double[dpointlist.size()];
        for (int i = 0; i < dpointlist.size(); i++) {
            dpoint temp = dpointlist.elementAt(i);
            a[i] = temp.x * 100 + temp.y * 0.1;

        }
        return a;
    }

    public void dpointsort(Vector<dpoint> k, double[] a, int l, int r) { //point sort
        if (l >= r) {
            return;
        } else {
            int i = l;
            int j = r + 1;
            double pivot = a[l];
            while (true) {
                do {
                    i = i + 1;
                } while (i <= r && a[i] < pivot);
                do {
                    j = j - 1;
                } while (j >= l && a[j] > pivot);
                if (i >= j) {
                    break;
                } else {
                    swap(a, i, j);
                    swap(k, i, j);

                }
            }
            a[l] = a[j];
            a[j] = pivot;
            swap(k, l, j);

            dpointsort(k, a, l, j - 1);
            dpointsort(k, a, j + 1, r);
        }

    }

    public void swap(Vector<dpoint> k, int i, int j) {

        dpoint ti = new dpoint();
        dpoint tj = new dpoint();
        ti = k.elementAt(i);
        tj = k.elementAt(j);
        k.remove(i);
        k.insertElementAt(tj, i);
        k.remove(j);
        k.insertElementAt(ti, j);

    }

    public void swap(double[] a, int i, int j) {

        double temp = 0;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public boolean inter(vpoint a, vpoint b, dpoint c, dpoint d) {
        boolean flag;
        double ax = a.x;
        double ay = a.y;
        double cx = c.x;
        double cy = c.y;
        double kab = (b.y - a.y) / (b.x - a.x);
        double kcd = (d.y - c.y) / (d.x - c.x);
        double x = (cy - ay - kcd * cx + kab * ax) / (kab - kcd);
        double y = kab * (x - ax) + ay;
        if ((x >= a.x & x <= b.x || x >= b.x & x <= a.x) &
            (x >= c.x & x <= d.x || x >= d.x & x <= c.x)) {
            flag = true;
        } else {
            flag = false;
        }

        return flag;
    }

    //Get a parameter value
    public String getParameter(String key, String def) {
        return isStandalone ? System.getProperty(key, def) :
                (getParameter(key) != null ? getParameter(key) : def);
    }

    //Construct the applet
    public dvr() {
    }

    //Initialize the applet
    public void init() {
        try {
            jbInit();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    //Component initialization
    private void jbInit() throws Exception {
        this.setLayout(null);
        this.addMouseListener(new dvr_this_mouseAdapter(this));
    }

    //Start the applet
    public void start() {
    }

    //Stop the applet
    public void stop() {
    }

    //Destroy the applet
    public void destroy() {
    }

    //Get Applet information
    public String getAppletInfo() {
        return "Applet Information";
    }

    //Get parameter info
    public String[][] getParameterInfo() {
        return null;
    }


}


class dvr_this_mouseAdapter extends MouseAdapter {
    private dvr adaptee;
    dvr_this_mouseAdapter(dvr adaptee) {
        this.adaptee = adaptee;
    }

    public void mouseClicked(MouseEvent e) {
        adaptee.this_mouseClicked(e);
    }
}