Thuật toán Xén đường thẳng

#include <stdio.h>
#include <stdlib.h>
#include <stack>
using namespace std;
#define Round(a) (int)(a+0.5)

struct myPoint      // diem
{
    int x, y;
};

struct myLine       // duong thang
{
    myPoint A, B;
    float m;
};

struct myRectangle  // hinh chu nhat
{
    int n;
    myLine *a;
};

stack <myPoint> S;

int check_myPoint(myLine L, myPoint P)  // kiem tra diem nam ben trai - phai duong thang
{
    int c = (L.B.x - L.A.x)*(P.y - L.A.y) - (L.B.y - L.A.y)*(P.x - L.A.x);
    if (c >= 0) return 1;   // trai
    else return 0;  // phai
}

void check_myLine(myLine L, myLine P1P2)    // tim diem giao giua 2 duong thang va luu vao S
{
    int a = check_myPoint(L, P1P2.A), b = check_myPoint(L, P1P2.B);
    if (!a && !b)
        return;
    if (a && b)
    {
        S.push(P1P2.A);
        S.push(P1P2.B);
        return;
    }
    myPoint I;
    if (b)
    {
        myPoint temp = P1P2.A;
        P1P2.A = P1P2.B;
        P1P2.B = temp;
    }

    if (L.A.x == L.B.x)
    {
        I.x = L.A.x;
        I.y = P1P2.A.y + Round((float)(I.x - P1P2.A.x)*P1P2.m);
    }
    else if (L.A.y == L.B.y)
    {
        I.y = L.A.y;
        I.x = P1P2.A.x + Round((float)(I.y - P1P2.A.y)/P1P2.m);
    }

    S.push(P1P2.A);
    S.push(I);
}

void SutherlandHodgman(myRectangle R, int n, myLine P1P2)       // xen duong thang
{
    //P1P2.m = (float)(P1P2.B.y - P1P2.A.y)/(P1P2.B.x - P1P2.A.x);

    check_myLine(R.a[0], P1P2);
    for (int i=1; i<n; i++)
    {
        P1P2.A = S.top();
        S.pop();
        P1P2.B = S.top();
        S.pop();

        check_myLine(R.a[i], P1P2);
    }

}

int main()
{
    int n = 4;
    myPoint A[] = {
            {2,2},  //A
            {8,2},  //B
            {8,6},  //C
            {2,6},  //D
            {1,3},  // P1
            {11,8}  // P2
        };
    myLine P1P2 = {A[4], A[5], (float)(P1P2.B.y - P1P2.A.y)/(P1P2.B.x - P1P2.A.x)}; // P1P2
    myLine *L = (myLine *) malloc(n*sizeof(myLine));
    for (int i=0; i<n; i++)
    {
        L[i].A = A[i];
        L[i].B = A[(i+1)%n];
    }
    myRectangle R = {n, L}; // HCN ABCD

    SutherlandHodgman(R, n, P1P2);      // Xen P1P2 bang ABCD

    if (S.empty())
    {
        printf("Khong co doan thang nao duoc giu lai");
        return 0;
    }
    printf("Cac doan thang duoc giu lai tao nen tu cac diem:\n");
    while (!S.empty())
    {
        printf("(%d, %d)\n", S.top().x, S.top().y);
        S.pop();
    }

    return 0;
}