delaunaytriangulation.java

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

/*--------------------------------------------------------------------------
 * Class DelaunayTriangulation
 *
 * Computes DelaunayTriangulation of points in 2D
 * This code is described in "Computational Geometry in C",
 * It is not written to be comprehensible without the
 * explanation in that book.
 *---------------------------------------------------------------------------*/
package com.well.www.user.xanthian.java.seeders;
import java.awt.*;

public class DelaunayTriangulation {
  /* Define flags */
  private static final boolean ONHULL = true;
  private static final boolean REMOVED = true;
  private static final boolean VISIBLE = true;
  private static final boolean PROCESSED = true;
  private static final int SAFE = 1000000;

  private boolean debug;
  private boolean check;
  boolean toDraw;
  private cVertexList list;
  private cEdgeList elist;
  private cFaceList flist;

  DelaunayTriangulation()
  {
    this.list = list;
    elist = new cEdgeList();
    flist = new cFaceList();
    debug = toDraw = false;
    check = false;
  }

  public void Start(cVertexList listOld)
  {
    this.list = new cVertexList();
    listOld.ListCopy(this.list);
    ReadVertices();
    if (DoubleTriangle()) {
      toDraw = true;
      ConstructHull();
      LowerFaces();
      Print();
    }
  }

  public void ClearDelaunay()
  {
    elist.ClearEdgeList();
    flist.ClearFaceList();
    check = debug = toDraw = false;
  }

  /*---------------------------------------------------------------------
    ReadVertices: Raises vertices to 3D and checks their coordinates.  
    ---------------------------------------------------------------------*/
  public void ReadVertices()
  {
    int vnum = 0;
    cVertex v = list.head;
    do {
      v.ResetVertex3D();
      v.vnum = vnum++;
      if (( Math.abs(v.v.x) > SAFE ) || ( Math.abs(v.v.y) > SAFE ) 
          || ( Math.abs(v.v.z) > SAFE ) ) {
        System.out.println("Coordinate of vertex below might be too large...");
        v.PrintVertex3D(vnum);
      }
      v = v.next;
    } while ( v != list.head );
  }

  private void LowerFaces()
  {
    cFace f = flist.head;
    /*int   z;*/
    int   Flower = 0;   /* Total number of lower faces. */
    
    do {
      /*z = Normz( f );
        if ( z < 0 ) {*/
      if ( Normz( f ) < 0 ) {
        Flower++;
        f.lower = true;
        System.out.println("lower face indices: "+f.vertex[0].vnum +", " +
                           f.vertex[1].vnum +", "+f.vertex[2].vnum );
      }
      else f.lower = false;
      f = f.next;
    } while ( f != flist.head );
    System.out.println("A total of "+Flower+" lower faces identified.");
  }
  
  /*---------------------------------------------------------------------
    Print: Prints out the vertices and the faces.  Uses the vnum indices 
    corresponding to the order in which the vertices were input.
    ---------------------------------------------------------------------*/
  private void  Print()
  {
    /* Pointers to vertices, edges, faces. */
    cVertex  v;
    cEdge    e;
    cFace    f;
    int xmin, ymin, xmax, ymax;
    int a[] = new int[3], b[] = new int[3];  /*used to compute normal vector */
    /* Counters for Euler's formula. */
    int         V = 0, E = 0 , F = 0;
    /* Note: lowercase==pointer, uppercase==counter. */
    
    /*-- find X min & max --*/
    v = list.head;
    xmin = xmax = v.v.x;
    do {
      if( v.v.x > xmax ) xmax = v.v.x;
      else
        if( v.v.x < xmin ) xmin = v.v.x;
      v = v.next;
    } while ( v != list.head );
    
    /*-- find Y min & max --*/
    v = list.head;
    ymin = ymax = v.v.y;
    do {
      if( v.v.y > ymax ) ymax = v.v.y;
      else
        if( v.v.y < ymin ) ymin = v.v.y;
      v = v.next;
    } while ( v != list.head );
    
    
    /* Vertices. */
    v = list.head;
    do {                                 
      if( v.mark ) V++;           
      v = v.next;
    } while ( v != list.head );
 
    System.out.println("\nVertices:\tV = "+ V);
    System.out.println("index:\tx\ty\tz");
    do {                                 
      System.out.println( v.vnum+":\t"+v.v.x+"\t"+v.v.y+"\t"+v.v.z+"");
      System.out.println("newpath");
      System.out.println(v.v.x+"\t"+v.v.y+" 2 0 360 arc");
      System.out.println("closepath stroke\n");
      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 )
        {
          System.out.println("vnums:  "+f.vertex[0].vnum+"  "
                             +f.vertex[1].vnum+"  "+f.vertex[2].vnum);
          System.out.println("newpath");
          System.out.println(f.vertex[0].v.x+"\t"+f.vertex[0].v.y+"\tmoveto"); 
          System.out.println(f.vertex[1].v.x+"\t"+f.vertex[1].v.y+"\tlineto");
          System.out.println(f.vertex[2].v.x+"\t"+f.vertex[2].v.y+"\tlineto");
          System.out.println("\n");
        }
      f = f.next;
    } while ( f != flist.head );
    
