1

我必须从我们的教授那里实现一个扫描线算法，但我真的不明白我是如何从扫描线与多边形获得交点的。这是算法： 扫描线算法

我已经实现了自己的多边形（使用 等方法） paint()，contains()并且我将多边形的所有边保存在这样的数组中：

int[] pointsX;
int[] pointsY;

我保存了 x 和 y 的最小值和最大值

int ymin, ymax, xmin, xmax;

0,ymin所以我的第一个想法是，如果下一个点在多边形内，我必须创建一个扫描线并检查一个循环。我这样实现了这个方法：

public boolean contains(Point test) {
    boolean result = false;

    java.awt.Polygon polygon = new java.awt.Polygon(pointsX, pointsY, pointsX.length);
    if (polygon.contains(test)) {
        result = true;
    }

    return result;
}

所以当下一个点在多边形内时，我有一个交点，依此类推。为此，我有这个循环：

ArrayList<Point> intersectionPoints = new ArrayList<>();
wasInside = false;
    for (int yTemp = ymin; yTemp <= ymax; yTemp++) {
        for (int xTemp = xmin; xTemp <= xmax; xTemp++) {
            if (wasInside != this.contains(new Point(xTemp, yTemp))) {
                intersectionPoints.add(new Point(xTemp, yTemp));
                wasInside = !wasInside;
            }
        }
    }

但是我从我的 stackoverflow 问题中得到了一个提示，这不是正确的解决方案。

有人可以给我一个提示，我如何从教授那里开始实施算法？我在哪里获得 x1,y1,x2,y2,c 积分？我知道这些是边缘，但我怎么知道我必须采取哪些边缘？

编辑：好的，现在我所有的边缘都按它们的 y 值排序。我可以用给定的公式 Sx=x1+(x2-x1)/... 计算交点吗？我的第一次尝试是这样的：

for (int c = ymin; c <= ymax; c++) {
        for (int xTemp = xmin; xTemp <= xmax; xTemp++) {
            for (int currentEdge = 0; currentEdge < edges.size() - 1; currentEdge++) {
                int x1 = edges.get(currentEdge).x;
                int x2 = edges.get(currentEdge + 1).x;
                int y1 = edges.get(currentEdge).y;
                int y2 = edges.get(currentEdge + 1).y;
                if ((y1 <= c && y2 > c) || (y2 <= c && y1 > c)) {
                    intersectionPoints.add(new Point((x1 + (x2 - x1) / (y2 - y1) * (c - y1)),c));
                }
            }
        }
    }

但这似乎是错误的，因为我在intersectionPoints.

4

1 回答 1

1

问题是我用int数字计算并int除以另一个int结果不准确。所以只是用double数字来解决它。

这就是我计算交点的方式： edges是一个ArrayList<Point>包含边缘点的。 ymin是最低的 y 值，而 `ymax`` 是最高的。

for (int yTemp = ymin; yTemp <= ymax; yTemp++) {
        ArrayList<Point> intersectionPoints = new ArrayList<>();

        for (int p = 0; p < edges.size() - 1; p++) {
            int x1, x2, y1, y2;
            double deltax, deltay, x;
            x1 = edges.get(p).x;
            y1 = edges.get(p).y;
            x2 = edges.get(p + 1).x;
            y2 = edges.get(p + 1).y;

            deltax = x2 - x1;
            deltay = y2 - y1;

            int roundedX;
            x = x1 + deltax / deltay * (yTemp - y1);
            roundedX = (int) Math.round(x);
            if ((y1 <= yTemp && y2 > yTemp) || (y2 <= yTemp && y1 > yTemp)) {
                intersectionPoints.add(new Point(roundedX, yTemp));
            }
        }
        //for the last interval
        int x1, x2, y1, y2;
        x1 = edges.get(edges.size() - 1).x;
        y1 = edges.get(edges.size() - 1).y;
        x2 = edges.get(0).x;
        y2 = edges.get(0).y;
        if ((y1 <= yTemp && y2 > yTemp) || (y2 <= yTemp && y1 > yTemp)) {
            intersectionPoints.add(new Point(x1 + (x2 - x1) / (y2 - y1) * yTemp - y1, yTemp));
        }
        //you have to sort the intersection points of every scanline from the lowest x value to thr highest
        Collections.sort(intersectionPoints, new SortXPoints());
        pointsOfScanline.add(intersectionPoints);

这将为您提供一个 ArrayList，其中包含每个扫描线的扫描线点的 ArrayList。所以你只需要用drawLine(x1, y2, x2, y2).

于 2014-07-12T11:32:39.480 回答