Page 69 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 5: Implementing Ellipse Algorithm
Kumar Vishal, Lovely Professional University

Unit 5: Implementing Ellipse Algorithm Notes

CONTENTS

Objectives
Introduction
5.1 Bresenham’s Ellipse Drawing Algorithm
5.2 Midpoint Ellipse Algorithm
5.3 Ellipse Area, Sector Area and Segment Area
5.3.1 Ellipse Area
5.3.2 Ellipse Sector Area
5.3.3 Ellipse Segment

5.4 Extending the Core Segment Algorithm to More General Cases
5.4.1 Segment Area for a (Directional) Line through a General Ellipse
5.4.2 Ellipse-ellipse Overlap Area
5.5 Summary
5.6 Keywords
5.7 Review Questions
5.8 Further Readings

Objectives

After studying this unit, you will be able to:

• Define Bresenham’s ellipse drawing algorithm
• Explain midpoint ellipse algorithm
• Define ellipse area, sector area and segment area

• Extending the core segment algorithm

Introduction

Ellipses are helpful in many applied circumstances, and in widely unlike fields. In our research,
we have encountered a common need for proficiently calculating the overlap area between two
ellipses. In one case, the design for a solar calibrator onboard an orbiting satellite required an
efficient algorithm for finding ellipse overlap areas. In a more down-to-earth setting, calculating
ellipse overlap areas is useful for modeling pedestrian dynamics. The approach described in
surrounds each pedestrian by an elliptical footprint area that the model uses to anticipate
obstacles and other pedestrians in or near the intended path. A force-based model produces a
repulsive force between overlapping exclusion areas, causing the pedestrians to slow down or
change course when the exclusion force becomes large. Implementing the force-based model
with elliptical exclusion areas in a simulation requires calculating the overlap area between many
different ellipses in the most general orientations. The ellipse area overlap algorithm must also
be efficient, so as not to bog down the simulation.

LOVELY PROFESSIONAL UNIVERSITY 63