Title: Draw stars in Python

[A seven-pointed star drawn with Python]

The example Draw stars inside polygons with Python and tkinter shows how you can draw stars by connecting the vertices of polygons. Unfortunately the result is self-intersecting. I wanted to draw a star where the lines don't cross each other. This turned out to be a more interesting problem than I expected.

Star Background

There's only one way to connect 5 or 6 vertices to make a star, but for 7 or more vertices there are multiple ways to make a star. For example, the picture below shows two ways that you can make seven-pointed stars. [Two ways to make a seven-pointed star]

For a discussion of star polygons that includes an interesting chart showing the stars that are possible for different numbers of points, see the Wikipedia article Star polygon.

This example takes the number of points the star should have and the number of points the program should skip when drawing the star. In the left star in the second figure, the skip number is 2 so the line leaving point 0 goes towards point 2 as indicated by the dashed line. In the star on the right the skip number is 3 so the line leaving point 0 heads towards point 3.

Note that some skip values don't produce nice stars. For example, if the skip number is half of the number of points, then the "star" is basically an asterisk, as shown in the following picture.

[If the skip number is half of the number of points, the result is an asterisk]

Some skip values are redundant. For example, if you use seven vertices, then the skip values 2 and 5 (which is 7 - 2) produce the same star.

Similarly, if the skip value is large, you get the same star you get if you set skip = (skip mod num_points). With seven vertices, for example, skip = 9 gives you the same result as skip = 9 % 7 = 2.

You won't get real stars for very small numbers of vertices. You can't even define a polygon with 1 or 2 vertices so a star doesn't make much sense. For that reason, the program requires at least 3 vertices.

With 3 vertices, you get a triangle. The only skip value that makes sense is 1 and that produces the original triangle, which really isn't a star. Still, I won't prohibit that.

Similarly with 4 vertices you get a rectangle. With skip = 1 you get the original rectangle and with skip = 2 you get an asterisk.

To avoid the asterisk problem, the program checks the skip value. If skip equals num_points / 2, the program creates an artificial inner radius so you get something star-like, although the inner vertices don't lie along the intersections of the lines connecting the vertices. For example, the following picture on the left shows a "star" with 4 vertices and a skip value of 2. The picture on the right shows a "star" with 6 vertices and skip value 3.

[A star with 4 vertices and skip value 2]

[A star with 6 vertices and skip value 3]

get_star_points

With that lengthy preamble, let's get to some code. The following get_star_points method returns the points needed to draw a star.

def get_star_points(start_theta, num_points, skip, bbox): '''Generate the points for a star centered in the bounding box.''' # bbox = (xmin, ymin, xmax, ymax) wid = bbox[2] - bbox[0] hgt = bbox[3] - bbox[1] rx = wid / 2 ry = hgt / 2 cx = bbox[0] + rx cy = bbox[1] + ry points = [] # Make sure skip is between 1 and num_points - 1. skip = skip % num_points # Do not allow skip = 0. if skip == 0: raise ValueError('skip should not be 0 or a multiple of num_points') # Is skip > num_points / 2, use the smaller equivalent. if skip > num_points / 2: skip = num_points - skip # If this is a polygon, don't bother with concave points. if skip == 1: theta = start_theta dtheta = 2 * math.pi / num_points for i in range(num_points): point = (cx + rx * math.cos(theta), cy + ry * math.sin(theta)) points.append(point) theta += dtheta return points # Find the radius for the concave vertices. inner_fraction = calculate_inner_radius(num_points, skip) # Make the points. theta = start_theta dtheta = math.pi / num_points for i in range(num_points): points.append(( cx + rx * math.cos(theta), cy + ry * math.sin(theta))) theta += dtheta points.append(( cx + rx * math.cos(theta) * inner_fraction, cy + ry * math.sin(theta) * inner_fraction)) theta += dtheta return points