    /* prints a list of all faces */
    System.out.println("List of all faces:");
    System.out.println("\tv0\tv1\tv2\t(vertex indices)");
    do {
      System.out.println("\t"+f.vertex[0].vnum+
                         "\t"+f.vertex[1].vnum+
                         "\t"+f.vertex[2].vnum);
      f = f.next;
    } while ( f != flist.head );
    
    /* Edges. */        
    e = elist.head;
    do {
      E++;
      e = e.next;
    } while ( e != elist.head );
    System.out.println("\nEdges:\tE = "+E);
    /* Edges not printed out (but easily added). */
  
    check = true;
    CheckEuler( V, E, F );
  }

  /*---------------------------------------------------------------------
    SubVec:  Computes a - b and puts it into c.
    ---------------------------------------------------------------------*/
  private void    SubVec( int a[], int b[], int c[])
  {
    int  i;
    
    for( i=0; i < 2; i++ )
      c[i] = a[i] - b[i]; 
  }
  
  /*---------------------------------------------------------------------
    DoubleTriangle builds the initial double triangle.  It first finds 3 
    noncollinear points and makes two faces out of them, in opposite order.
    It then finds a fourth point that is not coplanar with that face.  The  
    vertices are stored in the face structure in counterclockwise order so 
    that the volume between the face and the point is negative. Lastly, the
    3 newfaces to the fourth point are constructed and the data structures
    are cleaned up. 
    ---------------------------------------------------------------------*/
  private boolean DoubleTriangle()
  {
    cVertex  v0, v1, v2, v3, t;
    cFace    f0, f1 = null;
    cEdge    e0, e1, e2, s;
    int      vol;
    
    
    /* Find 3 non-Collinear points. */
    v0 = list.head;
    while ( Collinear( v0, v0.next, v0.next.next ) )
      if ( ( v0 = v0.next ) == list.head ) {
        System.out.println("DoubleTriangle:  All points are Collinear!");
        return false;
      }
    v1 = v0.next;
    v2 = v1.next;
    
    /* Mark the vertices as processed. */
    v0.mark = PROCESSED;
    v1.mark = PROCESSED;
    v2.mark = PROCESSED;
    
    /* Create the two "twin" faces. */
    f0 = MakeFace( v0, v1, v2, f1 );
    f1 = MakeFace( v2, v1, v0, f0 );
    
    /* Link adjacent face fields. */
    f0.edge[0].adjface[1] = f1;
    f0.edge[1].adjface[1] = f1;
    f0.edge[2].adjface[1] = f1;
    f1.edge[0].adjface[1] = f0;
    f1.edge[1].adjface[1] = f0;
    f1.edge[2].adjface[1] = f0;
    
    /* Find a fourth, non-coplanar point to form tetrahedron. */
    v3 = v2.next;
    vol = VolumeSign( f0, v3 );
    while ( vol == 0 ) {
      if ( ( v3 = v3.next ) == v0 ) { 
        System.out.println("DoubleTriangle:  All points are coplanar!");
        return false;
      }
      vol = VolumeSign( f0, v3 );
    }
  
    /* Insure that v3 will be the first added. */
    list.head = v3;
    if ( debug ) {
      System.out.println("DoubleTriangle: finished. Head repositioned at v3.");
      PrintOut( list.head );
    }
    return true;
  }

  
  /*---------------------------------------------------------------------
    ConstructHull adds the vertices to the hull one at a time.  The hull
    vertices are those in the list marked as onhull.
    ---------------------------------------------------------------------*/
  private void  ConstructHull()
  {
    cVertex  v, vnext;
    int      vol;
    boolean     changed;        /* T if addition changes hull; not used. */
    
    v = list.head;
    do {
      vnext = v.next;
      if ( !v.mark ) {
        v.mark = PROCESSED;
        changed = AddOne( v );
        CleanUp();
        
        if ( check ) {
          System.out.println("ConstrHull:After Add of "+v.vnum+"& Cleanup:");
          Checks();
        }
        if ( debug )
          PrintOut( v );
      }
      v = vnext;
    } while ( v != list.head );
  }
  
  /*---------------------------------------------------------------------
    AddOne is passed a vertex.  It first determines all faces visible from 
    that point.  If none are visible then the point is marked as not 
    onhull.  Next is a loop over edges.  If both faces adjacent to an edge
    are visible, then the edge is marked for deletion.  If just one of the
    adjacent faces is visible then a new face is constructed.
    ---------------------------------------------------------------------*/
  
  private  boolean      AddOne( cVertex p )
  {
    cFace   f; 
    cEdge   e;
    int     vol;
    boolean vis = false;
    
    if ( debug ) {
      System.out.println("AddOne: starting to add v"+p.vnum);
      PrintOut( list.head );
    }
    
    /* Mark faces visible from p. */
    f = flist.head;
    do {
      vol = VolumeSign( f, p );
      if (debug) 
        System.out.println("faddr: "+f+"   paddr: "+p+"   Vol = "+vol);
      if ( vol < 0 ) {
        f.visible = VISIBLE;  
        vis = true;                      
      }
      f = f.next;
    } while ( f != flist.head );
    
    /* If no faces are visible from p, then p is inside the hull. */
    if ( !vis ) {
      p.onhull = !ONHULL;  
      return false; 
    }
    
    /* Mark edges in interior of visible region for deletion.
       Erect a newface based on each border edge. */
    e = elist.head;
    do {