Implement the algorithm to Draw the polygon using filling technique in C Language.

 Here's a C++ program to draw and fill a polygon using the scan-line filling technique. This program uses the graphics.h library, which is typically available in Turbo C++ or similar environments. If you're using modern compilers like GCC, you'll need to use other graphics libraries like OpenGL or SDL.

Steps of the Algorithm

  1. Accept the vertices of the polygon.

  2. Find intersections of the scan line with polygon edges.

  3. Sort intersections by increasing x-coordinate.

  4. Fill pixels between pairs of intersections.


The Scan-Line Filling algorithm is a popular technique used in computer graphics to fill polygons. It works by drawing horizontal lines (scan lines) through the entire area of the polygon and determining which parts of these scan lines are inside the polygon and should be filled. Here's a detailed explanation and C program to draw and fill a polygon using the scan-line filling technique.

Steps for the Scan-Line Filling Algorithm:

  1. Input Polygon Coordinates: The user provides the polygon's vertices.

  2. Sort Edges by Y-coordinate: The edges of the polygon are sorted by their y-coordinate. This helps in determining which edges intersect the scan line.

  3. Intersect with Scan Lines: For each scan line (horizontal line), the algorithm calculates which edges of the polygon it intersects.

  4. Sort Intersections: Once the scan line intersects the polygon's edges, the intersections are sorted by their x-coordinate.

  5. Fill Between Intersections: The polygon is filled between each pair of intersection points.


C++ Code for Scan-Line Polygon Filling


#include <graphics.h>
#include <stdio.h>

#define MAX_VERTICES 100

void drawPolygon(int polyX[], int polyY[], int n) {
    for (int i = 0; i < n - 1; i++) {
        line(polyX[i], polyY[i], polyX[i + 1], polyY[i + 1]);
    }
    line(polyX[n - 1], polyY[n - 1], polyX[0], polyY[0]);  // Closing the polygon
}

void fillPolygon(int polyX[], int polyY[], int n) {
    int i, j, k;
    int y, temp;
    int x_intersections[MAX_VERTICES], intersections;

    int minY = polyY[0], maxY = polyY[0];
    
    // Find min and max Y values of the polygon
    for (i = 1; i < n; i++) {
        if (polyY[i] < minY) minY = polyY[i];
        if (polyY[i] > maxY) maxY = polyY[i];
    }

    // Scan-line filling
    for (y = minY; y <= maxY; y++) {
        intersections = 0;

        // Find intersections with polygon edges
        for (i = 0; i < n; i++) {
            j = (i + 1) % n;  // Next vertex
            
            if ((polyY[i] <= y && polyY[j] > y) || (polyY[j] <= y && polyY[i] > y)) {
                x_intersections[intersections++] =
                    polyX[i] + (y - polyY[i]) * (polyX[j] - polyX[i]) / (polyY[j] - polyY[i]);
            }
        }

        // Sort intersections using Bubble Sort
        for (i = 0; i < intersections - 1; i++) {
            for (j = 0; j < intersections - 1 - i; j++) {
                if (x_intersections[j] > x_intersections[j + 1]) {
                    temp = x_intersections[j];
                    x_intersections[j] = x_intersections[j + 1];
                    x_intersections[j + 1] = temp;
                }
            }
        }

        // Fill pixels between pairs of intersections
        for (i = 0; i < intersections; i += 2) {
            for (j = x_intersections[i]; j <= x_intersections[i + 1]; j++) {
                putpixel(j, y, WHITE);
            }
        }
    }
}

int main() {
    int gd = DETECT, gm;
    initgraph(&gd, &gm, "C:\\Turboc3\\BGI");

    int polyX[] = {100, 200, 250, 150};
    int polyY[] = {100, 50, 150, 200};
    int n = 4;  // Number of vertices

    drawPolygon(polyX, polyY, n);
    fillPolygon(polyX, polyY, n);

    getch();
    closegraph();
    return 0;
}



Explanation

  1. drawPolygon(): Draws the outline of the polygon.

  2. fillPolygon():

    • Determines the min and max Y values.

    • Finds intersections for each scan-line.

    • Sorts the intersection points.

    • Fills pixels between intersection pairs.


Comments

Post a Comment

Popular posts from this blog

Implement the DDA algorithm to draw the line. Generalize it for co-ordinates in C language.

Detailed Explanation of the DDA Algorithm: The Digital Differential Analyzer (DDA) algorithm is one of the simplest algorithms used in computer graphics to draw a straight line between two points. It works by interpolating values in small steps between the starting and ending coordinates, incrementing either the x-coordinate, y-coordinate, or both, depending on the slope of the line. This algorithm is based on the idea of incremental calculations to approximate the continuous line. Steps in the DDA Algorithm: Let’s assume we want to draw a line between two given points, (x1,y1)) and (x2,y2). The DDA algorithm proceeds as follows: Calculate dx and dy: dx=x2−x1 dy=y2−y1 These values represent the change in the x and y coordinates from the starting point to the endpoint. Determine the number of steps required: The number of steps is based on the larger of the absolute values of dx and dy: steps=max⁡( ∣ dx ∣ , ∣ dy ∣ ) This ensu...
Read more

Perform the Line Clipping Algorithm in C Language.

Image
Cohen-Sutherland Line Clipping Algorithm (Detailed Explanation) The Cohen-Sutherland Line Clipping Algorithm is used to clip lines against a rectangular clipping window. It determines which portion of a line is inside the window and discards the rest. 1. Key Concepts Clipping Window: A rectangular area defined by four boundaries: Left: x m i n x_{min} ​ Right: x m a x x_{max} ​ Bottom: y m i n y_{min} ​ Top: y m a x y_{max} ​ Line Segment: Defined by two endpoints ( x 1 , y 1 ) (x_1, y_1)  and ( x 2 , y 2 ) (x_2, y_2) . Region Codes: Each point is assigned a 4-bit region code based on its position relative to the window. 2. Region Code Calculation Each point is classified into one of nine regions based on its position relative to the clipping window. The region code is a 4-bit binary value where: Bit 1 : 1 if the point is above ( TOP ), else 0 Bit 2 : 1 if the point is below ( BOTTOM ), else 0 Bit 3 : 1 if the point is right ( RIGHT )...
Read more

Implement the Bresenham’s algorithm to draw the line. Generalize it for co-ordinates in C language

  Bresenham’s Line Drawing Algorithm and Implementation in C Language The Bresenham’s Line Drawing Algorithm is an efficient method to draw a straight line between two given points on a pixel-based screen. Unlike the Digital Differential Analyzer (DDA) algorithm, which uses floating-point arithmetic, Bresenham’s algorithm uses only integer arithmetic , making it faster and more suitable for real-time applications. Concept Behind Bresenham's Algorithm Given two points ( x 1 , y 1 ) and ( x 2 , y 2 ) , the task is to draw a line between these points by determining which pixels on a screen should be illuminated. To achieve this, Bresenham’s algorithm uses a decision parameter that helps decide which pixel to plot at each step while incrementally traversing from the starting point to the endpoint. How Bresenham’s Algorithm Works Calculate dx and dy: d x = x 2 − x 1 d y = y 2 − y 1 These values represent the differences between the x and y coordinates. Set up the...
Read more