delaunaytriangulation.java

来自「经典的货郎担问题解决办法」· Java 代码 · 共 1,032 行 · 第 1/3 页

      cEdge temp;
      temp = e.next;
      if ( e.adjface[0].visible && e.adjface[1].visible )
        /* e interior: mark for deletion. */
        e.delete = REMOVED;
      else if ( e.adjface[0].visible || e.adjface[1].visible ) 
        /* e border: make a new face. */
        e.newface = MakeConeFace( e, p );
      e = temp;
    } while ( e != elist.head );
    return true;
  }
  
  /*---------------------------------------------------------------------
    VolumeSign returns the sign of the volume of the tetrahedron determined 
    by f and p.  VolumeSign is +1 iff p is on the negative side of f,
    where the positive side is determined by the rh-rule.  So the volume 
    is positive if the ccw normal to f points outside the tetrahedron.
    The final fewer-multiplications form is due to Robert Fraczkiewicz.
    ---------------------------------------------------------------------*/
  private int  VolumeSign( cFace f, cVertex p )
  {
    double  vol;
    int     voli = 0;
    double  ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz;
    double  bxdx, bydy, bzdz, cxdx, cydy, czdz;
    
    ax = f.vertex[0].v.x;
    ay = f.vertex[0].v.y;
    az = f.vertex[0].v.z;
    bx = f.vertex[1].v.x;
    by = f.vertex[1].v.y;
    bz = f.vertex[1].v.z;
    cx = f.vertex[2].v.x;
    cy = f.vertex[2].v.y;
    cz = f.vertex[2].v.z;
    dx = p.v.x;
    dy = p.v.y;
    dz = p.v.z;
    
    bxdx = bx-dx;
    bydy = by-dy;
    bzdz = bz-dz;
    cxdx = cx-dx;
    cydy = cy-dy;
    czdz = cz-dz;
    vol  = (az-dz) * (bxdx*cydy - bydy*cxdx)
      + (ay-dy) * (bzdz*cxdx - bxdx*czdz)
      + (ax-dx) * (bydy*czdz - bzdz*cydy);
    
    if ( debug )
      System.out.println("Face="+f+"; Vertex="+p.vnum
                         +": vol(int) = "+voli+", vol(double) = "+vol);
    
    /* The volume should be an integer. */
    if      ( vol > 0.5 )   return  1;
    else if ( vol < -0.5 )  return -1;
    else                    return  0;
  }
  /*---------------------------------------------------------------------*/
  private int  Volumei( cFace f, cVertex p )
  {
    int    vol;
    int    ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz;
    int    bxdx, bydy, bzdz, cxdx, cydy, czdz;
    double vold;
    int    i;
    
    ax = f.vertex[0].v.x;
    ay = f.vertex[0].v.y;
    az = f.vertex[0].v.z;
    bx = f.vertex[1].v.x;
    by = f.vertex[1].v.y;
    bz = f.vertex[1].v.z;
    cx = f.vertex[2].v.x;
    cy = f.vertex[2].v.y;
    cz = f.vertex[2].v.z;
    dx = p.v.x;
    dy = p.v.y;
    dz = p.v.z;
   
    bxdx=bx-dx;
    bydy=by-dy;
    bzdz=bz-dz;
    cxdx=cx-dx;
    cydy=cy-dy;
    czdz=cz-dz;
    vol =   (az-dz)*(bxdx*cydy-bydy*cxdx)
      + (ay-dy)*(bzdz*cxdx-bxdx*czdz)
      + (ax-dx)*(bydy*czdz-bzdz*cydy);
    
    return vol;
  }             
  
  /*---------------------------------------------------------------------
    Volumed is the same as VolumeSign but computed with doubles.  For 
    protection against overflow.
    ---------------------------------------------------------------------*/
  private double        Volumed( cFace f, cVertex p )
  {
    double  vol;
    double  ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz;
    double  bxdx, bydy, bzdz, cxdx, cydy, czdz;
    
    ax = f.vertex[0].v.x;
    ay = f.vertex[0].v.y;
    az = f.vertex[0].v.z;
    bx = f.vertex[1].v.x;
    by = f.vertex[1].v.y;
    bz = f.vertex[1].v.z;
    cx = f.vertex[2].v.x;
    cy = f.vertex[2].v.y;
    cz = f.vertex[2].v.z;
    dx = p.v.x;
    dy = p.v.y;
    dz = p.v.z;
    
    bxdx=bx-dx;
    bydy=by-dy;
    bzdz=bz-dz;
    cxdx=cx-dx;
    cydy=cy-dy;
    czdz=cz-dz;
    vol = (az-dz)*(bxdx*cydy-bydy*cxdx)
      + (ay-dy)*(bzdz*cxdx-bxdx*czdz)
      + (ax-dx)*(bydy*czdz-bzdz*cydy);
    
    return vol;
  }
  
  /*---------------------------------------------------------------------
    MakeConeFace makes a new face and two new edges between the 
    edge and the point that are passed to it. It returns a pointer to
    the new face.
    ---------------------------------------------------------------------*/
  private cFace MakeConeFace( cEdge e, cVertex p )
  {
    cEdge  new_edge[] = new cEdge[2];
    cFace  new_face;
    int           i, j;
    
    /* Make two new edges (if don't already exist). */
    for ( i = 0; i < 2; ++i ) { 
      /* If the edge exists, copy it into new_edge. */
      new_edge[i] = e.endpts[i].duplicate;
      if ( new_edge[i] == null ) {
        /* Otherwise (duplicate is null), MakeNullEdge. */
        new_edge[i] = elist.MakeNullEdge();
        new_edge[i].endpts[0] = e.endpts[i];
        new_edge[i].endpts[1] = p;
        e.endpts[i].duplicate = new_edge[i];
      }
    }
    
    /* Make the new face. */
    new_face = flist.MakeNullFace();   
    new_face.edge[0] = e;
    new_face.edge[1] = new_edge[0];
    new_face.edge[2] = new_edge[1];
    MakeCcw( new_face, e, p ); 
    
    /* Set the adjacent face pointers. */
    for ( i=0; i < 2; ++i )
      for ( j=0; j < 2; ++j )  
        /* Only one NULL link should be set to new_face. */
        if ( new_edge[i].adjface[j] == null ) {
          new_edge[i].adjface[j] = new_face;
          break;
        }
        
    return new_face;
  }

  /*---------------------------------------------------------------------
    MakeCcw puts the vertices in the face structure in counterclock wise 
    order.  We want to store the vertices in the same 
    order as in the visible face.  The third vertex is always p.
    ---------------------------------------------------------------------*/
  private void  MakeCcw( cFace f, cEdge e, cVertex p )
  {
    cFace  fv;                  /* The visible face adjacent to e */
    int    i;                   /* Index of e.endpoint[0] in fv. */
    cEdge  s = new cEdge();     /* Temporary, for swapping */
    
    if  ( e.adjface[0].visible )      
      fv = e.adjface[0];
    else fv = e.adjface[1];
    
    /* Set vertex[0] & [1] of f to have the same orientation
       as do the corresponding vertices of fv. */ 
    for ( i=0; fv.vertex[i] != e.endpts[0]; ++i )
      ;
    /* Orient f the same as fv. */
    if ( fv.vertex[ (i+1) % 3 ] != e.endpts[1] ) {
      f.vertex[0] = e.endpts[1];  
      f.vertex[1] = e.endpts[0];    
    }
    else {                               
      f.vertex[0] = e.endpts[0];   
      f.vertex[1] = e.endpts[1];      
      Swap( s, f.edge[1], f.edge[2] );
    }
    /* This swap is tricky. e is edge[0]. edge[1] is based on endpt[0],
       edge[2] on endpt[1].  So if e is oriented "forwards," we
       need to move edge[1] to follow [0], because it precedes. */
    
    f.vertex[2] = p;
  }

  /*---------------------------------------------------------------------
    MakeFace creates a new face structure from three vertices (in ccw
    order).  It returns a pointer to the face.
    ---------------------------------------------------------------------*/
  private cFace   MakeFace( cVertex v0, cVertex v1, cVertex v2, cFace fold )
  {
    cFace  f;
    cEdge  e0, e1, e2;
    
    /* Create edges of the initial triangle. */
    if( fold == null ) {
      e0 = elist.MakeNullEdge();
      e1 = elist.MakeNullEdge();
      e2 = elist.MakeNullEdge();
    }
    else { /* Copy from fold, in reverse order. */
      e0 = fold.edge[2];
      e1 = fold.edge[1];
      e2 = fold.edge[0];
    }
    e0.endpts[0] = v0;              e0.endpts[1] = v1;
    e1.endpts[0] = v1;              e1.endpts[1] = v2;
    e2.endpts[0] = v2;              e2.endpts[1] = v0;
    
    /* Create face for triangle. */
    f = flist.MakeNullFace();
    f.edge[0]   = e0;  f.edge[1]   = e1; f.edge[2]   = e2;
    f.vertex[0] = v0;  f.vertex[1] = v1; f.vertex[2] = v2;
    
    /* Link edges to face. */
    e0.adjface[0] = e1.adjface[0] = e2.adjface[0] = f;
    
    return f;
  }
  
  /*---------------------------------------------------------------------
    CleanUp goes through each data structure list and clears all
    flags and NULLs out some pointers.  The order of processing
    (edges, faces, vertices) is important.
    ---------------------------------------------------------------------*/
  private void  CleanUp()
  {
    CleanEdges();
    CleanFaces();
    CleanVertices();
  }
  
  /*---------------------------------------------------------------------
    CleanEdges runs through the edge list and cleans up the structure.
    If there is a newface then it will put that face in place of the 
    visible face and NULL out newface. It also deletes so marked edges.
    ---------------------------------------------------------------------*/
  private void  CleanEdges()
  {
    cEdge  e;   /* Primary index into edge list. */
    cEdge  t;   /* Temporary edge pointer. */
    
    /* Integrate the newface's into the data structure. */
    /* Check every edge. */
    e = elist.head;
    do {
      if ( e.newface != null ) { 
        if ( e.adjface[0].visible )
            e.adjface[0] = e.newface; 
        else    e.adjface[1] = e.newface;
        e.newface = null;
      }
      e = e.next;
    } while ( e != elist.head );
    
    /* Delete any edges marked for deletion. */
    while ( elist.head != null && elist.head.delete ) { 
      e = elist.head;
      elist.Delete( e );
    }
    e = elist.head.next;
    do {
      if ( e.delete ) {
        t = e;
        e = e.next;
        elist.Delete( t );
      }
      else e = e.next;
    } while ( e != elist.head );
  }
  
  /*---------------------------------------------------------------------
    CleanFaces runs through the face list and deletes any face marked visible.
    ---------------------------------------------------------------------*/
  private void  CleanFaces()
  {
    cFace  f;   /* Primary pointer into face list. */
    cFace  t;   /* Temporary pointer, for deleting. */
    
    
    while ( flist.head != null && flist.head.visible ) { 
      f = flist.head;
      flist.Delete( f );
    }
    f = flist.head.next;
    do {
      if ( f.visible ) {
        t = f;
        f = f.next;
        flist.Delete( t );
      }
      else f = f.next;
    } while ( f != flist.head );
  }
  
  /*---------------------------------------------------------------------
    CleanVertices runs through the vertex list and deletes the 
    vertices that are marked as processed but are not incident to any 
    undeleted edges. 
    ---------------------------------------------------------------------*/
  private void  CleanVertices()
  {
    cEdge    e;
    cVertex  v, t;
    
    /* Mark all vertices incident to some undeleted edge as on the hull. */
    e = elist.head;
    do {
      e.endpts[0].onhull = e.endpts[1].onhull = ONHULL;
      e = e.next;
    } while (e != elist.head);
    
    /* Delete all vertices that have been processed but
       are not on the hull. */
    while ( list.head != null&& list.head.mark && !list.head.onhull ) { 
      v = list.head;
      list.Delete( v );
    }
    v = list.head.next;
    do {