Monday, December 8, 2014

Fast parallelizable way to generate approximate points for a circle without using trig functions

This method starts with the four points of the bounding square...
Then replaces each point with two points (1- root 2/2) away from the sides... This is basically like truncating every corner to the right proportion...
Then iterates this process but using .25 instead of (1-root 2/2) that I found by experiment works very well. I suppose for perfect accuracy there is a recursive series involving root 2 but it approaches .25 so quickly that I didn't bother with it.

I found 4 iterations is enough for fairly large circles...
And in the end you have an list with all the points in counter clockwise order around the circle. 
Python source code (Using PIL for drawing)
import Image, ImageDraw
def plot(points, draw):
    for i in range(0, len(points)-1):
        draw.line([points[i], points[i+1]])
    draw.line([points[len(points)-1], points[0]])
def truncate(points):
    newpoints = []
    param = .29
    if len(points)>4:
        param = .25
    for i in range(0, len(points)-1):
        x1 = points[i+1][0]*(param)+points[i][0]*(1.0-param)
        y1 = points[i+1][1]*(param)+points[i][1]*(1.0-param)
        x2 = points[i+1][0]*(1.0-param)+points[i][0]*(param)
        y2 = points[i+1][1]*(1.0-param)+points[i][1]*(param)
        newpoints.append((x1, y1))
        newpoints.append((x2, y2))
    x1 = points[0][0]*(param)+points[len(points)-1][0]*(1.0-param)
    y1 = points[0][1]*(param)+points[len(points)-1][1]*(1.0-param)
    x2 = points[0][0]*(1.0-param)+points[len(points)-1][0]*(param)
    y2 = points[0][1]*(1.0-param)+points[len(points)-1][1]*(param)
    newpoints.append((x1, y1))
    newpoints.append((x2, y2))
    return newpoints
def main():

    points = [(100,100),(100,700),(700,700),(700,100)]
    for i in range(1, 5):
        p ="RGB", [800,800])
        draw = ImageDraw.Draw(p)
        points = truncate(points)  
        plot(points, draw)"plots"+str(i)+".png")

No comments:

Post a Comment