Page 70 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Lab on Computer Graphics

Notes We provide an algorithm that determines the overlap area between two general ellipses. We
first find the area of an ellipse segment, which is the area between a secant line and the ellipse
boundary. The segment algorithm then forms the basis of an application for calculating the
overlap area between two general ellipses, once the points of intersection between the two
ellipses have been found. The algorithm is implemented in c-code, and algebraic details are
provided in the text for all numerical operations in the code.
We present a general algorithm for finding the overlap area between two ellipses. The algorithm
is based on finding a segment area (the area between an ellipse and a secant line) given two points
on the ellipse. The Gauss-Green formula is used to determine the ellipse sector area between
the two points, and a triangular area is added or subtracted to give the segment area. For two
ellipses, overlap area is calculated by adding the areas of appropriate segments and polygons.
Intersection points for two general ellipses are found using Ferrari’s quadratic formula to solve
the polynomial that results from combining the two ellipse equations. All cases for the number
of intersection points (0, 1, 2, 3, 4) are handled. The algorithm is implemented in c-code, and has
been tested with a range of input ellipses. The code is efficient enough for use in simulations
that require many overlap area calculations.

5.1 Bresenham’s Ellipse Drawing Algorithm

There is a well-known algorithm for plotting straight lines on a display machine or a plotter
where the grid in excess of which the line is drawn consists of distinct points or pixels. In working
with a lattice of points it is useful to avoid floating point arithmetic. Integer arithmetic has the
advantages of speed and precision; working with floating point values requires more time and
memory and such values would need to be rounded to integers anyway.
#include “stdio.h”
#include “conio.h”
#include “math.h”
#include “graphics.h”
main()
{
int gd=DETECT,gm;
int xcenter,ycenter,rx,ry;
int p,x,y,px,py,rx 1 ,ry 1 ,rx 2 ,ry 2 ;
initgraph(&gd,&gm, “c:\\tc\\bgi”);
printf(“Enter The Radius Value:\n”);
scanf(“%d%d”,&rx,&ry);
printf(“Enter The xcenter and ycenter Values:\n”);
scanf(“%d%d”,&xcenter,&ycenter);
ry 1 =ry*ry;
rx 1 =rx*rx;
ry 2 =2*ry 1 ;
rx 2 =2*rx 1 ;
/* REGION 1 */
x=0;
y=ry;
plotpoints(xcenter, ycenter, x, y);

64 LOVELY PROFESSIONAL UNIVERSITY