使用我的多边形填充算法填充多边形会出现越界错误

Question

我正在创建一个程序，它需要绘制一个多边形，然后用绿色填充多边形。我目前编写的算法存在问题，因为它只填充多边形的上半部分，然后出现 IndexOutOfBounds 错误。

这是我的算法代码：

public class FillPolygon
{
    int left_most_edge, right_most_edge, scan = 0;
    double[] xcoord;
    double[][] table = new double[4][200];  //2d array containing: 
                                            //[0][-] -> ymax, [1][-] -> ymin, [2][-] -> dx, [3][-] -> x

    public void initializeTable()
    {
        int i, j;

        for (i = 0; i < 4; i++)
        {
            for (j = 0; j < 200; j++)
            {
                table[i][j] = 0;
            }//end for
        }//end for
    }//end initializeTable

    public void help(int i)
    {
        double helpX, helpDX, helpYMax, helpYMin;
        for (int j = i - 1; j >= 0; j--)
        {
            if ((table[1][j] == table[1][j + 1] && table[3][j] > table[3][j + 1]) || table[1][j] > table[1][j + 1])
            {
                helpYMax = table[0][j];
                table[0][j] = table[0][j + 1];
                table[0][j + 1] = helpYMax;

                helpYMin = table[1][j];
                table[1][j] = table[1][j + 1];
                table[1][j + 1] = helpYMin;

                helpDX = table[2][j];
                table[2][j] = table[2][j + 1];
                table[2][j + 1] = helpDX;

                helpX = table[3][j];
                table[3][j] = table[3][j + 1];
                table[3][j + 1] = helpX;
            }//end if
        }//end for
    }//end help

    public double max (double x, double y)
    { //determines the greater of two values
        double max;
        if (x > y)
            max = x;
        else
            max = y;
        return max;
    }//end max

    public void edgeInsert(double xStart, double yStart, double xEnd, double yEnd, int number_entered_edges)
    {
        int j = number_entered_edges - 1; //removing the - 1 removes line on left side
        double x;

        if (yStart > yEnd)
        {
            table[0][j] = yStart;
            table[1][j] = yEnd;
        }//end if
        else
        {
            table[0][j] = yEnd;
            table[1][j] = yStart;
        }//end else

        if (table[1][j] == xStart)
            x = xStart;
        else
            x = xEnd;

        if (table[0][j] == yStart)
            table[2][j] = -(-(xEnd - xStart) / (yEnd - yStart));
        else
            table[2][j] = -(xEnd - xStart) / (yEnd - yStart);

        table[3][j] = x + table[2][j] / 2;

        help(j);
    }//end edgeInsert

    public void loadTable(int number_vertices, int number_entered_edges,
                    double[] px, double[] py)
    { //take the x and y coordinats and build an edge table based off of them
        int k;
        double xStart, yStart, xEnd, yEnd;

        xStart = px[number_vertices - 1];
        yStart = trunc(py[number_vertices - 1]) + 0.5;

        //start off with no edges in edge table
        number_entered_edges = 0;
        for (k = 0; k < number_vertices; k++)
        {
            xEnd = px[k];
            yEnd = trunc(py[k]) + 0.5;
            System.out.println("x: " + xEnd + " y: " + yEnd);
            if (yStart == yEnd)
            {
                xStart = xEnd;
            }//end if
            else
            {
                //add edge to edge table
                number_entered_edges++;
                edgeInsert(xStart, yStart, xEnd, yEnd, number_entered_edges);

                yStart = yEnd;
                xStart = xEnd;
            }//end else
        }//end for
        scan = (int)trunc(table[1][0]); //start at the top of the polygon
    }//end loadTable

    public void include(int number_entered_edges)
    { //pushing the right most edge
        while ((right_most_edge + 1 < number_entered_edges) && (table[1][right_most_edge + 1] < scan))
        {
            right_most_edge++;
        }//end while
    }//end include

    public void exclude()
    { //excluding edges that we no longer care about
        for (int i = left_most_edge; i <= right_most_edge; i++)
        {
            if (table[0][i] < scan)
            {
                left_most_edge++;
                for (int j = i; j >= left_most_edge; j--)
                {
                    table[0][j] = table[0][j - 1];
                    table[2][j] = table[2][j - 1];
                    table[3][j] = table[3][j - 1];
                }//end for
            }//end if
        }//end for
    }//end exclude

    public void updateX()
    { //increment x based on dx
        for (int i = left_most_edge; i <= right_most_edge; i++)
        {
            table[3][i] += table[2][i];
        }//end for
    }//end updateX

    public void sortOnX()
    { //sorting x values from least to greatest in edge table
        int l = 0;
        double t;
        xcoord = new double[right_most_edge - left_most_edge + 1];

        for (int i = left_most_edge; i <= right_most_edge; i++)
        {
            xcoord[l] = table[3][i];
            for(int j = l - 1; j >= 0; j--)
            {
                if (xcoord[j] > xcoord[j + 1])
                {
                    t = xcoord[j];
                    xcoord[j] = xcoord[j + 1];
                    xcoord[j + 1] = t;
                }//end if
            }//end for

            l++;
        }//end for
    }//end sortOnX

