Drawing semi circles using Bresenham's Algorithm

Posted on 2006-04-12
Last Modified: 2013-12-26
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?

Question by:andrewstobirski
    LVL 84

    Accepted Solution

    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.
    LVL 18

    Assisted Solution


    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...


    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    IT, Stop Being Called Into Every Meeting

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  I’ll start with the algor…
    Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
    Sending a Secure fax is easy with eFax Corporate ( First, Just open a new email message.  In the To field, type your recipient's fax number You can even send a secure international fax — just include t…
    This video discusses moving either the default database or any database to a new volume.

    759 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    10 Experts available now in Live!

    Get 1:1 Help Now