Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 24, 2018 20:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/cdaff949862911957461ec08ddaf4425 to your computer and use it in GitHub Desktop.
Save jianminchen/cdaff949862911957461ec08ddaf4425 to your computer and use it in GitHub Desktop.
Draw a circle - code review January 24 2018
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DrawACircle
{
class DrawACircle
{
static void Main(string[] args)
{
}
/*
problem statement:
You have one help function: Set(int x, int y) which turns on a pixel at (x,y).
The task at hand is to come up with an algorithm and code to draw a circle on screen.
You can use C/C++/C#/Java or similar languages.
*/
/// <summary>
/// code review on 1/24/2018 based on the code written in 2012.
/// https://github.com/jianminchen/AlgorithmsProblems/blob/master/DrawACircle.cs
/// Highlights of review:
/// 1. clean up the code, define extra explanation variables:
/// 2. remove a break statement on line 99.
///
///
/// updated on Dec 2012
/// since we only can show pixel on the integer, then, we do not have many options,
/// maximum number of points on the circle is 2 * radius,
/// Go through X anxis first, from -radius, -radius +1, …, 0, …, radius, see if
/// the y value is integer or not;
/// We can relax the algorithm, define a variable double errorRange, so we can make
/// it more points on circle, but less good shape; in the algorithm, set errorRange = 0,
/// but make the algorithm extendable
///
/// In terms of algorithm time complexity, it is O(2n);
/// But if we find too less points on the circle, then we have to design the algorithm
/// to find the best error range to simulate the circle.
///
/// In the last, I will start from small error range to increment the range to find best fit
/// </summary>
/// <param name="xCenter"></param>
/// <param name="yCenter"></param>
/// <param name="radius"></param>
public static void DrawCircle(int xCenter, int yCenter, int radius)
{
if (radius < 0)
{
return;
}
if (radius == 0)
{
Set(xCenter, yCenter);
}
// Double errorRange = 0;
// We may change it based on percentage, 0.1 * radius for example
Double errorRange = 0.1 * radius;
int n = 2;
int lookLikeCircle = 4 + 4 * n; // we may think about at 8 point will make it look like circle,
// we have at least 4 point on integer
int countPoint = 0;
int tryTimeMaximum = 1000;
int countTry = 0;
while(true)
{
for (int row = 0; row < radius; row++)
{
int x1 = xCenter - row;
int x2 = xCenter + row;
Double yValue = Math.Sqrt(radius * radius - row * row);
if (Math.Abs(yValue - Convert.ToInt16(yValue)) < errorRange)
{
countPoint = countPoint + 2;
}
}
if (countPoint < lookLikeCircle)
{
errorRange = errorRange * 2;
}
else
{
for (int row = 0; row < radius; row++)
{
int left_x = xCenter - row;
int right_x = xCenter + row;
Double yValue = Math.Sqrt(radius * radius - row * row);
var offset = Convert.ToInt16(yValue);
int top_y = yCenter + offset;
int bottom_y = yCenter - offset;
if (Math.Abs(yValue - offset) < errorRange)
{
Set(left_x, top_y);
Set(left_x, bottom_y);
Set(right_x, top_y);
Set(right_x, bottom_y);
}
}
countTry++;
if (countTry > tryTimeMaximum)
{
break;
}
}
}
}
public static int toInt(double x)
{
return Convert.ToInt16(x);
}
public static void Set(int x, int y)
{
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment