dv.java

一个新的voronoi算法实现

package dv;

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.util.*;

public class dv extends Applet {
    boolean isStandalone = false;
    BorderLayout borderLayout1 = new BorderLayout();
    int clicknum = 0;
    Vector<vpoint> vpointlist = new Vector<vpoint>(); //store the voronoi points
    Vector<dpoint> dpointlist = new Vector<dpoint>(); //store the delaunary points (create point)
    Vector<edge> edgelist = new Vector<edge>(); //store the edges
    Vector<dpoint> rchc = new Vector<dpoint>(); //store the right hull chain
    Vector<vpoint> vpointliststore = new Vector<vpoint>();
    int vpointkey = 0;
    int dpointkey = 0;
    int edgekey = 0;

    double unlimit = 9999;
    double max = 20000;
    int kkx = 0;
    int kky = 0;
    int kkx1 = 0;
    int kky1 = 0;
    int kkx2 = 0;
    int kky2 = 0;
    int index0 = 3;
    int god = 1;
    double det = 0.01;

    public void paint(Graphics g) {
        if (!(kkx == 0 & kky == 0)) {
            g.setColor(Color.red);
            g.fillOval(kkx, kky, 10, 10);
        }
        if (!(kkx1 == 0 & kky1 == 0)) {
            g.setColor(Color.green);
            g.fillOval(kkx1, kky1, 10, 10);
        }
        if (!(kkx2 == 0 & kky2 == 0)) {
            g.setColor(Color.blue);
            g.fillOval(kkx2, kky2, 10, 10);
        }
        g.setColor(Color.black);
        for (int i = 0; i < edgelist.size(); i++) {
            edge t = edgelist.elementAt(i);
            g.drawLine((int) t.a.x, (int) t.a.y, (int) t.b.x, (int) t.b.y);

        }
        g.setColor(Color.red);
        for (int i = 0; i < dpointlist.size(); i++) {
            dpoint t = dpointlist.elementAt(i);
            g.fillOval((int) t.x, (int) t.y, 4, 4);
        }

        g.setColor(Color.green);

        if (rchc.size() != 2) {
            for (int i = 0; i < rchc.size() - 1; i++) {

                dpoint t = rchc.elementAt(i);
                dpoint t2 = rchc.elementAt(i + 1);
                g.drawLine((int) t.x, (int) t.y, (int) t2.x, (int) t2.y);

            }
        } else if (rchc.size() == 2) {
            dpoint t = rchc.elementAt(0);
            dpoint t2 = rchc.elementAt(01);
            g.drawLine((int) t.x, (int) t.y, (int) t2.x, (int) t2.y);

        }

    }

    public void this_mouseClicked(MouseEvent e) {

        //insrt some points
        init0();
        dpoint t5 = new dpoint(186.0, 272.0, dpointkey++);
        dpointlist.add(t5);
        dpoint t12 = new dpoint(261.0, 364.0, dpointkey++);
        dpointlist.add(t12);

        dpoint t3 = new dpoint(392.0, 281.0, dpointkey++);
        dpointlist.add(t3);
        dpoint t8 = new dpoint(422.0, 229.0, dpointkey++);
        dpointlist.add(t8);
        /*             */
        /////////////////////////////////////////////////
        /*          dpoint t8 = new dpoint(100.0, 259.0, dpointkey++);
                  dpointlist.add(t8);
                  dpoint t12 = new dpoint(287.0, 349.0, dpointkey++);
                  dpointlist.add(t12);
                  dpoint t3 = new dpoint(434.0, 149.0, dpointkey++);
                  dpointlist.add(t3);
                  dpoint t5 = new dpoint(488.0, 307.0, dpointkey++);
                  dpointlist.add(t5);
         */
        ///////////////////////////////////////////////////////
        /*   dpoint t9 = new dpoint(380, 234, dpointkey++);
           dpointlist.add(t9);
                     dpoint t2 = new dpoint(430.0, 191.0, dpointkey++);
                   dpointlist.add(t2);
                  dpoint t1 = new dpoint(432.0, 249.0, dpointkey++);
                   dpointlist.add(t1);
                   dpoint t11 = new dpoint(440.0, 258.0, dpointkey++);
                   dpointlist.add(t11);
                   dpoint t6 = new dpoint(445.0, 355.0, dpointkey++);
                   dpointlist.add(t6);
                   dpoint t10 = new dpoint(450, 260, dpointkey++);
                   dpointlist.add(t10);
                   dpoint t4 = new dpoint(477.0, 289.0, dpointkey++);
                   dpointlist.add(t4);
         dpoint t7 = new dpoint(485, 230, dpointkey++); ///350 200//432   230
                   dpointlist.add(t7);

                   dpoint t13 = new dpoint(350, 350, dpointkey++);
                   dpointlist.add(t13);
         */
        //comlete the insert points
        //  init0();
        /*     initexcdpoint();
            clicknum = clicknum + 1;
            double x = e.getX();
            double y = e.getY();
            dpoint t = new dpoint(x, y, dpointkey++);
            dpointlist.add(t);
            System.out.println("第 " + clicknum + " 点坐标 : " + x + ",   " + y);
         */

        double[] a = createarray(dpointlist);
        int l = 0;
        int r = a.length - 1;
        dpointsort(dpointlist, a, l, r);

        construct(edgelist, dpointlist, vpointlist, rchc);
        //     System.out.println(t9.dpointedges.size());
        /*
              for (int i = 0; i < t3.dpointedges.size(); i++) {
                  edge t = t3.dpointedges.elementAt(i);
         System.out.println("a点  : " + t.a.x + "  " + t.a.y + "  to b 点 : " +
                                     t.b.x + "  " + t.b.y);
              }
         */
        repaint();

    }

