Chapter 6: Drawing Shapes and Polygons

Building upon basic line and circle drawing, we can now construct more complex geometric shapes.

Rectangles and Squares

Rectangles are the simplest polygons. A rectangle is defined by two points: the top-left corner $(x_1, y_1)$ and the bottom-right corner $(x_2, y_2)$.

• Outline: Draw four lines:
  1. $(x_1, y_1)$ to $(x_2, y_1)$
  2. $(x_2, y_1)$ to $(x_2, y_2)$
  3. $(x_2, y_2)$ to $(x_1, y_2)$
  4. $(x_1, y_2)$ to $(x_1, y_1)$
• Filled: Iterate through every $y$ from $y_1$ to $y_2$ and draw a horizontal line from $x_1$ to $x_2$.

Polygons

A polygon is a closed 2D shape with straight sides. It is defined by a list of vertices: $V = \{P_1, P_2, \dots, P_n\}$.

Convex vs. Concave Polygons

• Convex: Any line segment connecting two internal points stays entirely inside the polygon. All internal angles are less than 180°.
• Concave: At least one line segment between two internal points passes outside the polygon. At least one internal angle is greater than 180°.

Filling Shapes: The Scanline Approach

Filling a polygon is the process of identifying which pixels lie within its boundaries. The most common technique is the Scanline Fill Algorithm.

1. Find the minimum and maximum $y$ values of the polygon to define the range of scanlines.
2. For each scanline $y$:
   • Find the intersection points of the scanline with all edges of the polygon.
   • Sort the intersection points by their $x$ coordinates.
   • Fill the pixels between pairs of intersection points (e.g., between the 1st and 2nd, the 3rd and 4th, etc.).

Handling Special Cases

• Vertices: If a scanline passes through a vertex, it could count as one or two intersections. A common rule is to count it as one intersection if it's a local minimum or maximum, and two otherwise.
• Horizontal Edges: These can be ignored during the intersection calculation as the scanline will handle them.

Even-Odd Rule and Winding Number

To determine if a point is "inside" a complex, self-intersecting polygon, we use mathematical rules.

Even-Odd Rule

1. Draw a ray from the point to infinity in any direction.
2. Count the number of times the ray crosses an edge of the polygon.
3. If the number is odd, the point is inside. If even, it's outside.

Winding Number

1. Initialize a counter to zero.
2. Draw a ray from the point.
3. Every time an edge crosses the ray from left-to-right, add 1.
4. Every time an edge crosses from right-to-left, subtract 1.
5. If the final number is non-zero, the point is inside.

Summary

Moving from lines to shapes introduces the need for robust filling algorithms. The scanline approach is a powerful and general-purpose method for rasterizing any polygon, while the even-odd and winding number rules provide the logic necessary for handling complex, overlapping geometries.