How to implement scanline algorithm to draw a shape in c++/qt

Question

I am trying to implement scan line algorithm in order to fill in drawn shape with color in program qt creator where I use c++. I am particularly stuck on part 2. Can someone give me advice how to deal with this?

//parameter vector of segments, after I draw shape on my screen, each segment that has been connected with line is stored in this vector.
void MyProgram::drawScanLine(std::vector<Segment> p) {
    double minY = p[0].y;
    double maxY = p[0].y;
    for(int i=0;i<p.size();i++) {
          if(p[i].y < minY) {
              minY = p[i].y;
          }
          if(p[i].y> maxY) {
              maxY = p[i].y;
          }
    }
    //x[]
    //find the intersection from the horizontal level of y
    //sort the array/vector (x[])
    //I have a method that fills every pixel with color.
    std::cout<<"MIN: "<<minY<<"MAX: "<<maxY<<std::endl;
    for(int y=minY;y<=maxY;y++) {
        std::cout<<"Test"<<std::endl;
    }
}

Is there any reason you're doing this 'by hand' rather than using the existing functionality available in [`QPainter`](https://doc.qt.io/qt-6/qpainter.html), [`QPainterPath`](https://doc.qt.io/qt-6/qpainterpath.html) etc.? — G.M., Jul 02 '22 at 08:24
Does this answer your question? [How do I sort a vector of pairs based on the second element of the pair?](https://stackoverflow.com/questions/279854/how-do-i-sort-a-vector-of-pairs-based-on-the-second-element-of-the-pair) — infinitezero, Jul 02 '22 at 08:45
Re. `"sorting is the least of the problems here"`: you state `"I am particularly stuck on part 3"` where 'part 3' specifies `"Sort the intersection point in the increasing order of X coordinate"`. So your question as it stands states quite clearly that sorting *is* the problem. If it isn't then please edit your question accordingly. — G.M., Jul 02 '22 at 12:01

infinitezero · Answer 1 · 2022-07-03T08:43:34.127

0

Assuming you have all the edge points of the polygon, then we just need to find the intersection between a horizontal line and each line segment.

The equations for a line through two points (x1, y1) and (x2, y2) are given by

(x1)  + r (x2-x1)   (1)
(y1)  + r (y2-y1)   (2)

Assuming you scan at height h, solve (2) for r, i.e.

h = y1 + r (y2-y1)
=> r = (h-y1)/(y2-y1)

if 0 <= r <= 1 you are still within the line segment (convince yourself that this is true). If so, plug in r into equation (1) to obtain the corresponding x coordinate.

Iterate through all the points in your polygon (i.e. through each line segment) and you'll have all the intersection points.

edited Jul 03 '22 at 08:43

answered Jul 02 '22 at 14:18

infinitezero

1,610
3
14
29

But how do I get the p0, p1 etc? I completely dont understand this. All I got are the segments(corners) of the shape which is being passed as parameter. I also have a line drawing algorithm that fills every pixel from point A to B. – Dave Jul 03 '22 at 08:31
Every point has the same y coordinate as the one you scan. How to get the x-coordinate,I described above. If you need more help, please specify precisely where you are stuck and what you don't understand – infinitezero Jul 03 '22 at 08:42

How to implement scanline algorithm to draw a shape in c++/qt

1 Answers1