Search code examples
javascanline

Scanline algorithm: how to calculate intersection points

I have to implement a scanline algorithm from our professor but I don't really understand how I get the intersection points from the scanline with a polygon. Here is the algorithm: scanline algorithm

I implemented my own polygon(with methods like paint(), contains() and so on) already and I have all edges from the polygon saved in an array like this:

int[] pointsX;
int[] pointsY;

and I have the min and max values for x and y saved in

int ymin, ymax, xmin, xmax;

So my first thought is that I have to create a scanline starting from 0,ymin and check in a loop if the next point is inside the polygon. I implemented this method like this:

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;
}

So when the next point is inside the polygon, I have a intersection point and so on. For this i have this loop:

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;
            }
        }
    }

But I got a hint that this is no proper solution from my stackoverflow question.

Can someone give me a hint, how I can start implementing the algorithm from my professor? Where do I get the x1,y1,x2,y2,c points? I know that these are the edges but how do I know which edges do I have to take?

EDIT: OK, now I have all Edges sorted by their y values. Can I calculate the intersection points with the given formula Sx=x1+(x2-x1)/...? My first try looks like this:

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));
                }
            }
        }
    }

But this seems to be wrong, because I get a lot of wrong Points in intersectionPoints.

Solution

  • The problem was that I calculated with int numbers and an int divided by another int results in inaccuracies. So just doing this with double numbers solved it.

    This is how I calculate the intersection points: edges is a ArrayList<Point> containing the edge points. ymin is the lowest y value and `ymax`` the highest one.

    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);

    This will give you an ArrayList containing ArrayLists of scanline points for every Scanline. So you just have to draw them with drawLine(x1, y2, x2, y2).