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.

Solved

Posted on 2006-04-12

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

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

2 Comments

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

Jose

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

RTS server listeners separate Threads, or one Listener? | 20 | 145 | |

Unity game development advices! | 3 | 241 | |

GPU processing of c++ library | 7 | 91 | |

Will this chess board object .clone() call in Java make a perfect copy? | 3 | 67 |

This video discusses moving either the default database or any database to a new volume.

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

Connect with top rated Experts

**10** Experts available now in Live!