dvrk.java~3~

一个新的voronoi算法实现

            Vector<edge> edgelist, dpoint dop, dpoint dtemp, edge t, vpoint vop,
            int index) { //dop 就是现在关联的点就是要dtemp dop 的中分线
        //是生成一条新边并加入edgelist  处理一条旧边   生成一天新边 并判断是否满足
        //两个点就递归调用 一个点就生成完毕


        //生成一条新边
        edge temp = new edge();
        temp.a = vpointstore.elementAt(0);
        temp.b = vpointstore.elementAt(1);
        temp.op1 = dtemp;
        temp.op2 = dop;
        edgelist.add(temp);
        dtemp.dpointedges.add(temp);
        dop.dpointedges.add(temp);
        removeedge(edgelist, dop, temp.a, temp.b);
        ///////处理一条旧边
        if (vop.brother(vpointstore.elementAt(0), det)) {
            vop = vpointstore.elementAt(1);
            t = edgestore.elementAt(1);
        } else if (vop.brother(vpointstore.elementAt(1), det)) {
            vop = vpointstore.elementAt(0);
            t = edgestore.elementAt(0);
        } //将交点和边处理为当前要处理的边
        t.a = shortlen(dop, dtemp, t);
        t.b = vop;
        //////////
        //生成一条新边
        if (t.op1 == dop) {
            dop = t.op2;
        } else {
            dop = t.op1;
        }
        base(edgestore, vpointstore, dtemp, dop, index);
        if (vpointstore.size() == 1) {
            //在create中已经加入了此边不需要处理 自然结束就可以
            createnewedgedtempdop(edgelist, dtemp, dop, vop);
        } else if (vpointstore.size() == 2) {
            //准备好初始条件

            kernerl(edgestore, vpointstore, edgelist, dop, dtemp, t,
                    vop, index);

        }

    }


    public void createnewedgedtempdop(Vector<edge> edgelist, dpoint dtemp,
            dpoint dop, vpoint vop) {
        edge temp = new edge();
        double xk = (dtemp.x + dop.x) / 2;
        double yk = (dtemp.y + dop.y) / 2;
        double sk = -(dtemp.x - dop.x) / (dtemp.y - dop.y);
        vpoint pre0;
        vpoint preunlimit;
        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++);
        }

        if (convex(dop, vop, pre0) == 1) {
            temp.a = pre0;
            temp.b = vop;
        } else if (convex(dop, vop, preunlimit) == 1) {
            temp.a = preunlimit;
            temp.b = vop;
        } else if (convex(dtemp, vop, pre0) == 1) {
            temp.a = pre0;
            temp.b = vop;
        } else if (convex(dtemp, vop, preunlimit) == 1) {
            temp.a = preunlimit;
            temp.b = vop;
        }

        else {

            for (int i = 0; i < dop.dpointedges.size(); i++) {
                edge t = dop.dpointedges.elementAt(i);
                dpoint xop = new dpoint();
                if (t.op1 == dop & t.op2 != dtemp) {
                    xop = t.op2;
                } else if (t.op2 == dop & t.op1 != dtemp) {
                    xop = t.op1;
                }

                dpoint a = dtemp;
                dpoint b = dop;
                dpoint c = xop;
                double xa = a.x;
                double ya = a.y;
                double xb = b.x;
                double yb = b.y;
                double xc = c.x;
                double yc = c.y;

                double c1 = (xa * xa + ya * ya - xb * xb - yb * yb) / 2;
                double c2 = (xa * xa + ya * ya - xc * xc - yc * yc) / 2;
                double xo = (c1 * (ya - yc) - c2 * (ya - yb)) /
                            ((xa - xb) * (ya - yc) - (xa - xc) * (ya - yb));
                double yo = (c1 * (xa - xc) - c2 * (xa - xb)) /
                            ((ya - yb) * (xa - xc) - (ya - yc) * (xa - xb));

                vpoint v = new vpoint(xo, yo);
                if (v.brother(vop, det)) {
                    temp = anglebigorsmall(dtemp, dop, xop, vop, pre0,
                                           preunlimit);
                    break;
                } else {

                }

            }
        }

        temp.op1 = dtemp;
        temp.op2 = dop;
        edgelist.add(temp);
        dtemp.dpointedges.add(temp);
        dop.dpointedges.add(temp);
        removeedge(edgelist, dop, temp.a, temp.b);

    }

    public edge anglebigorsmall(dpoint dtemp, dpoint dop, dpoint xop,
                                vpoint vop, vpoint pre0, vpoint preunlimit) {
        edge temp = new edge();
        double lxopdtemp = Math.pow(dtemp.x - xop.x, 2) +
                           Math.pow(dtemp.y - xop.y, 2);
        double ldopdtemp = Math.pow(dop.x - dtemp.x, 2) +
                           Math.pow(dop.y - dtemp.y, 2);
        double lxopdop = Math.pow(xop.x - dop.x, 2) + Math.pow(dop.y - xop.y, 2);

        if (ldopdtemp >= lxopdop + lxopdtemp) {
            if (inter(vop, pre0, dop, dtemp)) {
                temp.a = vop;
                temp.b = preunlimit;
            } else if (inter(vop, preunlimit, dop, dtemp)) {
                temp.a = vop;
                temp.b = pre0;
            }
        } else {
            if (inter(vop, pre0, dop, dtemp)) {
                temp.a = vop;
                temp.b = pre0;
            } else if (inter(vop, preunlimit, dop, dtemp)) {
                temp.a = vop;
                temp.b = preunlimit;
            }

        }
        return temp;

    }

    public int convex(dpoint dop, vpoint vop, vpoint test) {
        int flag = -1;
        double max = 9000000;
        vpoint vopf = new vpoint(max, max);
        vpoint vopf2 = new vpoint(max, max);
        for (int i = 0; i < dop.dpointedges.size(); i++) {
            edge t = dop.dpointedges.elementAt(i);
            if (t.a.brother(vop, det)) {
                vopf = t.b;
            } else if (t.b.brother(vop, det)) {
                vopf = t.a;
            }
        }
        for (int i = 0; i < dop.dpointedges.size(); i++) {
            edge t = dop.dpointedges.elementAt(i);
            if (t.a.brother(vopf, det) & !t.b.brother(vop, det)) {
                vopf2 = t.b;
            } else if (t.b.brother(vopf, det) & !t.a.brother(vop, det)) {
                vopf2 = t.a;
            }
        }
        if (!(vopf.x == max || vopf2.x == max)) {
            double f2fv = turnlr(vopf2, vopf, vop);
            double fvtest = turnlr(vopf, vop, test);
            if (f2fv * fvtest >= 0) {
                flag = 1;
            } else if (f2fv * fvtest < 0) {
                flag = 2;
            }

        } else {
            flag = 3;
        }
        return flag;
    }

    public double turnlr(vpoint v1, vpoint v2, vpoint v3) { //左转 右转
        double flag0 = 0; //-1 left   1 right
        double ax = v1.x;
        double ay = v1.y;
        double bx = v2.x;
        double by = v2.y;
        double cx = v3.x;
        double cy = v3.y;
        flag0 = ((bx - ax) * (cy - by) - (by - ay) * (cx - bx));

        return flag0;
    }

    public vpoint shortlen(dpoint dop, dpoint dtemp, edge t) {
        double xk = (dop.x + dtemp.x) / 2;
        double yk = (dop.y + dtemp.y) / 2;
        double sk = -(dop.x - dtemp.x) / (dop.y - dtemp.y);
        vpoint a = t.a;
        vpoint b = t.b;
        double flaga = a.y - yk - sk * (a.x - xk);
        double flagb = b.y - yk - sk * (b.x - xk);
        if (sk > 0) {
            if (flaga > 0) {
                return a;
            } else {
                return b;
            }
        } else {
            if (flaga < 0) {
                return a;
            } else {
                return b;
            }
        }
    }

    public double len(dpoint dop, vpoint v) {
        double len;
        double lenx = Math.pow(dop.x - v.x, 2);
        double leny = Math.pow(dop.y - v.y, 2);
        len = Math.sqrt(lenx + leny);
        return len;
    }


    public void base(Vector<edge> edgestore, Vector<vpoint> vpointstore,
            dpoint dtemp, dpoint dop, int index) { //记录如果产生的新币，则生成的新边，与dop的边界相交的点和线
        edgestore.removeAllElements();
        vpointstore.removeAllElements();

        double xk = (dop.x + dtemp.x) / 2;
        double yk = (dop.y + dtemp.y) / 2;
        double sk = -(dtemp.x - dop.x) / (dtemp.y - dop.y);

        for (int i = 0; i < dop.dpointedges.size(); i++) {
            edge t = dop.dpointedges.elementAt(i);
            vpoint a = t.a;
            vpoint b = t.b;
            double sks = (b.y - a.y) / (b.x - a.x);

            double x = (yk + sks * a.x - a.y - sk * xk) / (sks - sk); //不能处理垂直的情况

            if (x >= a.x - det & x <= b.x + det ||
                x >= b.x - det & x <= a.x + det) {
                double y = a.y + sks * (x - a.x);
                vpoint vop = new vpoint(x, y, vpointkey++);
                vpointstore.add(vop);
                edgestore.add(t);

            }

        }

    }

    public void initdpoint() { //remove   except the dpointlist
        vpointlist.removeAllElements();
        vpointliststore.removeAllElements();
        edgelist.removeAllElements();
        for (int i = 0; i < dpointlist.size(); i++) {
            dpoint t = dpointlist.elementAt(i);
            t.dpointedges.removeAllElements();
        }

    }

    public double dis(dpoint d1, dpoint d2, vpoint v3) {
        double distance = 0;
        double A = d1.y - d2.y;
        double B = d1.x - d2.x;
        double C = d1.y * (d1.x - d2.x) - d1.x * (d1.y - d2.y);
        distance = Math.abs(A * v3.x + B * v3.y + C) /
                   Math.sqrt(Math.pow(A, 2) + Math.pow(B, 2));
        return distance;
    }

    public void removeedge(Vector<edge> edgelist, dpoint d, vpoint up,
            vpoint down) {

        Vector<edge> smalledgelist = d.dpointedges;
        double ax;
        double ay;
        double bx;
        double by;
        double sk = (up.y - down.y) / (up.x - down.x);
        double flag1, flag2;
        edge t;
        int i = 0;
        while (true) {
            t = smalledgelist.elementAt(i);
            ax = t.a.x;
            ay = t.a.y;
            bx = t.b.x;
            by = t.b.y;

            flag1 = ay - up.y - sk * (ax - up.x);
            flag2 = by - up.y - sk * (bx - up.x);
            if (sk < 0 & flag1 > det & flag2 > det) {
                t.op1.dpointedges.remove(t);
                t.op2.dpointedges.remove(t);
                edgelist.remove(t);

                i = i;
            } else if (sk > 0 & flag1 < -det & flag2 < -det) {
                t.op1.dpointedges.remove(t);
                t.op2.dpointedges.remove(t);
                edgelist.remove(t);
                i = i;

            } else {
                i = i + 1;
            }
            if (i == smalledgelist.size()) {
                break;
            }
        }

    }

    public void construct2(Vector<edge> edgelist,
            Vector<dpoint> dpointlist,
            Vector<vpoint> vpointlist, Vector<dpoint> rchc,
            dpoint dtemp,
            int index) {
        dpoint a = dpointlist.elementAt(0);
        dpoint b = dpointlist.elementAt(1);
        dpoint c = dpointlist.elementAt(2);
        vpoint v = new vpoint();
        kernerl2(edgelist, a, b, c, v);
    }

    public void kernerl2(Vector<edge> edgelist, dpoint a, dpoint b,
            dpoint c,
            vpoint v) {

        double xa = a.x;
        double ya = a.y;
        double xb = b.x;
        double yb = b.y;
        double xc = c.x;
        double yc = c.y;

        double c1 = (xa * xa + ya * ya - xb * xb - yb * yb) / 2;
        double c2 = (xa * xa + ya * ya - xc * xc - yc * yc) / 2;
        double xo = (c1 * (ya - yc) - c2 * (ya - yb)) /
                    ((xa - xb) * (ya - yc) - (xa - xc) * (ya - yb));
        double yo = (c1 * (xa - xc) - c2 * (xa - xb)) /
                    ((ya - yb) * (xa - xc) - (ya - yc) * (xa - xb));

        v.x = xo;
        v.y = yo;
        double lab = Math.pow((xb - xa), 2) + Math.pow((yb - ya), 2);
        double lbc = Math.pow((xb - xc), 2) + Math.pow((yb - yc), 2);
        double lac = Math.pow((xa - xc), 2) + Math.pow((ya - yc), 2);

        dedge ab = new dedge();
        ab.a = a;
        ab.b = b;
        ab.length = Math.sqrt(lab);