    public void fillScan(Graphics g)
    { //determines the line to be drawn for filling
        for (int i = 0; i < xcoord.length; i += 2)
        {
                drawMyHorizontalLine(g, (int)Math.round(xcoord[i]), scan, (int)Math.round(xcoord[i + 1]));
        }//end for
    }//end fillScan

    public double trunc(double num)
    { //trucates the number passed in to remove any decimal
        double rem;
        if ((num % 2) == 0)
            return num;
        else
        {
            rem = num % 2;
            return num - rem;
        }//end else
    }//end trunc

    public void drawMyPolygon(Graphics g)
    { //draws the polygon
        g.setColor(Color.RED);
        g.drawLine(100, 125, 150, 100); //from (100, 125) to (150, 100)
        g.drawLine(150, 100, 250, 200); //from (150, 100) to (250, 200)
        g.drawLine(250, 200, 300, 150); //from (250, 200) to (300, 150)
        g.drawLine(300, 150, 250, 100); //from (300, 150) to (250, 100)
        g.drawLine(250, 100, 150, 200); //from (250, 100) to (150, 200)
        g.drawLine(150, 200, 100, 200); //from (150, 200) to (100, 200)
        g.drawLine(100, 200, 100, 125); //from (100, 125) to (100, 125)
    }//end drawMyPolygon

    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 fillMyPolygon(Graphics g, int number_vertices, int number_entered_edges, double[] px, double[] py)
    { //called methods to deal with edge table and fill the polygon
        if (number_entered_edges < 3 || number_entered_edges > 200)
        {
            System.out.println("Polygon size error");
        }//end if
        else
        {
            loadTable(number_vertices, number_entered_edges, px, py);
            while (left_most_edge < number_entered_edges)
            {
                scan++;
                exclude();
                updateX();
                include(number_entered_edges);
                sortOnX();
                fillScan(g);
            }//end while
        }//end else
    }//end fillMyPolygon



}//end FillPolygon

@Override
public void paint(Graphics g)
{
    FillPolygon f = new FillPolygon();
    double[] px = new double[7]; //contains all x coord.
    double[] py = new double[7]; //contains all y coord.

    //populate x coord.
    px[0] = 100;
    px[1] = 150;
    px[2] = 250;
    px[3] = 300;
    px[4] = 250;
    px[5] = 150;
    px[6] = 100;

    //populate y coord.
    py[0] = 125;
    py[1] = 100;
    py[2] = 200;
    py[3] = 150;
    py[4] = 100;
    py[5] = 200;
    py[6] = 200;

    f.initializeTable();
    f.fillMyPolygon(g, 7, 7, px, py); //begin filling the polygon
    f.drawMyPolygon(g); //draw polygon with red outline
}//end paint

我不知道为什么会收到错误消息或如何停止它。错误发生在我的行 "drawMyHorizontalLine(g, (int)Math.round(xcoord[i]), scan, (int)Math.round(xcoord[i + 1]));"

非常感谢您的帮助。谢谢

Answer 1

这是因为 i + 1 在 for 循环的最后一次迭代中超出了 xcoord 数组的范围。

我按如下方式更改了您的 fillScan() 方法，它似乎表现得更好（从 i = 1 开始并在循环内使用 i - 1，而不是 i + 1 ).

    public void fillScan(Graphics g) {
        for (int i = 1; i < xcoord.length; i++) {
            drawMyHorizontalLine(g, (int) Math.round(xcoord[i-1]),
                                scan, (int) Math.round(xcoord[i]));
        }
    }

Answer 2

这个循环是你的问题。您一次遍历数组的两个位置 (i+= 2)，但您一直这样做直到 i < xcoord.length。

所以当i == (xcoord.length - 1)时，即xcoord[i]是数组的最后一个元素，在你调用drawMyHorizontalLine的方法中，xcoord[i + 1]会过去数组的末尾。

public void fillScan(Graphics g)
{ //determines the line to be drawn for filling
    for (int i = 0; i < xcoord.length; i += 2)
    {
        drawMyHorizontalLine(g, (int)Math.round(xcoord[i]), scan, (int)Math.round(xcoord[i + 1]));
    }//end for
}//end fillScan

要修复此循环，只需更改为 for(...; i < xcoord.length-1 ;i += 2)。只要数组中剩余两个元素，就一次移动两个元素。

这应该可以解决您的越界错误，不确定您的多边形是否只填充了一半。我不太理解你的多边形表示。

使用我的多边形填充算法填充多边形会出现越界错误

Filling in polygon with my polygon fill algorithm give an out of bounds error

java

polygon

fill

indexoutofboundsexception