Is there a way to generate the corners of a regular N-gon without division and without trig, given N as input

Question

Edit: So I found a page related to rasterizing a trapezoid https://cse.taylor.edu/~btoll/s99/424/res/ucdavis/GraphicsNotes/Rasterizing-Polygons/Rasterizing-Polygons.html but am still trying to figure out if I can just do the edges

I am trying to generate points for the corners of an arbitrary N-gon. Where N is a non-zero positive integer. But I am trying to do so efficiently without the need of division and trig. I am thinking that there is probably some of sort of Bresenham's type algorithm for this but I cannot seem to find anything.

The only thing I can find on stackoverflow is this but the internal angle increments are found by using 2*π/N: How to draw a n sided regular polygon in cartesian coordinates?

Here was the algorithm from that page in C

float angle_increment = 2*PI / n_sides;
for(int i = 0; i < n_sides; ++i)
{
    float x = x_centre + radius * cos(i*angle_increment +start_angle);
    float y = y_centre + radius * sin(i*angle_increment +start_angle);
}

So is it possible to do so without any division?

Answer 1

There's no solution which avoids calling sin and cos, aside from precomputing them for all useful values of N. However, you only need to do the computation once, regardless of N. (Provided you know where the centre of the polygon is. You might need a second computation to figure out the coordinates of the centre.) Every vertex can be computed from the previous vertex using the same rotation matrix.

The lookup table of precomputed values is not an unreasonable solution, since at some sufficiently large value of N the polygon becomes indistinguishable from a circle. So you probably only need a lookup table of a few hundred values.