Created
January 24, 2018 20:44
-
-
Save jianminchen/cdaff949862911957461ec08ddaf4425 to your computer and use it in GitHub Desktop.
Draw a circle - code review January 24 2018
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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