    public void construct(Vector<edge> edgelist, Vector<dpoint> dpointlist,
            Vector<vpoint> vpointlist, Vector<dpoint> rchc) {
        for (int i = 0; i < dpointlist.size(); i++) {
            if (i == 0) {

            } else if (i == 1) {
                construct1(edgelist, dpointlist, vpointlist, rchc);
            } else if (i == 2) {
                initdpoint();
                dpoint dtemp = dpointlist.elementAt(2);
                construct2(edgelist, dpointlist, vpointlist, rchc, dtemp, i);
                constructrchc(rchc, dtemp);

            } else if (i > 2 && i != index0) {
                //        System.out.println("第i 个点 ：" + (i + 1));
                dpoint dtemp = dpointlist.elementAt(i);
                construct3(edgelist, dpointlist, vpointlist, dtemp, i);
                constructrchc(rchc, dtemp);
            } else if (i == index0) {
                //        System.out.println("第i 个点 ：" + (i + 1));
                dpoint dtemp = dpointlist.elementAt(i);
                construct3(edgelist, dpointlist, vpointlist, dtemp, i);
                constructrchc(rchc, dtemp);

            }

        }
    }

    public void kernerl3(Vector<edge> edgelist, dpoint dop, dpoint xop,
            dpoint dtemp,
            vpoint vop, edge t, int index) { //position ==1 interpointnum==1

        ///mend the old edge

        forbackxopdop(dop, xop, dtemp, t, vop);

        vpoint a = t.a;
        vpoint b = t.b;
        double xk;

        //create the first edge 锐角对应的边
        xk = (dop.x + dtemp.x) / 2;
        double yk = (dop.y + dtemp.y) / 2;
        double sk = -(dop.x - dtemp.x) / (dop.y - dtemp.y);
        vpoint pre0;

        if (yk + sk * ( -unlimit - xk) > max) {

            pre0 = new vpoint(((max - yk) / sk) + xk, max, vpointkey++);
        } else if (yk + sk * ( -unlimit - xk) < -max) {
            pre0 = new vpoint((( -max - yk) / sk) + xk, -max, vpointkey++);
        }

        else {
            pre0 = new vpoint( -unlimit, yk + sk * ( -unlimit - xk), vpointkey++);
        }
        vpoint preunlimit;
        if (yk + sk * (unlimit - xk) > max) {
            preunlimit = new vpoint(((max - yk) / sk) + xk, max, vpointkey++);
        } else if (yk + sk * (unlimit - xk) < -max) {
            preunlimit = new vpoint((( -max - yk) / sk) + xk, -max, vpointkey++);
        } else {
            preunlimit = new vpoint(unlimit, yk + sk * (unlimit - xk),
                                    vpointkey++);
        }
        if (xk < vop.x & vop.x > pre0.x || xk < pre0.x & xk > vop.x) {
            edge temp = new edge();
            temp.a = pre0;
            temp.b = vop;
            temp.op1 = dop;
            temp.op2 = dtemp;
            edgelist.add(temp);
            dop.dpointedges.add(temp);
            dtemp.dpointedges.add(temp);
            removeedge(edgelist, dop, temp.a, temp.b);
        } else {
            edge temp = new edge();
            temp.a = preunlimit;
            temp.b = vop;
            temp.op1 = dop;
            temp.op2 = dtemp;
            edgelist.add(temp);
            dop.dpointedges.add(temp);
            dtemp.dpointedges.add(temp);
            removeedge(edgelist, dop, temp.a, temp.b);

        }

        //create the second edge 钝角对应的边

        Vector<edge> edgestore = new Vector<edge>();
        Vector<vpoint> vpointstore = new Vector<vpoint>();
        xk = (dtemp.x + xop.x) / 2;
        yk = (xop.y + dtemp.y) / 2;
        sk = -(xop.x - dtemp.x) / (xop.y - dtemp.y);

        if (yk + sk * ( -unlimit - xk) > max) {

            pre0 = new vpoint(((max - yk) / sk) + xk, max, vpointkey++);
        } else if (yk + sk * ( -unlimit - xk) < -max) {
            pre0 = new vpoint((( -max - yk) / sk) + xk, -max, vpointkey++);
        }

        else {
            pre0 = new vpoint( -unlimit, yk + sk * ( -unlimit - xk), vpointkey++);
        }

        if (yk + sk * (unlimit - xk) > max) {
            preunlimit = new vpoint(((max - yk) / sk) + xk, max, vpointkey++);
        } else if (yk + sk * (unlimit - xk) < -max) {
            preunlimit = new vpoint((( -max - yk) / sk) + xk, -max, vpointkey++);
        } else {
            preunlimit = new vpoint(unlimit, yk + sk * (unlimit - xk),
                                    vpointkey++);
        }
        edge temp = new edge();
        if (xk < vop.x & xk > pre0.x || xk < pre0.x & xk > vop.x) {

            temp.a = preunlimit;
            temp.b = vop;
            temp.op1 = xop;
            temp.op2 = dtemp;
        } else {

            temp.a = pre0;
            temp.b = vop;
            temp.op1 = xop;
            temp.op2 = dtemp;

        }

        for (int i = 0; i < xop.dpointedges.size(); i++) {
            edge tk = xop.dpointedges.elementAt(i);
            a = tk.a;
            b = tk.b;
            double sks = (b.y - a.y) / (b.x - a.x);
            double x = (yk - a.y - sk * xk + sks * a.x) / (sks - sk);
            if (x >= a.x - det & x <= b.x + det ||
                x >= b.x - det & x <= a.x + det) {
                double y = yk + sk * (x - xk);
                vpoint vopk = new vpoint(x, y, vpointkey++);
                vpointstore.add(vopk);
                edgestore.add(tk);
            }

        }

        if (vpointstore.size() == 1) {

            edgelist.add(temp);
            xop.dpointedges.add(temp);
            dtemp.dpointedges.add(temp);
            removeedge(edgelist, xop, temp.a, temp.b);

        } else if (vpointstore.size() == 2) {

            kernerl5(edgestore, vpointstore, temp, edgelist, dop, xop, dtemp,
                     vop, t, index);

        }

    }


