circle iterate algorithm.txt

Journeyman's circle iteration algorithm - Public Domain
Does not use division or square roots!

Given: 
	Circle struct:
	```c
	typedef struct Circle
	{
		/*!
		 * \brief The x position of the center of the circle.
		 */
		int center_x;
		/*!
		 * \brief The y position of the center of the circle.
		 */
		int center_y;
		/*!
		 * \brief The radius of the circle.
		 */
		float radius;
	} Circle;
	```
	Point struct:
	```c
	typedef struct Point
	{
		/*!
		 * \brief The x coordinate of the point.
		 */
		int x;
		/*!
		 * \brief The y coordinate of the point.
		 */
		int y;
	} Point;
	```
	Point in circle function:
	```c
	int circle_contains_point(const Circle circle, const Point point)
	{
		const float circle_border_squared_distance = (float)((point.x * point.x) + (point.y * point.y)) - (circle.radius * circle.radius);
		return circle_border_squared_distance <= 0.0f; // equal to 0 is on the border of the circle, greater is outside, less is inside.
	}
	```
	Topmost point of circle function:
	```c
	#include <math.h>
	
	Point circle_get_top_point(const Circle circle)
	{
		Point ret = { circle.center_x, (int)roundf((float)circle.center_y - circle.radius) };
		return ret;
	}
	```
	Function to iterate a point (this is just the prototype):
	void iterate_point(const Point point);

Task:
	In a roguelike tile grid, iterate over every tile within the circle.
	For a tile to be in the circle, the centerpoint of the tile must 
	be within the radius from the center of the center point.

Solution:
	Step 1:	
		Determine topmost point of the circle.		
		```c
		Point topmost_point = circle_get_top_point(circle);
		```
	Step 2:
		Find the first point of the topmost row and set as top_row_first_point.
		Decrement x coord of topmost point in loop. 
		Check if topmost point is contained by the circle.
		If it is not, add 1 back to the x coord.
		```c
		Point top_row_first_point = topmost_point;
		do top_row_first_point.x--; 
		while(circle_contains_point(circle, top_row_first_point));
		top_row_first_point.x++;
		```
	Step 3:
		Calculate the following:
		```c
		Point row_first_point = top_row_first_point;
		int int_radius = (circle.center_y - topmost_point.y);
		int first_point_perp_move = (circle.center_x - row_first_point.x) + int_radius;
		int first_point_par_move = int_radius - (topmost_point.x + (topmost_point.x - row_first_point.x));
		```
	Step 4:
		Set cur_point to be row_first_point.
		Iterate from cur_point, 
		incrementing x until it is equal to circle.center_x.
		```c
		Point cur_point = row_first_point;
		while(cur_point.x != circle.center_x)
		{
			iterate_point(cur_point);
			cur_point.x++;
		}
		```
	Step 5:
		Move row_first_point to the top point of the row on the rightmost side of the circle.
		```c
		row_first_point.x += first_point_perp_move;
		row_first_point.y += first_point_par_move;
		```
	Step 6:
		Set cur_point to be row_first_point.
		Iterate from cur_point, 
		incrementing y until it is equal to circle.center_y.
		```c
		cur_point = row_first_point;
		while(cur_point.y != circle.center_y)
		{
			iterate_point(cur_point);
			cur_point.y++;
		}
		```
	Step 7:
		Move row_first_point to the right point of the row on the bottomost side of the circle.
		```c
		row_first_point.x += first_point_par_move;
		row_first_point.y += first_point_perp_move;
		```
	Step 8:
		Set cur_point to be row_first_point.
		Iterate from cur_point, 
		decrementing x until it is equal to circle.center_x.
		```c
		cur_point = row_first_point;
		while(cur_point.x != circle.center_x)
		{
			iterate_point(cur_point);
			cur_point.x--;
		}
		```
	Step 9:
		Move row_first_point to the bottom point of the row on the leftmost side of the circle.
		```c
		row_first_point.x -= first_point_perp_move;
		row_first_point.y += first_point_par_move;
		```
	Step 10:
		Set cur_point to be row_first_point.
		Iterate from cur_point, 
		decrementing y until it is equal to circle.center_y.
		```c
		cur_point = row_first_point;
		while(cur_point.y != circle.center_y)
		{
			iterate_point(cur_point);
			cur_point.y--;
		}
		```
	Step 11:
		If top_row_first_point.x y is circle.center_y plus 1, go to Step 13.
		otherwise, go to Step 12.
	Step 12:
		Decrement top_row_first_point.y.
		Decrement top_row_first_point.x until top_row_first_point is not in the circle,
		then increment top_row_first_point.x.
		Go to Step 3.
		```c
		top_row_first_point.y--;
		do top_row_first_point.x--; 
		while(circle_contains_point(circle, top_row_first_point));
		top_row_first_point.x++;
		```
	Step 13:
		Done!