c++algorithmcomputational-geometry

How to fill a closed poly-line with equidistant horizontal lines?


I need to write and algorithm that fills closed poly-line with horizontal equidistant lines.

I've done similar things with rectangles and circles, here is a code snippet for the latter:

// circle parameters: center(point(0).x, point(0).y), radius
int offsetX = point(0).x + radius;
int offsetY = point(0).y + radius;
for(int i = -radius; i < radius; i += spacing){
    int ry = i;
    int rx = sqrt(double(radius*radius - ry*ry));
    // the parameters are pair of coordinates of the horizontal line
    fl_line(offsetX - rx, offsetY + i, 
            offsetX + rx, offsetY + i);
}

In the case of closed poly-line the additional degree of difficulty (for me) is that the coordinates of the horizontal lines would not be extracted from a single equation (circle, height of rectangle, etc), but rather from the equations of the lines with the same "y" coordinates, which will not match continuously.

Question:

  1. Could you provide me with some insight on how to proceed with creating an algorithm that fills closed poly-lines with horizontal lines?

Solution

  • This is just a special case of the scan line algorithm (designed for filling polygons): http://www.tutorialspoint.com/computer_graphics/polygon_filling_algorithm.htm

    Iterate y from yMin (top of your polygon) to yMax with the desired step (spacing).

    For each y, find intersections with the polygon line segments, order them by their x-coordinate, connect every other pair with a line