Drawing semi circles using Bresenham's Algorithm

Hi Guys

I'm reasonably familiar with using Bresenham's Algorithm to draw a circle, but I would like to be able draw half of a circle just  by specifying two points - each point , obviously, is a distance of R (radius) from the circle centre.

How would I go about doing that?

Cheers
Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
If the points are 2R apart, then the centre of the circle is at the midpoint betwen the two points, and you only need to know which half you want to draw, which you can specify by the order of the two points.

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Graphics ExpertCommented:
Hi,

Strictly speaking:
Two points don't define a circle. Except if the center is supposed to be between the points, exactly in the middle. In this case, we have three points, confirming the above afirmation.

Three points in line don't define a circle.
Let's suppose that the points are in the same vertical line. The semicircle can be at left or at right, thus requiring a fourth point or an indication on what side the semicircle is.

So, a interesting way to define the semicircle only with two points is to decide on the following assumptions:
- The arc is always constructed in clockwise direction (or anti, as you want)
- The first point is always the starting point.
- The second point is the end point
- The center and radius are calculated from 1st and 2nd points.
- The start angle is calculated from center and start point

So, the algorithm would be:
SEMICIRCLE(start, end)
{
center = (start + end) / 2
startAngle = (center.x - start.x) / (center.y - start.y)  // actualy the tangent
drawArc by invoking a modified Bresenham Algorithm
}

The Bresenham's algorithm will be modified to test if the point to be ploted is part or not of the semicircle.
If your implementation works with 4 quadrants, each pass in the loop will plot just 2 points, not 4.
The trick is to check one point. If the analysed point is in the arc, plot it its symetrical isn't. Also, determine which quadrant (regard to x and y) is to be tested.

Lets an exemple for drawArc.
center = (0,0);  radius = 14.14;  startAngle = 45º; start=(10,10);
First, plot start and end points.
Quadrants are: Q1=(x,y), Q2=(x,-y), Q3=(-x,-y) and Q4=(-x,y). Notation is:  -x  represents negative x's.
The arc is in Q1 (part, only if x > 10) , in Q2 (total), in Q3(part, only if x > -10), nothing in Q4.
So, in this case, the analysis is focused on:
Q1: if it is OK, that is, x>10, plot the point, and don't plot the symetrical one in Q3,
if otherwise, don't plot in Q1 and plot in Q3;
Q2: No need to analyse it: all points will be drawn;
Q3: Analysed at same time as Q1;
Q4: No need to analyse Q4: nothing to plot in.

Unfortunately, this algorithm will be slightly less efficient than the original Bresenham's, due the tests.
Interesting challenge...

Jose
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.