dvr.java

一个新的voronoi算法实现

package dv;

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

public class dvr 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 = 8;
    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.fillOval(308, 275, 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) {
        /*    init0();
            dpoint t5 = new dpoint(143.0, 293.0, dpointkey++);
            dpointlist.add(t5);
            dpoint t6 = new dpoint(173.0, 219.0, dpointkey++);
            dpointlist.add(t6);
            dpoint t3 = new dpoint(177.0, 356.0, dpointkey++);
            dpointlist.add(t3);
            dpoint t11 = new dpoint(212.0, 413.0, dpointkey++);
            dpointlist.add(t11);
         dpoint t7 = new dpoint(240.0, 275.0, dpointkey++); ///350 200//432   230
            dpointlist.add(t7);
            dpoint t10 = new dpoint(256.0, 312.0, dpointkey++);
            dpointlist.add(t10);
            dpoint t2 = new dpoint(284.0, 405.0, dpointkey++);
            dpointlist.add(t2);
            dpoint t8 = new dpoint(306.0, 313.0, dpointkey++);
            dpointlist.add(t8);
            dpoint t4 = new dpoint(308.0, 276.0, dpointkey++);
            dpointlist.add(t4);
            dpoint t1 = new dpoint(328.0, 322.0, dpointkey++);
            dpointlist.add(t1);
            dpoint t13 = new dpoint(350, 350, dpointkey++);
            dpointlist.add(t13);
            dpoint t12 = new dpoint(374.0, 253.0, dpointkey++);
            dpointlist.add(t12);
            dpoint t9 = new dpoint(455.0, 342.0, dpointkey++);
            dpointlist.add(t9);

         */
        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);
        repaint();

    }

    public void initexcdpoint() {
        vpointlist.removeAllElements();
        vpointliststore.removeAllElements();
        edgelist.removeAllElements();

        rchc.removeAllElements();

    }

    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 construct3(Vector<edge> edgelist, Vector<dpoint> dpointlist,
            Vector<vpoint> vpointlist, dpoint dtemp, int i) {
        Vector<dpoint> position = findpos(rchc, dtemp);
        int index = i;
        if (position.size() == 1) {

            dpoint dop = position.elementAt(0);
            Vector<vpoint> vpointstore = new Vector<vpoint>();
            Vector<edge> edgestore = new Vector<edge>();
            base(edgestore, vpointstore, dtemp, dop, index);
            if (vpointstore.size() == 1) {
                edge t = edgestore.elementAt(0);
                //处理完一条相交边
                t.a = shortlen(dop, dtemp, t);
                t.b = vpointstore.elementAt(0);
                //处理完新生成的边
                vpoint vop = vpointstore.elementAt(0);
                createnewedgedtempdop(edgelist, dtemp, dop, vop); //不仅产生而其把dtemp的op1  op2 都设置完毕并且加入到了edgelist

                //从交点继续做中分线
                if (t.op1 == dop) {
                    dop = t.op2;
                } else if (t.op2 == dop) {
                    dop = t.op1;
                }

                base(edgestore, vpointstore, dtemp, dop, index);
                if (vpointstore.size() == 1) {
                    vop = vpointstore.elementAt(0);
                    createnewedgedtempdop(edgelist, dtemp, dop, vop);
                } else if (vpointstore.size() == 2) {
                    //产生了连续的剪切  此处传入了变量t 记录进入的那条边  每次处理的都是dop dtemp
                    kernerl(edgestore, vpointstore, edgelist, dop, dtemp, t,
                            vop, index);

                }

            } else if (vpointstore.size() == 2) {
                //处理完vpointstore的两个元素组成的边
                edge tk = new edge();
                tk.a = vpointstore.elementAt(0);
                tk.b = vpointstore.elementAt(1);
                tk.op1 = dop;
                tk.op2 = dtemp;
                edgelist.add(tk);
                dtemp.dpointedges.add(tk);
                dop.dpointedges.add(tk);
                removeedge(edgelist, dop, tk.a, tk.b);
                //处理上相交边
                edge tup = edgestore.elementAt(0);
                tup.a = shortlen(dop, dtemp, tup);
                tup.b = vpointstore.elementAt(0);
                edge tdown = edgestore.elementAt(1);
                tdown.a = shortlen(dop, dtemp, tdown);
                tdown.b = vpointstore.elementAt(1);

                //处理上面的一部分
                vpoint vop = vpointstore.elementAt(0);
                edge t = tup;
                if (tup.op1 == dop) {
                    dop = tup.op2;
                } else if (tup.op2 == dop) {
                    dop = tup.op1;
                }
                base(edgestore, vpointstore, dtemp, dop, index);
                if (vpointstore.size() == 1) {
                    createnewedgedtempdop(edgelist, dtemp, dop, vop);
                } else {
                    kernerl(edgestore, vpointstore, edgelist, dop, dtemp, t,
                            vop, index);
                }

                //处理下相交边


                //处理下面的一部分
                vop = null;
                vop = new vpoint();
                t = null;
                t = new edge();
                if (tdown.op1 == position.elementAt(0)) {
                    dop = tdown.op2;
                } else if (tdown.op2 == position.elementAt(0)) {
                    dop = tdown.op1;
                }
                vop = tdown.b;
                t = tdown;
                base(edgestore, vpointstore, dtemp, dop, index);
                if (vpointstore.size() == 1) {
                    createnewedgedtempdop(edgelist, dtemp, dop, vop);
                } else {
                    kernerl(edgestore, vpointstore, edgelist, dop, dtemp, t,
                            vop, index);
                }

            }

        } else if (position.size() == 2) { //所处voronoi的生成点为一条边
            dpoint up = position.elementAt(0);
            dpoint down = position.elementAt(1);
            if (up.y < down.y) {

            } else {
                up = position.elementAt(1);
                down = position.elementAt(0);
            }
            //资源的准备
            Vector<edge> edgestore = new Vector<edge>();
            Vector<vpoint> vpointstore = new Vector<vpoint>();

            //处理up点完全模拟只有一个点的情况但是不涉及到down点
            dpoint dop = up;
            base(edgestore, vpointstore, dtemp, dop, index);
            if (vpointstore.size() == 1) {
                //处理旧边 产生新边  继续产生新边 且要注意如果变换后的dop为down是不处理留在down 处理就行了
                edge t = edgestore.elementAt(0);
//处理完一条相交边
                t.a = shortlen(dop, dtemp, t);
                t.b = vpointstore.elementAt(0);
//处理完新生成的边
                vpoint vop = vpointstore.elementAt(0);
                createnewedgedtempdop(edgelist, dtemp, dop, vop); //不仅产生而其把dtemp的op1  op2 都设置完毕并且加入到了edgelist
//////////////////////////////////////////若要完整需要down点的处理
                //down 点开始处理:
                //从交点继续做中分线
                if (t.op1 == dop) {
                    dop = t.op2;
                } else if (t.op2 == dop) {
                    dop = t.op1;
                }

                base(edgestore, vpointstore, dtemp, dop, index);
                if (vpointstore.size() == 1) {
                    vop = vpointstore.elementAt(0);
                    createnewedgedtempdop(edgelist, dtemp, dop, vop);
                } else if (vpointstore.size() == 2) {
                    //产生了连续的剪切  此处传入了变量t 记录进入的那条边  每次处理的都是dop dtemp
                    kernerl(edgestore, vpointstore, edgelist, dop, dtemp, t,
                            vop, index);

                }

            } else if (vpointstore.size() == 2) {
                //处理此次生成的边  处理上边一系列生成问题
                edge tk = new edge();
                tk.a = vpointstore.elementAt(0);
                tk.b = vpointstore.elementAt(1);
                tk.op1 = dop;
                tk.op2 = dtemp;
                edgelist.add(tk);
                dtemp.dpointedges.add(tk);
                dop.dpointedges.add(tk);
                removeedge(edgelist, dop, tk.a, tk.b);

                int minup = 0;
                int maxdown = 1;
                if (vpointstore.elementAt(0).y < vpointstore.elementAt(1).y) {
                    minup = 0;
                    maxdown = 1;
                } else if (vpointstore.elementAt(1).y < vpointstore.elementAt(0).
                           y) {
                    minup = 1;
                    maxdown = 0;
                }
                //处理上面的一系列问题

                dop = up;
                edge tup = edgestore.elementAt(minup);
                tup.a = shortlen(dop, dtemp, tup);
                tup.b = vpointstore.elementAt(minup);
                edge tdown = edgestore.elementAt(maxdown);
                tdown.a = shortlen(dop, dtemp, tdown);
                tdown.b = vpointstore.elementAt(maxdown);

                //处理上面的一部分  //对down点的下边没有处理不要忘记了

                vpoint vop = vpointstore.elementAt(minup);
                edge t = tup;
                if (tup.op1 == dop & tup.op2 != down) {
                    dop = tup.op2;
                } else if (tup.op2 == dop & tup.op1 != down) {
                    dop = tup.op1;
                }
                if (dop != down) {
                    base(edgestore, vpointstore, dtemp, dop, index);
                    if (vpointstore.size() == 1) {
                        createnewedgedtempdop(edgelist, dtemp, dop, vop);
                    } else if (vpointstore.size() == 2) {
                        kernerl(edgestore, vpointstore, edgelist, dop, dtemp, t,
                                vop, index);
                    }
                }
                //it's time to 处理down点


                //处理下面的一部分  //对down点的下边没有处理不要忘记了
                vop = null;
                t = null;
//                vop = vpointstore.elementAt(maxdown);
                vop = tdown.b;
                t = tdown;
                if (t.op1 == up & t.op2 != up) {
                    dop = t.op2;
                } else if (t.op2 == up & t.op1 != up) {
                    dop = t.op1;
                }

                if (dop != up) {
                    base(edgestore, vpointstore, dtemp, dop, index);
                    if (vpointstore.size() == 1) {
                        createnewedgedtempdop(edgelist, dtemp, dop, vop);
                    } else if (vpointstore.size() == 2) {
                        //产生了连续的剪切  此处传入了变量t 记录进入的那条边  每次处理的都是dop dtemp
                        kernerl(edgestore, vpointstore, edgelist, dop, dtemp, t,
                                vop, index);
                    }

                }

            }

        }

    }

    public void kernerl(Vector<edge> edgestore, Vector<vpoint> vpointstore,