Алгоритм Scanline: как рассчитать точки пересечения

Мне нужно реализовать алгоритм развертки от нашего профессора, но я не очень понимаю, как получить точки пересечения линии развертки с полигоном. Вот алгоритм: алгоритм сканирования

Я уже реализовал свой собственный многоугольник (с такими методами, как 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;
            }
        }
    }

Но я получил подсказку, что это не правильное решение из мой вопрос о стеке с переполнением.

Может ли кто-нибудь дать мне подсказку, как я могу начать реализацию алгоритма от моего профессора? Где взять точки 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.


java scanline
person Peter    schedule 28.06.2014    source источник
comment
Агоритм строки развертки обычно поддерживает набор активных ребер (а именно, ребер, пересекаемых текущей строкой развертки). c - это просто текущая y-позиция строки сканирования. А точки (x1,y1) и (x2,y2) — это просто конечные точки одного активного ребра. Вы должны отсортировать все ребра на основе их значений y, а затем позволить c пройти от ymin до ymax, обновляя набор активных ребер всякий раз, когда вы сканируете угол.   -  person Marco13    schedule 29.06.2014
comment
Спасибо за ваши подсказки. Я добавил свою попытку вычислить точки пересечения, но в ней есть ошибки. Что я делаю не так? Кажется, я не очень хорошо понял этот алгоритм...   -  person Peter    schedule 29.06.2014
comment
Вам так и не удалось сказать, что вы пытаетесь вычислить. Строка сканирования — это класс алгоритмов, которые могут вычислять многие вещи. Как сказал @Marco13, сама строка сканирования представляет собой структуру данных, которая обычно включает в себя список ребер, сегментов линий, дуг и т. д., которые она пересекает в данный момент. Конечные точки ребер и т.п., а также пересечения обрабатываются как события, изменяющие линию развертки.   -  person Gene    schedule 29.06.2014
comment
Извините за это, я хочу заполнить полигон алгоритмом сканирования.   -  person Peter    schedule 29.06.2014

Ответы (1)


arrow_upward
1
arrow_downward

Проблема заключалась в том, что я рассчитал с 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, содержащий ArrayLists точек развертки для каждой строки развертки. Так что вам просто нужно нарисовать их с помощью drawLine(x1, y2, x2, y2).

person Peter    schedule 12.07.2014