Skanowanie linii algorytm

Próbuje zaimplementowac Scanline który pokoloruje mi kształ, lecz mam problem przy Step 2. Nie mam kompletnie idei jak znaleźć punkty przecięcia, z googlem też to jakoś nie idzie - doradzi ktoś coś jak iść z tym dalej?

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

    //find intersection segments
    //sort
    //fill all segments from x[2n] to x[2n+1]
    std::cout<<"MIN: "<<minY<<"MAX: "<<maxY<<std::endl;
    for(int y=minY;y<=maxY;y++) {
        
    }
}

Punkty na ekranie dodaje sobie myszką, aktualnie wygląda to tak

W sumie tu google nie jest potrzebne, można to na prostych liniowych zrobić i rozwiązywaniu układów równań.

masz punkty z wierzchołów, A, B, C, D, E, F i łączysz w pary A->B pierwsza funkcja liniowa, B->C Druga, itp.
Otrzymasz tak 6 funkcji liniowych i potem robisz następną tą scaneline i iterując po wszystkich funkcjach liniowych rozwiązujesz szukając punktu przecięcia.
Masz jakąś funkcję i sprawdzasz po kolej tą funkcję liniową ze wszystkimi tworzącymi tego polygona czyli A-B z tą funkcją,która przecina i rozwiązujesz jakąś metodą np. podstawienia czy tam gaussa jordana metodą, możesz wcześniej sprawdzić czy funkcje nie są równoległe, a także czy nie min i max funkcji liniowej nie przekroczył punktu, czyli czy rozwiązanie nie znajduje się czasem po za punktem zaczęcia i zakończenia funkcji.

Tak otrzymane punkty, możesz sortować jak tam masz, możesz też sobie graf zrobić i odszukać cycle, albo jakoś łatwiej sprawdzić, które funkcje są połączone i czy występują w nich przecięcia.

Potem musisz wykonać rasteryzację, najlepiej stworzyć oddzielną surface, powierzchnię, i np. mając 3 punkty trójkąt, czy więcej, tworzysz na tej pustej planszy rysujesz jakimś kolorem border tych obiektów, wyliczasz środkowy punkt średnią, i rekurencyjnie od tego środkowego punktu w każdym kierunku się przesuwasz do góry, na dół, lewo, prawo i jak trafisz na już zakolorowane pole czyli obramowanie lub inne pole to kończysz rekurencję, aż ci się powierzchnia zapełni kolorem, potem robisz binary maskę na głównej powierzchni.

Co tam engine jakiś piszesz? Lepsza jest hardware acceleracja rasteryzacji, na CPU są różne metody wykonania tego, ja kiedyś robiłem coś podobnego jak wyżej.

//skrzyżowanie (prostej przez A,B) z (prostą przez C,D):
//(Ax,Ay)-(Bx,By) & (Cx,Cy)-(Dx,Dy)
double Ax=MinX, Ay=ScanY, Bx=MaxX, By=ScanY;
double Cx=p[i].x, Cy=p[i].y, Dx=p[(i+1)%p.size()].x, Dy=p[(i+1)%p.size()].y;
double x=((Bx-Ax)*(Dx*Cy-Dy*Cx)-(Dx-Cx)*(Bx*Ay-By*Ax))/((By-Ay)*(Dx-Cx)-(Dy-Cy)*(Bx-Ax));
//double y=((Dy-Cy)*(Bx*Ay-By*Ax)-(By-Ay)*(Dx*Cy-Dy*Cx))/((Dy-Cy)*(Bx-Ax)-(By-Ay)*(Dx-Cx)); // tego wierszu akurat nie potrzebujesz
if((Ax<=x)&&(x<=Bx)) // got intersect in point x,y