The active list (also known as the active edge list) is a data structure used in scanline algorithms to keep track of the edges that intersect the current scanline. It dynamically maintains a list of edges that are currently intersecting or overlapping the scanline.
Now active list is nothing but a list of linked lists. Now, we have been given the following points in the question:
We start by constructing the Edge Table (ET) with each edge sorted by their minimum y-coordinate. For each edge, we store:
y_min: the minimum y-coordinate of the edge
y_max: the maximum y-coordinate of the edge
x: the x-coordinate of the lower endpoint of the edge
1/m: the inverse of the slope of the edge (used to update the x-coordinate as the scan line moves)
Edges:
AB: From A(1,2) to B(6,6)
y_min = 2, y_max = 6, x = 1, 1/m = (6-2)/(6-1) = 4/5
BC: From B(6,6) to C(8,3)
y_min = 3, y_max = 6, x = 8, 1/m = (3-6)/(8-6) = -3/2
CD: From C(8,3) to D(5,10)
y_min = 3, y_max = 10, x = 8, 1/m = (10-3)/(5-8) = 7/-3 = -7/3
DA: From D(5,10) to A(1,2)
y_min = 2, y_max = 10, x = 1, 1/m = (10-2)/(5-1) = 8/4 = 2
This is the global edge table. Now we have to find the active edge table.
The AET starts empty and is updated as we move through each scan line from the minimum y-coordinate to the maximum y-coordinate in the ET.
Scan Line y=2
Initialize AET with edges starting at y = 2: (1, 4/5) and (1, 2)
Scan Line y=3
Update x-coordinates:
For (1, 4/5): new x = 1 + 4/5 = 1.8
For (1, 2): new x = 1 + 2 = 3
Scan Line y=4
Update x-coordinates:
For (1.8, 4/5): new x = 1.8 + 4/5 = 2.6
For (3, 2): new x = 3 + 2 = 5
For (8, -3/2): new x = 8 - 3/2 = 6.5
For (8, -7/3): new x = 8 - 7/3 ≈ 5.67
Scan Line y=5
Update x-coordinates:
For (2.6, 4/5): new x = 2.6 + 4/5 = 3.4
For (5, 2): new x = 5 + 2 = 7
For (6.5, -3/2): new x = 6.5 - 3/2 = 5
For (5.67, -7/3): new x = 5.67 - 7/3 ≈ 3.33
The AET at each scan line is updated according to the intersection of the polygon edges with the scan line. The process above describes the update and maintenance of the AET at each scan line, showing how the x-coordinates are adjusted based on the edge slopes. The final polygon fill will be based on the intervals defined by the x-coordinates in the AET for each scan line.