扫描线:寻找交点

Question

我想用扫描线算法填充一个多边形。为此，我必须知道扫描线与多边形接触的所有点。我为此写了一个循环，但它显然不起作用(它从不向列表中添加一个点，这意味着它找不到任何可以切割多边形的点)我可以创建一个多边形，并从它的所有边。

这是我的代码获取点的扫描线相交的多边形Xmin, xmax, ymin和ymax是多边形的最大点。他们也是正确的。contains()检查一个点是否在多边形内，使用java.awt.Polygon类。这也在起作用。wasInside包含一个布尔值，它保存旧的状态，无论最后检查的点是否在多边形内。

boolean wasInside = false;
ArrayList<Point> intersectionPoints = new ArrayList<Point>();
    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;
            }
        }
    }

Answer 1

我已经在最小框架中运行了您的代码。它可以工作，没有任何问题。

我建议你检查这些陷阱:

• Polygon.contains()从字面上检查点是否在内。例如，如果多边形是从点(10,10)开始的矩形，那么contains(10, 10)将返回false。只有contains(11, 11)会返回true。所以你找的不是真正的交点，而是里面的第一个(和最后一个)点。
• (对不起，我自己偶然发现了)确保x和y没有混淆。
• 检查方向:如果你使用画布，(0,0)是左上角点。但是如果你拿一本数学书，看看笛卡尔图，(0,0)是左下角的点，除非你有负值。会不会方向搞错了?
• 如何检查intersectionPoints是否添加了一些点?这应该可以工作:System.out.println("Nb of intersection points found: " + intersectionPoints.size());

在此之后，它应该为您工作。为了更好地理解，您可能需要打印出检查的内容:

for (int xTemp = xmin; xTemp <= xmax; xTemp++) {
    System.out.println("Check: " + xTemp + ", " + yTemp);
    if (wasInside != this.contains(new Point(xTemp, yTemp))) {
        System.out.println(" - Inside! Bash!");
        intersectionPoints.add(new Point(xTemp, yTemp));
        wasInside = !wasInside;
    }
}