scanline: finding intersection points

Question

I want to fill a polygon with the scanline algorith. for this I have to know all points where the scanline comes in contact with the polygon. I wrote a loop for this, but its obviously not working (it never adds a point to the list which means it can't find any points which cuts the polygon) I can create a Polygon and have all Edges from it.

Here is my code for getting the points of the scanline which intersect the polygon xmin, xmax, ymin and ymax are the max points from the polygon. They are also correct. contains() checks, if a Point is inside the polygon, with using the java.awt.Polygon class. This is working too. wasInside contains a boolean, which saves the old state, if the last point checked was inside the polygon or not.

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

peter_the_oak · Accepted Answer · 2014-06-28 15:10:49Z

1

I have run your code in a minimal frame. It works, there is nothing wrong with it.

I suggest you check these pitfalls:

Polygon.contains() checks literally if a point is inside. So e.g. if your polygon is a rectangle starting at point (10, 10), then contains(10, 10) will return false. Only contains(11, 11) will return true. So you are not finding the real intersection points, but the first (and last) points inside.
(Sorry, I've stumbled upon it myself) Make sure x and y are confused nowhere.
Check the orientation: if you work with canvas, (0, 0) is the upper left point. But if you take a Math book and look at a Cartesian diagram, (0, 0) is the bottom left point - unless you have negative values. Could the orientation be confused somewhere?
How do you check if some points were added to intersectionPoints? This should work: System.out.println("Nb of intersection points found: " + intersectionPoints.size());

After this, it should work for you. You might want to print out what is checked for better understanding:

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

answered Jun 28, 2014 at 15:10

peter_the_oak

3,7405 gold badges28 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Peter Over a year ago

thanks for your help, I had something mixed up with the xmin and xmax. Also the hint that it won't find points which are on the border of the polygon was important. to fix this, can I just say something like: intersectionPoints.add(new Point(xTemp - 1, yTemp)); ? Because the x value is always 1 pixel to high in my opinion.

peter_the_oak Over a year ago

If your scanline enters the polygon, the polygon's border will be 1 px to the left. If your scanline leaves the polygon, the polygon's border will be the point just checked. But doing so, you still won't find the y axis intersection part properly. I'm sorry but for a proper solution, I think you will have to work either with java.awt.geom.Line2D, in order to find real intersection points, or with java.awt.geom.Area.intersect(Area). Find a good start here.

Collectives™ on Stack Overflow

scanline: finding intersection points

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related