    public void kernerl5(Vector<edge> edgestore, Vector<vpoint> vpointstore,
            edge temp, Vector<edge> edgelist, dpoint dop, dpoint xop,
            dpoint dtemp, vpoint vop, edge t, int index) { //position is 1  first inter point ==1 but rhe next interpoint is 2
        int hero = 0;
        vpoint exvop = new vpoint();
        edge ext = new edge();
        if ((temp.op1 == xop & temp.op2 == dtemp) ||
            (temp.op1 == dtemp & temp.op2 == xop)) {
            hero = 2;
        } else if ((temp.op1 == dop & temp.op2 == dtemp) ||
                   (temp.op1 == dtemp & temp.op2 == dop)) {
            hero = 1;
        }
        if (hero == 1) {
            temp.a = vpointstore.elementAt(0);
            temp.b = vpointstore.elementAt(1);

            temp.op1 = dop; //处理半成品边为dop 和dtemp的
            temp.op2 = dtemp;
            edgelist.add(temp);
            dtemp.dpointedges.add(temp);
            dop.dpointedges.add(temp); //remove edges??

            removeedge(edgelist, dop, temp.a, temp.b);

            if (vop.brother(vpointstore.elementAt(0), det)) {

                vop = vpointstore.elementAt(1);
                t = edgestore.elementAt(1);
                exvop = vpointstore.elementAt(1);
                ext = edgestore.elementAt(1);
            } else {
                vop = vpointstore.elementAt(0);
                t = edgestore.elementAt(0);
                exvop = vpointstore.elementAt(0);
                ext = edgestore.elementAt(0);
            }

            if (t.op1 == dop) {

                xop = t.op2;
            } else {

                xop = t.op1;
            }

        } else if (hero == 2) { //
            temp.a = vpointstore.elementAt(0);
            temp.b = vpointstore.elementAt(1);

            temp.op1 = xop; //处理半成品边为dop 和dtemp的
            temp.op2 = dtemp;
            edgelist.add(temp);
            dtemp.dpointedges.add(temp);
            xop.dpointedges.add(temp); //remove edges??

            removeedge(edgelist, xop, temp.a, temp.b);

            if (vop.brother(vpointstore.elementAt(0), det)) {