Drawing a 1-pixel outline for an ellipse

Shared Code
#1

Well, not just pixels, it can also be applied to tile maps.

The math behind solving this problem is [icode](ex^2 / rx^2) + (ey^2 / ry^2) = 1[/icode]
Where rx is x-radius, ry is y-radius, ex is the distance from an x-coordinate to the centre, and ey is the distance from a y coordinate to the centre.

The extents (e[xy]) must be lower than their respective radii.

If the x and y extents are too small, the point is inside the circle and [icode](ex^2 / rx^2) + (ey^2 / ry^2) < 1[/icode].
If the x and y extents are too large, the point is outside the circle and [icode](ex^2 / rx^2) + (ey^2 / ry^2) > 1[/icode].

At first you’d think to just check every pixel/tile in range with that formula, but that doesn’t work, because you are taking integers into an equation that need floating-point precision. You would end up with a very irregular line, and the chances are lots of parts would be missing.

The proper way to solve this is to take floats into the equation and later floor/ceil them to integers. The way to do this is take the coordinate on one axis and use it to solve the other.

To solve this equation for a point on the x-axis, we need to find ey:


(ex^2 / rx^2) + (ey^2 / ry^2) = 1   // Starting equation
1 - ex^2 / rx^2 = ey^2 / ry^2       // Subtract (ex^2 / rx^2) from both sides
(1 - ex^2 / rx^2) * ry^2 = ey^2     // Multiply both sides by ry^2
sqrt((1 - ex^2 / rx^2) * ry^2) = ey // And get the square root

and then do the same but using a point on the y-axis to get ex.

Once you have those points, you add/subtract them from the centre and turn them into ints.
Make sure that you do opposite operations with floor/ceil to make sure the ellipse is symmetrical.

Code



// Get the y-coord for each x-coord
for(int i = (int) (cx - rx); i <= cx + rx; i++)
{
	float ex = (float) i - cx; // ex = extent from the centre to a coordinate 'i'
	
	float j = 1f - ((ex * ex) / (rx * rx));
	j = j * ry * ry;
	j = (float) Math.sqrt(j);
	
	// Then you can just add the y-extent to the centre and you get the coordinates!
	doSomething(i, MathUtils.floor(cy + j));
	doSomething(i, MathUtils.ceil(cy - j));
}

// Get the x-coord for each y-coord.
// This is the same as the first part, but in order yx instead of xy, to fill in the gaps.
for(int j = (int) (cy - ry); j <= cy + ry; j++)
{
	float ey = (float) j - cy;
	
	float i = 1f - ((ey * ey) / (ry * ry));
	i = i * rx * rx;
	i = (float) Math.sqrt(i);
	
	doSomething(MathUtils.floor(cx + i), j);
	doSomething(MathUtils.ceil(cx - i), j);
}

Hopefully someone finds this useful. If you find any bugs/typos, please report them so other people get working code.