Scanline: поиск точек пересечения

Question

Я хочу заполнить многоугольник алгоритмом сканирования. для этого мне нужно знать все точки, где сканлайн соприкасается с полигоном. Я написал цикл для этого, но он, очевидно, не работает (он никогда не добавляет точку в список, что означает, что он не может найти какие-либо точки, которые обрезают многоугольник). Я могу создать многоугольник и получить все ребра из него.

Вот мой код для получения точек линии развертки, которые пересекают многоугольник xmin, xmax, ymin и ymax - это максимальные точки из многоугольника. Они тоже правильные. содержит () проверяет, находится ли точка внутри многоугольника, с использованием класса 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) вернет ложь. Только contains(11, 11) вернет истину. Таким образом, вы не находите реальные точки пересечения, но первые (и последние) точки внутри.
• (Извините, я сам наткнулся на это) Убедитесь, что 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;
    }
}