• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 4761
  • Last Modified:

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?

2 Solutions
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.
Jose ParrotGraphics ExpertCommented:

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
   radius = dist(start, center)
   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...


Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Tackle projects and never again get stuck behind a technical roadblock.
Join Now