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:
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
.
The problem was that I calculated with
int
numbers and anint
divided by anotherint
results in inaccuracies. So just doing this withdouble
numbers solved it.This is how I calculate the intersection points:
edges
is aArrayList<Point>
containing the edge points.ymin
is the lowest y value and `ymax`` the highest one.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)
.