使用 Sutherland-Hodgman 算法时多边形裁剪不起作用

Question

我正在编写一个程序来创建一个形状像鱼的多边形并用绿色填充它。在 window 内有一些按钮可以移动这条鱼。我只想让 window 内的鱼部分可见，因此我试图实现 Sutherland-Hodgman 算法来执行此操作。

我不确定哪里出错了。我所知道的是，当我接触到 window 的边缘时，我最终会把线转到它们不应该去的地方。

例如：

第一张图是鱼碰到边缘之前，第二张是鱼碰到边缘的时候window:

这是我为实现多边形裁剪的 Sutherland-Hodgman 算法而编写的代码：

int left_most_edge, right_most_edge, scan = 0;
double wxl = 50, wxh = 362, wyl = 246, wyh = 62;
double[][] table = new double[4][200];  //2d array containing: 
                                        //[0][-] -> ymax, [1][-] -> ymin, [2][-] -> dx, [3][-] -> x
double[] px = {100, 150, 200, 210, 215, 205, 215, 210, 200, 150}; //contains all x coord.
double[] py = {125, 100, 120, 110, 115, 125, 135, 140, 130, 150}; //contains all y coord.
double[] xout = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
double[] yout = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int outnum;
double[] lastl = new double[2];
double[] lastr = new double[2];
double[] lastt = new double[2];
double[] lastb = new double[2];
boolean drawAgain = false;

public void clipPolygon(Graphics g, int number_entered_edges) 
{//clips the polygon so only parts that are in the viewing window get filled
    lastl[0] = px[number_entered_edges - 1];
    lastl[1] = py[number_entered_edges - 1];

    lastr[0] = wxl;
    lastb[0] = wxl;
    lastt[0] = wxl;
    lastr[1] = wyl;
    lastb[1] = wyl;
    lastt[1] = wyl;

    outnum = 0;

    for (int i = 0; i < number_entered_edges; i++) 
    {
        clipL(px[i], py[i]);
    }//end for

    outnum = 0;

    for (int i = 0; i < number_entered_edges; i++) 
    {
        clipL(px[i], py[i]);
    }//end for
}//end clipPolygon

public void clipL(double x, double y) 
{//clips from the left
    if ((lastl[0] < wxl && wxl <= x) || (x <= wxl && wxl < lastl[0])) 
    {
        System.out.println("Passed into clipR -> (" + wxl + ", " + ((((y - lastl[1]) * (wxl - x)) / x - lastl[0]) + y) + ")");
        System.out.println(y + " - " + lastl[1] + " * " + "(" + wxl + " - " + x + ") / " + x + " - " + lastl[0] + " + " + y + ")");
        clipR(wxl, ((((y - lastl[1]) * (wxl - x)) / x - lastl[0]) + y));
        drawAgain = true;
    }//end if

    lastl[0] = x;
    lastl[1] = y;

    if (wxl < x)
        clipR(x, y);
}//end clipL

public void clipR(double x, double y)
{//clips from the right
    System.out.println("herro: " + x + ", " + y);
    if ((x <= wxh && wxh < lastr[0]) || (lastr[0] < wxh && wxh <= x)) 
    {
        clipB(wxh, ((((y - lastr[1]) * (wxh - x)) / x - lastr[0]) + y));
        drawAgain = true;
    }//end if

    lastr[0] = x;
    lastr[1] = y;

    if (x < wxh)
        clipB(x, y);
}//end clipR

public void clipB(double x, double y) 
{//clips from the bottom
    if ((lastb[1] < wyl && wyl <= y) || (y <= wyl && wyl < lastb[1]))
    {
        clipT(((((x - lastb[0]) * (wyl - y)) / y - lastb[1]) + x), wyl);
        drawAgain = true;
    }//end if

    lastb[0] = x;
    lastb[1] = y;

    if (wyl > y)
        clipT(x, y);
}//end clipB

public void clipT(double x, double y) 
{//clips from the top
    if ((lastt[1] > wyh && wyh >= y) || y >= wyh && wyh > lastt[1])
    {
        store(((((x - lastt[0]) * (wyh - y)) / y - lastt[1]) + x), wyh);
           drawAgain = true;
    }//end if
    lastt[0] = x;
    lastt[1] = y;

    if (wyh < y)
        store(x, y);
}//end clipT

public void store(double x, double y) 
{//stores the final coordinates after clipping
    xout[outnum] = x;
    yout[outnum] = y;
    outnum++;
}//end store

public void drawMyPolygon(Graphics g) 
{ //draws the polygon
    g.setColor(Color.RED);
    g.drawLine((int) px[0], (int) py[0], (int) px[1], (int) py[1]);
    g.drawLine((int) px[1], (int) py[1], (int) px[2], (int) py[2]);
    g.drawLine((int) px[2], (int) py[2], (int) px[3], (int) py[3]);
    g.drawLine((int) px[3], (int) py[3], (int) px[4], (int) py[4]);
    g.drawLine((int) px[4], (int) py[4], (int) px[5], (int) py[5]);
    g.drawLine((int) px[5], (int) py[5], (int) px[6], (int) py[6]);
    g.drawLine((int) px[6], (int) py[6], (int) px[7], (int) py[7]);
    g.drawLine((int) px[7], (int) py[7], (int) px[8], (int) py[8]);
    g.drawLine((int) px[8], (int) py[8], (int) px[9], (int) py[9]);
    g.drawLine((int) px[9], (int) py[9], (int) px[0], (int) py[0]);
}//end drawMyPolygon

