delaunaytriangulation.java

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

      if ( v.mark && !v.onhull ) {    
        t = v; 
        v = v.next;
        list.Delete( t );
      }
      else v = v.next;
    } while ( v != list.head );
    
    /* Reset flags. */
    v = list.head;
    do {
      v.duplicate = null; 
      v.onhull = !ONHULL; 
      v = v.next;
    } while ( v != list.head );
  }
  
  /*---------------------------------------------------------------------
    Collinear checks to see if the three points given are collinear,
    by checking to see if each element of the cross product is zero.
    ---------------------------------------------------------------------*/
  private boolean Collinear( cVertex a, cVertex b, cVertex c )
  {
    return 
      ( c.v.z - a.v.z ) * ( b.v.y - a.v.y ) -
      ( b.v.z - a.v.z ) * ( c.v.y - a.v.y ) == 0
      && ( b.v.z - a.v.z ) * ( c.v.x - a.v.x ) -
      ( b.v.x - a.v.x ) * ( c.v.z - a.v.z ) == 0
      && ( b.v.x - a.v.x ) * ( c.v.y - a.v.y ) -
      ( b.v.y - a.v.y ) * ( c.v.x - a.v.x ) == 0  ;
  }
  
  /*---------------------------------------------------------------------
    Computes the z-coordinate of the vector normal to face f.
    ---------------------------------------------------------------------*/
  private int   Normz( cFace f )
  {
    cVertex a, b, c;
    /*double ba0, ca1, ba1, ca0,z;*/
    
    a = f.vertex[0];
    b = f.vertex[1];
    c = f.vertex[2];
    
    /*
      ba0 = ( b.v.x - a.v.x );
      ca1 = ( c.v.y - a.v.y );
      ba1 = ( b.v.y - a.v.y );
      ca0 = ( c.v.x - a.v.x );
      
      z = ba0 * ca1 - ba1 * ca0; 
      System.out.println("Normz = %lf=%g\n", z,z);
      if      ( z > 0.0 )  return  1;
      else if ( z < 0.0 )  return -1;
      else                 return  0;
    */
    return 
      ( b.v.x - a.v.x ) * ( c.v.y - a.v.y ) -
      ( b.v.y - a.v.y ) * ( c.v.x - a.v.x );
  }

  /*---------------------------------------------------------------------
    Consistency runs through the edge list and checks that all
    adjacent faces have their endpoints in opposite order.  This verifies
    that the vertices are in counterclockwise order.
    ---------------------------------------------------------------------*/
  private void  Consistency()
  {
    cEdge  e;
    int    i, j;
    
    e = elist.head;
    
    do {
      /* find index of endpoint[0] in adjacent face[0] */
      for ( i = 0; e.adjface[0].vertex[i] != e.endpts[0]; ++i )
        ;
      
      /* find index of endpoint[0] in adjacent face[1] */
      for ( j = 0; e.adjface[1].vertex[j] != e.endpts[0]; ++j )
        ;
      
      /* check if the endpoints occur in opposite order */
      if ( !( e.adjface[0].vertex[ (i+1) % 3 ] ==
              e.adjface[1].vertex[ (j+2) % 3 ] ||
              e.adjface[0].vertex[ (i+2) % 3 ] ==
              e.adjface[1].vertex[ (j+1) % 3 ] )  )
        break;
      e = e.next;
      
    } while ( e != elist.head );
    
    if ( e != elist.head )
      System.out.println("Checks: edges are NOT consistent.");
    else
      System.out.println("Checks: edges consistent.");
  }
  
  /*---------------------------------------------------------------------
    Convexity checks that the volume between every face and every
    point is negative.  This shows that each point is inside every face
    and therefore the hull is convex.
    ---------------------------------------------------------------------*/
  private void  Convexity()
  {
   cFace    f;
    cVertex  v;
    int               vol;
    
    f = flist.head;
    
    do {
      v = list.head;
      do {
        if ( v.mark ) {
          vol = VolumeSign( f, v );
          if ( vol < 0 )
            break;
        }
        v = v.next;
      } while ( v != list.head );
      
      f = f.next;
      
    } while ( f != flist.head );
    
    if ( f != flist.head )
      System.out.println("Checks: NOT convex.");
    else if ( check ) 
      System.out.println("Checks: convex.");
  }
  
  /*---------------------------------------------------------------------
    CheckEuler checks Euler's relation, as well as its implications when
    all faces are known to be triangles.  Only prints positive information
    when debug is true, but always prints negative information.
    ---------------------------------------------------------------------*/
  private void  CheckEuler( int V, int E, int F )
  {
    if ( check )
      System.out.print("Checks: V, E, F = "+V+", "+E+", "+F+"\n");
    
    if ( (V - E + F) != 2 )
      System.out.print(" Checks: V-E+F != 2\n");
    else if ( check )
      System.out.print(" V-E+F = 2\t\n");
    
    
    if ( F != (2 * V - 4) )
      System.out.print(" Checks: F=" +F+ " != 2V-4=" +(2*V-4)+ "; V=" +V);
    
    else if ( check ) 
      System.out.println ("F = 2V-4\t");
    
    if ( (2 * E) != (3 * F) )
      System.out.println(" Checks: 2E="+2*E+" != 3F="+3*F+"; E="+E+", F="+F);
    else if ( check ) 
      System.out.println(" 2E = 3F");
  }
  
  /*-------------------------------------------------------------------*/
  private void  Checks()
  {
    cVertex  v;
    cEdge    e;
    cFace    f;
    int            V = 0, E = 0 , F = 0;
    
    Consistency();
    Convexity();
    
    v = list.head;
    if ( v != null )
      do {
        if (v.mark) V++;
        v = v.next;
      } while ( v != list.head );
    
    e = elist.head;
    if ( e != null )
      do {
        E++;
        e = e.next;
      } while ( e != elist.head );
    
    f = flist.head;
    if ( f != null )
      do {
        F++;
        f  = f.next;
      } while ( f  != flist.head );
    CheckEuler( V, E, F );
  }
  
  
  /*===================================================================
    These functions are used whenever the debug flag is set.
    They print out the entire contents of each data structure.  
    Printing is to standard error.  To grab the output in a file in the csh, 
    use this:
    chull < i.file >&! o.file
    =====================================================================*/
  /*-------------------------------------------------------------------*/
  private void  PrintOut( cVertex v )
  {
    System.out.println("Head vertex "+v.vnum+" =  "+v+"\t:");
    PrintVertices();
    PrintEdges();
    PrintFaces();
  }
  
  /*-------------------------------------------------------------------*/
  private void  PrintVertices()
  {
    cVertex  temp;
    
    temp = list.head;
    System.out.println ("Vertex List");
    if (list.head != null) do {
      System.out.print("  addr "+list.head+"\t");
      System.out.print("  vnum "+list.head.vnum);
      System.out.println("   ("+list.head.v.x+","
                         +list.head.v.y+","
                         +list.head.v.z+")");
      System.out.println("   active:"+list.head.onhull);
      System.out.println("   dup:"+list.head.duplicate );
      System.out.println("   mark:\n"+ list.head.mark );
      list.head = list.head.next;
    } while ( list.head != temp );
    
  }
  
  /*-------------------------------------------------------------------*/
  private void PrintEdges()
  {
    cEdge  temp;
    int           i;
    
    temp = elist.head;
    System.out.println ("Edge List");
    if (elist.head != null) do {
      System.out.print("  addr: "+elist.head+"\t");
      System.out.print("adj: ");
      for (i=0; i<2; ++i) 
        System.out.print( elist.head.adjface[i] );
      System.out.print("  endpts:");
      for (i=0; i<2; ++i) 
        System.out.print(elist.head.endpts[i].vnum);
      System.out.print( "  del:"+elist.head.delete+"\n");
      elist.head = elist.head.next; 
    } while (elist.head != temp );
    
  }
  
  /*-------------------------------------------------------------------*/
  private void  PrintFaces()
  {
    int           i;
    cFace  temp;
    
    temp = flist.head;
    System.out.print ( "Face List\n");
    if (flist.head != null) do {
      System.out.print( "  addr: "+flist.head+"\t");
      System.out.print( "  edges:");
      for( i=0; i<3; ++i )
        System.out.print( flist.head.edge[i] );
      System.out.print( "  vert:");
      for ( i=0; i<3; ++i)
        System.out.print( flist.head.vertex[i].vnum );
      System.out.print( "  vis: "+flist.head.visible+"\n");
      flist.head= flist.head.next;
    } while ( flist.head != temp );  
  }
  
  private void Swap(cEdge t, cEdge x, cEdge y)
  {
    t = x;
    x = y;
    y = t;
  } 

  /*---------------------------------------------------------------------
    DrawDelaunayTri: Draws the vertices and the faces.  Uses the vnum indices 
    corresponding to the order in which the vertices were input.
    ---------------------------------------------------------------------*/
  public void   DrawDelaunayTri(Graphics g, int w, int h)
  {
    /* Pointers to vertices, edges, faces. */
    cVertex  v;
    cEdge    e;
    cFace    f;
    /* Counters for Euler's formula. */
    int         V = 0, E = 0 , F = 0;
    /* Note: lowercase==pointer, uppercase==counter. */
    
    /* Vertices. */
    v = list.head;
    do {                                 
      if( v.mark ) V++;           
      v = v.next;
    } while ( v != list.head );
 
    /* Faces. */
    /* visible faces are printed as PS output */
    f = flist.head;
    do {
      ++F;                              
      f  = f .next;
    } while ( f  != flist.head );
    System.out.println("\nFaces:\tF = "+F);
    System.out.println("Visible faces only:");
    do {           
      /* Print face only if it is lower */
      if ( f. lower )
      {
        g.setColor(Color.blue);
        if(flist.n >= 2) {
          g.drawLine(f.vertex[0].v.x, f.vertex[0].v.y,
                     f.vertex[1].v.x, f.vertex[1].v.y);
          g.drawLine(f.vertex[1].v.x, f.vertex[1].v.y,
                     f.vertex[2].v.x, f.vertex[2].v.y);
          g.drawLine(f.vertex[2].v.x, f.vertex[2].v.y,
                     f.vertex[0].v.x, f.vertex[0].v.y);
        }
      }
      f = f.next;
    } while ( f != flist.head );    

    System.out.println("\nVertices:\tV = "+ V);
    System.out.println("index:\tx\ty\tz");
    do {
      g.setColor(Color.black);
      Font font = new Font("Helvetica", Font.PLAIN, 12);
      g.setFont(font);
      g.drawString(Integer.toString(v.vnum), 
                   v.v.x - (int)1.5*w, v.v.y - (int)1.5*h);
      g.setColor(Color.blue);
      g.fillOval(v.v.x - (int)(w/2), v.v.y - (int)(h/2), w, h);
      v = v.next;
    } while ( v != list.head );  
  }
}