习题101

在计算机图形学中，填充算法是一种常见的技术，用于在屏幕上绘制多边形并填充内部颜色。其中，使用活跃边表（Active Edge Table, AET）的扫描转换算法是一种高效的方法，尤其适用于处理复杂的多边形。这个算法的核心思想是沿着水平方向从上到下扫描，同时管理一个包含当前扫描线与多边形边相交的边表。 在题目描述的场景中，我们需要填充一个五边形。五边形的顶点坐标已经给出，分别是（10.5，10.5）、（15，5）、（12，5）、（8，2.5）、（4，5.5）。为了简化计算，通常会将坐标四舍五入到整数，得到（11，11）、（15，5）、（12，5）、（8，3）、（4，6）。 我们需要构建边表（Edge Table, ET），它是一个二维数组，记录了每条边与扫描线的交点。对于每条边，我们找到它的起点和终点，并计算它们对应的y坐标，然后根据这些坐标确定边在哪几条扫描线上。例如，边（11，11）-（15，5）在y=5的扫描线上有交点，边（12，5）-（8，3）在y=3的扫描线上有交点，以此类推。 接下来，我们创建活跃边表，初始时为空。然后，从最上方的扫描线开始，逐步向下扫描。在每个扫描线y，我们做以下操作： 1. 将所有与该扫描线相交的边添加到AET。 2. 对于AET中的每条边，检查其是否到达终点，如果是，则从AET中移除。 3. 按照y坐标排序AET中的边，以便于后续处理。 在这个过程中，我们需要关注边的相对顺序，因为这将决定像素的填充规则。通常，如果两条边在同一扫描线上相遇，那么它们之间的区域应该被填充。在实际编程实现时，这通常通过比较边的x坐标来判断。 对于给出的五边形，我们需要手动计算每条边与各个扫描线的交点，并构建完整的ET。然后，模拟扫描过程，记录AET在每个扫描线上的变化情况。具体的过程包括计算边的斜率、截距，以及确定边与扫描线的交点坐标等。由于题目没有提供完整的ET表，这部分需要自行计算完成。 理解这个算法的关键在于掌握如何维护和更新AET，以及如何正确处理边的相遇和移除。这个过程涉及到了数据结构（如链表或队列）和排序算法，同时还需要对几何和坐标变换有一定的理解。 使用活跃边表的扫描算法填充五边形，需要通过构建和管理边表、处理边界条件以及维护活跃边表来实现。这是一个典型的计算机图形学问题，对于理解和实现2D图形渲染算法具有重要意义。