public void drawNewPolygon(Graphics g)
{ //draw a new polygon with the coordinates of the clipped polygon
    g.setColor(Color.RED);
    g.drawLine((int) xout[0], (int) yout[0], (int) xout[1], (int) yout[1]);
    g.drawLine((int) xout[1], (int) yout[1], (int) xout[2], (int) yout[2]);
    g.drawLine((int) xout[2], (int) yout[2], (int) xout[3], (int) yout[3]);
    g.drawLine((int) xout[3], (int) yout[3], (int) xout[4], (int) yout[4]);
    g.drawLine((int) xout[4], (int) yout[4], (int) xout[5], (int) yout[5]);
    g.drawLine((int) xout[5], (int) yout[5], (int) xout[6], (int) yout[6]);
    g.drawLine((int) xout[6], (int) yout[6], (int) xout[7], (int) yout[7]);
    g.drawLine((int) xout[7], (int) yout[7], (int) xout[8], (int) yout[8]);
    g.drawLine((int) xout[8], (int) yout[8], (int) xout[9], (int) yout[9]);
    g.drawLine((int) xout[9], (int) yout[9], (int) xout[0], (int) yout[0]);
    drawAgain = false;
}//end drawNewPolygon

public void drawMyHorizontalLine(Graphics g, int x1, int y, int x2) 
{ //draws the line for filling
    g.setColor(Color.GREEN);
    g.drawLine(x1, y, x2, y);
}//end drawMyHorizontalLine

public void drawWindow(Graphics g) 
{//draws the viewing window
    g.setColor(Color.BLACK);
    g.drawLine((int)wxl, (int)wyh, (int)wxl, (int)wyl);
    g.drawLine((int)wxl, (int)wyh, (int)wxh, (int)wyh);
    g.drawLine((int)wxl, (int)wyl, (int)wxh, (int)wyl);
    g.drawLine((int)wxh, (int)wyh, (int)wxh, (int)wyl);
}//end drawWindow

@Override
public void paint(Graphics g) 
{   
    super.paint(g);

    //draw viewing window
    drawWindow(g);

    //initialize the edge table to all zeroes
    initializeTable();

    //clip the polygon
    clipPolygon(g, 10);

    System.out.println("Coordinates:");
    System.out.println("(" + px[0] + ", " + py[0] + ")");
    System.out.println("(" + px[1] + ", " + py[1] + ")");
    System.out.println("(" + px[2] + ", " + py[2] + ")");
    System.out.println("(" + px[3] + ", " + py[3] + ")");
    System.out.println("(" + px[4] + ", " + py[4] + ")");
    System.out.println("(" + px[5] + ", " + py[5] + ")");
    System.out.println("(" + px[6] + ", " + py[6] + ")");
    System.out.println("(" + px[7] + ", " + py[7] + ")");
    System.out.println("(" + px[8] + ", " + py[8] + ")");
    System.out.println("(" + px[9] + ", " + py[9] + ")");

    System.out.println("\nStored:");
    System.out.println("(" + xout[0] + ", " + yout[0] + ")");
    System.out.println("(" + xout[1] + ", " + yout[1] + ")");
    System.out.println("(" + xout[2] + ", " + yout[2] + ")");
    System.out.println("(" + xout[3] + ", " + yout[3] + ")");
    System.out.println("(" + xout[4] + ", " + yout[4] + ")");
    System.out.println("(" + xout[5] + ", " + yout[5] + ")");
    System.out.println("(" + xout[6] + ", " + yout[6] + ")");
    System.out.println("(" + xout[7] + ", " + yout[7] + ")");
    System.out.println("(" + xout[8] + ", " + yout[8] + ")");
    System.out.println("(" + xout[9] + ", " + yout[9] + ")");

    for (int i = 0; i < xout.length; i++)
        System.out.println("outnum -> " + outnum);

    //draw polygon with red outline
    if (drawAgain)
    {
        fillMyPolygon(g, 10, 10);
        drawNewPolygon(g);
    }//end if
    else
    {
        fillMyPolygon(g, 10, 10);
        drawMyPolygon(g);
    }//end else

    //set buttons to visible
    buttons();
}//end paint

如果您有任何想法或可能需要更多信息，请告诉我。谢谢

Answer 1

算法的问题很简单，就是缺少括号来分隔公式的不同部分，这些公式决定了剪裁线的新坐标。解决后效果很好

使用 Sutherland-Hodgman 算法时多边形裁剪不起作用

Polygon Clipping not working when using Sutherland-Hodgman Algorithm

java

algorithm

netbeans

clipping

polygon