polygondx.java

实现二维基本图元直线段生成的基本算法（DDA

package graphics0;
import java.awt.*;
import java.util.*;
import java.awt.image.*;
import javax.swing.Timer;
/**
 * <p>Title: computer graphics </p>
 * <p>Description: homeworks</p>
 * <p>Copyright: Copyright (c) 2004 </p>
 * <p>Company: shu</p>
 * @author dxf
 * @version 1.0
 */
class Edge {
  int ymax;       //边的上端点y坐标;
  float x;        //初值为边下端点的x坐标，AEL中为当前扫描线与边的交点的X坐标;
  float deltax;   //边的斜率的倒数；

  public Edge() {
  }

  public Edge(int y,float x0,float d) {
    ymax = y;
    x =x0;
    deltax =d;
  }
}

public class PolygonDx extends Object2D {
  Vector vPoint,vAel;
  Vector []vEdge;
  int ymax,ymin;

////////////////////////////////////////////////////////////////
  ///以x的正序插入vAel]中,nEdge 是新边
  void insertEdge(Vector v,Edge nEdge) {
    int i,isize,iEdge;
    Edge e1,tmp;
    isize = v.size();
    if (0 ==isize) {
      v.add(nEdge);
    }
    else {
      //isize -= 1;
      //e1 = (Edge)(v.elementAt(0));
      i = 0;
      while (i<isize){
        if (nEdge.x>=((Edge)(v.elementAt(i))).x)
          i++;
        else
           break;
      }
      v.add(i,nEdge);

    }
  }
//////////////////////////////////////////////////////////////
  //求出下一个非水平线的y值
  int  yNext(int k) {
    int j,isize;
    isize = vPoint.size();
    if (k>(isize-2))       j=0;
    else    j = k+1;

    Point p0,p1;
    p0 = (Point)(vPoint.elementAt(k));
    p1 = (Point)(vPoint.elementAt(j));
    while (p0.y==p1.y){
      if (j > (isize - 2))
        j = -1;
      else
        j++;

      p1 = (Point)(vPoint.elementAt(j));
    }

    return (p1.y);

  }
////////////////////////////////////////////////////////
  //生成一条初始边
  void makeEdge(Point lower,Point upper,int yComp){
    float d ,x;
    int ymax;
    d = (float)(upper.x - lower.x)/(float)(upper.y - lower.y);
    x = lower.x;
    if (upper.y<yComp)
      ymax = upper.y -1;
    else
      ymax = upper.y;

    insertEdge(vEdge[lower.y],new Edge(ymax,x,d));
    System.out.println("edge="+lower.y+",edge's ymax="+ymax+",x="+x+
                         ",d="+d);
  }
///////////////////////////////////////////////////////////////////////
//建初始的边数组
  void buildNet() {
    int i,j,tmp,isize,yprev;
    float delta;
    Point v1 = new Point(0,0),v2= new Point(0,0);
    /////////////////////////////////////////
    //求y的最大最小值
   // ymax = ((Point)vPoint.elementAt(0)).y;
    ymin = ymax = 0;
    isize = vPoint.size();

    for (i=0;i<isize;i++) {//求出多边形中y的最大值
      tmp = ((Point)vPoint.elementAt(i)).y;
      if (tmp>ymax) ymax = tmp; // if (tmp<ymin) ymin = tmp;
      System.out.println("i="+i+",x="+((Point)vPoint.elementAt(i)).x+
                         ",y="+((Point)vPoint.elementAt(i)).y);
    }
    vEdge = new Vector[ymax+1];// - ymin +1];
    //生成矢量数组
    for (i = 0;i<vEdge.length ;i++)
       vEdge[i]=new Vector();

    ///////////////////////////////////////////
    //生成net表
    yprev = ((Point)vPoint.elementAt(isize -2)).y;
    v1 = (Point)vPoint.elementAt(isize-1);
    for (i=0;i<isize;i++) {
      v2 = (Point)vPoint.elementAt(i);
      if (v1.y!=v2.y) {
        if (v1.y<v2.y)
          makeEdge(v1,v2,yNext(i));
        else
          makeEdge(v2,v1,yprev);
      }
      yprev = v1.y;v1=v2;

    }
    //////////////////////////////////////////////////
  }
///////////////////////////////////////////////////////////////////////////
  //建活性边
  void buildAEL(int scan){
    System.out.println("scan="+scan);
    int isize = vEdge[scan].size();
    if (isize>0){
    //  isize -=1;
      for (int i=0;i<isize;i++){
        insertEdge(vAel,(Edge)(vEdge[scan].elementAt(i)));
      }
    }
  }
///////////////////////////////////////////////////////////////////////////
  //删建活性边
  void updateActiveList(int scan){
    Edge e0;
    int isize = vAel.size();
    if (isize>0){
      int i = 0;
      while (i<vAel.size()){
        e0 = (Edge)(vAel.elementAt(i));
       if (scan >=e0.ymax) {
         vAel.remove(i);
       }
       else {
         e0.x = e0.x+e0.deltax;
         i++;
       }
      }
    }
  }
///////////////////////////////////////////////////////////////////////////
  //活性边重新排序
  void restoreActiveList(){
    Edge e0;
    Vector v0 = new Vector();
    int isize = vAel.size();
    if (isize>0){
     // isize -= 1;
      for(int i = 0;i<isize;i++){
        e0 =(Edge)(vAel.elementAt(i));
        insertEdge(v0,e0);
      }

      vAel.clear();
      for(int i = 0;i<isize;i++){
        vAel.add(v0.elementAt(i));
      }
    }

  }

////////////////////////////////////////////////////////////////////////////
  //用一条直线填充一条活性边中的两个交点之间的区域
  void fill(int scan, Graphics2D g){
    int x0,x1;
    int isize = vAel.size();
    if (isize>0){
    //  isize -=1;
      for (int i = 0; i < isize; i+=2) {
        x0 = Math.round(((Edge)(vAel.elementAt(i))).x);
        if ((i+1)<isize) {
          x1 = Math.round(((Edge)(vAel.elementAt(i+1))).x);
          if (x0>x1) {
            x0-=1;x1+=1;
          }
          else{
            x0+=1;x1-=1;
          }

          g.drawLine(x0,scan,x1,scan);
        }

      }
    }

  }
////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////
    public void polyfill(Color bc, Graphics2D g) {
      g.setColor(bc);
      vAel = new Vector();
      buildNet();
      for (int i=0;i<ymax;i++) {
        buildAEL(i);
        System.out.println("vAel.size="+vAel.size());
        if (vAel.size()>0){
          fill(i,g);
          updateActiveList(i);
          restoreActiveList();
        }
      }

  }

///////////////////////////////////////////////////////////////////////////////
  void drawDemo(Graphics Canvas){

  }

  void draw(Graphics Canvas){
    Canvas.setColor(ForeColor);
    int l,j= vPoint.size();
    Point s,p;
    for ( int i=0;i<j;i++){
      s = (Point)(vPoint.elementAt(i));
      l= i+1;
      if (l==j) l=0;
      p = (Point)(vPoint.elementAt(l));
      Canvas.drawLine(s.x,s.y,p.x,p.y);
    }

  }

  boolean IsInside(Point p0) {
    return (true);
  };

///////////////////////////////////////////////////////////////////////////////
  public PolygonDx() {
    vPoint = new Vector();
  }

  public PolygonDx(Vector vp) {
    vPoint = new Vector();
    int j= vp.size() - 1;
    Point tmp;

    for ( int i=0;i<j;i++){
      tmp = new Point((Point)vp.get(i));
      vPoint.add(tmp);
      System.out.println("vPoint x="+tmp.x+",y="+tmp.y);