The code first gets the width and height of the target bounding box and uses them to find the center and X and Y radii of the star. If you want the star to be regular, make the bounding box square. If you use a non-square rectangle, the star will be stretched horizontally or vertically.

Next, the code sets skip equal to skip % num_points so we know its value is between 0 and num_points - 1. It then checks that the result isn't 0 and raises an error if it is because that value won't define a star.

If skip is larger than num_points / 2, the code then adjusts it to use the equivalent smaller value.

Now if skip is 1, the "star" is really just the original polygon. In that case, the code doesn't bother figuring out where the stars inner concave points are. Instead it just generates the polygon's points and returns them.

After all that, the code finally gets down to calculating the points for a real star. First, it calls the calculate_inner_radius function described shortly to find the distance from the center of the bounding box to the star's inner points.

It then sets theta equal to the desired starting value. Use that parameter to put the star's first point in a particular direction. For example, you can make a 5-pointed star with its "top" at the top of the bounding box or on the right.

The program sets dtheta equal to π / num_points. That gives the angle between the star's points and its inner concavities.

The code then enters a loop to generate the star's points. Inside the loop, it uses some simple math to find the star's next outer point. It then adds dtheta to the angle and uses similar math to calculate the location of the next inner point. This time it multiples the distance from the center of the bounding box to the point by inner_fraction. It finishes the loop by multiplying theta by dtheta again so it's ready to generate the next point.

After the loop ends, the method returns the star's points.

calculate_inner_radius

The calculate_inner_radius method finds the distance from the center of the bounding box to the star's inner concave points as shown in the following picture.

It doesn't really calculate the distance for the star. Instead it calculates the fraction of the distance from the center to the outer radius. To do that, it performs some calculations on a test star with outer radius 1.

The following code shows how the method works.

def calculate_inner_radius(num_points, skip): '''Calculate the inner star radius.''' # If skip = num_points / 2, make a fake star instead of an asterisk. if math.isclose(skip, num_points / 2): return 0.33 # Calculate angles to key points. dtheta = 2 * math.pi / num_points theta00 = -math.pi / 2 theta01 = theta00 + dtheta * skip theta10 = theta00 + dtheta theta11 = theta10 - dtheta * skip # Find the key points. pt00 = (math.cos(theta00), math.sin(theta00)) pt01 = (math.cos(theta01), math.sin(theta01)) pt10 = (math.cos(theta10), math.sin(theta10)) pt11 = (math.cos(theta11), math.sin(theta11)) # See where the segments connecting the points intersect. lines_intersect, segments_intersect, intersection, close_p1, close_p2 = \ find_line_intersection(pt00, pt01, pt10, pt11) # Calculate the distance between the point of intersection and the center. return math.sqrt( intersection[0] * intersection[0] + intersection[1] * intersection[1])

The method first checks whether skip equals num_points / 2. If so, it simply returns 0.33 so you can build something like a star for those weird asterisk cases.

Next, the code finds the angle between the star's (outer) vertices and uses it to calculate the angles for one vertex (at angle theta00), the vertex we skip to (at theta01), the vertex following the first (theta10), and the vertex following the skip vertex (theta11). It uses those angles to find the points p00, p01, p10, and p11 shown in the following picture. Next, the code uses the find_line_intersection method (described in the post Determine where two lines intersect in Python) to see where the p00 → p10 and p10 → p11 lines intersect, giving the point marked by the dot in the picture.

Finally, the code calculates the distance from the origin to the point to get the inner radius. This star has outer radius 1, so the inner radius is also the fraction of the radius for the original star.

Conclusion

The main example program finds a square bounding box inside its canvas widget, uses get_star_points to get the necessary points, and draws the star. You could modify the program to do other things to the resulting polygon like fill the star, draw it with dashed lines, or whatever.

The whole thing was a bit more involved than I thought it would be, but it gives a pretty good result.

Download the example to experiment with it and to see additional details.