Circle & Curve Generation: Algorithms, Symmetry & Parametric Methods

TAKEAWAYS:

• The Midpoint Circle Algorithm uses a decision parameter to minimize calculations by exploiting symmetry, reducing time complexity to O(n).
• Parametric curves (Bezier, B-spline) define shapes via control points and weights, enabling smooth animations in apps like Pathao’s ride trajectory visualization.
• Symmetry properties (4-way, 8-way) allow drawing a full circle from just 1/8th of its points, cutting computation by 75%.
• Bresenham’s Circle Algorithm avoids floating-point operations, making it ideal for low-end devices (e.g., NTC’s old ticketing kiosks).
• Bezier curves are used in Khalti’s transaction flow animations and Daraz’s product mockups for smooth transitions.
• B-splines enable 3D character rigging in Nepali animation studios (e.g., Kathmandu’s 3D models for tourism ads).

---

1. Drawing a Circle: Symmetry and Algorithms

A circle is defined as the set of all points at a fixed distance (radius, r) from its center (x₀, y₀). In computer graphics, we digitize (map to pixel coordinates) this continuous shape. The key challenge: minimize calculations while ensuring accuracy.

Symmetry Properties of a Circle

A circle has 8-fold symmetry about its center. This means:

• If you plot one point in the first octant (top-right quadrant), you can reflect it across the x-axis, y-axis, and both diagonals to get all 8 points.
• Example: For a circle centered at (10, 5) with radius 5, plotting (12, 7) implies you also plot (12, 3), (8, 7), (8, 3), etc.

Why this matters: Instead of calculating all 4r points, you only need ~r/2 points in the first octant, then mirror them.

---

2. Midpoint Circle Algorithm

The Midpoint Circle Algorithm uses a decision parameter (P) to determine the next pixel without floating-point operations. It works by:

1. Starting at (x₀ + r, y₀) (top-rightmost point).
2. Calculating P = F(x, y) = x² + y² – r².
   • If P < 0, the next pixel is inside the circle → move right (x++).
   • If P ≥ 0, the next pixel is outside → move diagonally (x++, y--).
3. Update P using the recurrence relation:

   If P < 0: P = P + 2x + 3
   Else:     P = P + 2(x - y) + 5
   

Worked Example: Circle with r=5, Center (10,5)

Step-by-Step Trace:

Visualization of Explored Path:

Real-World Tie-In:

• NTC’s old ticketing machines used Bresenham’s algorithm (a variant) to draw circles for route maps on low-power displays.
• Pathao’s ride trajectory in the app shows a smooth circle for estimated arrival time, generated using parametric methods.

---

3. Bresenham’s Circle Algorithm

Bresenham’s algorithm is an integer-only version of the midpoint method, avoiding floating-point errors. It uses:

• Initial point: (x₀ + r, y₀)
• Decision parameter: P₀ = 5/4 – r
• Recurrence:

  If P < 0: P = P + 2x + 1; x = x – 1; y = y + 1
  Else:     P = P + 2(x – y) + 1; x = x – 1; y = y – 1
  

Comparison Table:

---

4. Parametric Curve Generation

Beyond circles, curves (e.g., Bezier, B-spline) define smooth shapes used in animation, UI design, and 3D modeling.

A. Bezier Curves

A Bezier curve is defined by:

• Control points: P₀, P₁, ..., Pₙ (e.g., 4 points for a cubic Bezier).
• Parametric equation:

  B(t) = (1-t)³P₀ + 3(1-t)²tP₁ + 3(1-t)t²P₂ + t³P₃,  t ∈ [0,1]
  

• Properties:
  • Starts at P₀, ends at Pₙ.
  • Never crosses the convex hull of control points.

Example: Cubic Bezier Curve Control points: P₀(0,0), P₁(2,5), P₂(5,2), P₃(7,0)

Graph of B(t):

Real-World Use:

• Khalti’s transaction animation: The swipe-to-pay curve is a Bezier curve for smooth motion.
• Daraz’s product mockups: Bezier curves define rounded corners in UI elements.

---

B. B-Splines

B-splines are piecewise polynomial curves controlled by knots and weights. They are:

• Smooth: C¹ continuous (no sharp corners).
• Local control: Moving one control point affects only a subset of the curve.
• Used in: 3D modeling (e.g., Blender, used by Nepali animators for Kathmandu’s 3D tourism ads).

Example: Quadratic B-spline Control points: P₀(0,0), P₁(2,4), P₂(4,0), P₃(6,4)

Graph of B-spline:

---

5. Applications in Nepal’s Tech Scene

Example: Daraz Order Queue

• When you place an order, Daraz’s progress bar uses a Bezier curve to animate from "Processing" to "Shipped."
• The curve is defined by:
  • P₀: Start (0,0)
  • P₁: Control point (1,2)
  • P₂: Control point (3,1)
  • P₃: End (4,0)

---

6. Exam Tip: How to Score Full Marks

1. For Midpoint/Bresenham:

   • Always show the decision parameter table (like the r=5 example above).
   • Label symmetric points clearly (8-way or 4-way).
   • Mention time complexity: O(r) for midpoint, O(1) per pixel for Bresenham.

2. For Bezier/B-spline:

   • Draw the control polygon (connect P₀ to Pₙ).
   • Write the parametric equation (even if not asked, it shows depth).
   • Compare with Bezier: B-splines are "smoother" but harder to compute.

3. Real-world tie-ins:

   • Pathao/Khalti: Bezier curves for animations.
   • NTC: Bresenham’s algorithm for low-power displays.
   • Daraz: B-splines for UI design.

4. Common Pitfalls:

   • Forgetting to mirror points (lose marks for incomplete circle).
   • Using floating-point in Bresenham (it’s integer-only!).
   • Misplacing control points in Bezier curves (curve won’t match expected shape).

---