dv.java~1046~

一个新的voronoi算法实现

                //此时temp代表的是新生成的边 but 还有一条旧边没有处理 此旧边的对应op1  op2 为dtemp xop
                edge et = edgestore.elementAt(0);

                a = et.a;
                b = et.b;

                if (a.x < b.x) {
                    et.a = a;
                    et.b = vop;
                } else {
                    et.a = vop;
                    et.b = b;
                }

                edgelist.add(temp);
                xop.dpointedges.add(temp);
                dtemp.dpointedges.add(temp);

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

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

                a = ext.a;
                b = ext.b;
                if (a.x < b.x) {
                    ext.a = a;
                    ext.b = exvop;
                } else {
                    ext.b = b;
                    ext.a = exvop;
                }

                if (hero == 1) {
                    dop = xop;
                }

                kernerlshdow5(edgestore, vpointstore, temp, edgelist, dop, xop,
                              dtemp,
                              vop, t, index, down);
            }

        }

    }

    public void kernerl6create(dpoint dop, dpoint xop, dpoint dtemp, vpoint vop) {
        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 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++);
        }

        edge temp = new edge();
        forbackdtempdop(dop, xop, dtemp, temp, vop); //dtemp  dop的处理
//        System.out.println("  temp 的顶点 : "+temp.a.x+"  "+temp.a.y+"  "+temp.b.x +"  "+temp.b.y);
        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 void forbackdtempdop(dpoint dop, dpoint xop, dpoint dtemp,
                                edge t,
                                vpoint vop) {
        double flag = 0; //钝角为1 锐角为-1
        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);
        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;

        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 (lxopdtemp >= (ldopdtemp + lxopdop) ||
            ldopdtemp >= (lxopdtemp + lxopdop) ||
            (lxopdop >= ldopdtemp + lxopdtemp)) {
            flag = 1;

        } else {
            flag = -1;
        }
        if (flag == 1) {
            if (ldopdtemp >= lxopdop + lxopdtemp) {
                if (xk >= vop.x & xk <= pre0.x || xk <= vop.x & xk >= pre0.x) {

                    t.a = preunlimit;
                    t.b = vop;
                } else {
                    t.a = vop;
                    t.b = pre0;
                }
            } else {
                if (xk >= pre0.x & xk <= vop.x || xk <= pre0.x & xk >= vop.x) {
                    t.a = pre0;
                    t.b = vop;
                } else {
                    t.a = vop;
                    t.b = preunlimit;
                }

            }

        }

        else {
            if (xk >= pre0.x & xk <= vop.x || xk <= pre0.x & xk >= vop.x) {
                t.a = pre0;
                t.b = vop;
            } else {
                t.a = vop;
                t.b = preunlimit;
            }

        }

    }

    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;
    }

    public void kernerl4(Vector<edge> edgelist, dpoint dop, dpoint xop,
            dpoint dtemp, vpoint vop, edge t, int index) {
        //mend the old edge
        forbackxopdop(dop, xop, dtemp, t, vop);
        vpoint a = t.a;
        vpoint b = t.b;

        double xk = (xop.x + dtemp.x) / 2;
        double yk = (xop.y + dtemp.y) / 2;
        double sk = -(xop.x - dtemp.x) / (xop.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++);
        }

        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;

        }

        Vector<edge> edgestore = new Vector<edge>();
        Vector<vpoint> vpointstore = new Vector<vpoint>();
        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) {
            temp.op1 = dtemp;
            temp.op2 = xop;
            edgelist.add(temp);
            xop.dpointedges.add(temp);
            dtemp.dpointedges.add(temp);
            removeedge(edgelist, xop, temp.a, temp.b);

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

            temp = null;
            temp = new edge();
            temp.op1 = xop;
            temp.op2 = dtemp;
            kernerl5(edgestore, vpointstore, temp, edgelist, dop, xop,
                     dtemp,
                     vop, t, index);

        }

    }

    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) {
                d.dpointedges.remove(t);
                edgelist.remove(t);
                i = i;
            } else if (sk > 0 & flag1 < -det & flag2 < -det) {
                d.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);

        dedge bc = new dedge();
        bc.a = b;
        bc.b = c;
        bc.length = Math.sqrt(lbc);

        dedge ac = new dedge();
        ac.a = a;
        ac.b = c;