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 questionから、これは適切な解決策ではないというヒントを得ました。

教授からアルゴリズムの実装を開始するにはどうすればよいですか？x1、y1、x2、y2、c ポイントはどこで取得できますか? これらがエッジであることはわかっていますが、どのエッジを使用する必要があるかをどのように知ることができますか?

編集:OK、これですべてのエッジが 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