<jupyter_start><jupyter_text>Polygon covering (sandbox code)This is a simple algorithm that illustrates some of the concepts that we've covered. You might also find some bits in here that aren't entirely clear. That's okay! Just get in here and play around. If you get confused, look up the various functions that are used online. Keep in mind that some functions can be used in multiple ways. Problem:Given the vertices of a convex polygon, a positive real number $r$, and a natural number $k$, find locations for $k$ balls of radius $r$ that cover as much as you can of the the polygon. In the code given, these values are hardcoded, but try to make your algorithm flexible enough that it can handle some variety of input parameters.<jupyter_code>"""Polygon covering problem exercise
Suppose we are given the vertices of a convex polygon (in order) and a radius r.
We want to find the locations of balls of radius r that cover the polygon."""

import matplotlib.pyplot as plt
from numpy import random


# Define the vertices counter-clockwise and the radius of the balls.
# Feel free to change these values and see what happens.
vertices = [[1,0], [0,1], [-1,0], [0,-1]]
ballRadius = .5
k = 4

# Populate x- and y- value arrays.
xValues = []
yValues = []
for v in vertices:
    plt.plot(v[0], v[1], 'o', color='black')
    xValues.append(v[0])
    yValues.append(v[1])

# Draw the shape.
plt.plot(xValues, yValues, color = 'black')
plt.plot([xValues[len(xValues)-1], xValues[0]],[yValues[len(yValues)-1], yValues[0]], color='black')

# Pick some random points within our shape
# Gives each vertex a weight of (random float between 0 and 1)/(number of vertices)
# Maybe some clever person can find a better way to pick the centers of our balls?
centers = []
circles = []
for i in range(k):
    centers.append([0,0])
    for v in vertices:
        rando = random.rand()/len(vertices)
        centers[i][0] = centers[i][0] + rando*v[0]
        centers[i][1] = centers[i][1] + rando*v[1]
    print(centers[i])
    tempCircle = plt.Circle((centers[i][0],centers[i][1]), radius = ballRadius, fill=False)
    circles.append(tempCircle)
    
# Draw the covering balls
fig = plt.gcf()
plt.axis('equal')
ax = fig.gca()
for c in circles:
    ax.add_artist(c)<jupyter_output>[0.12450225151738661, -0.015126366317805423]
[-0.01711908476219598, -0.1614267068864634]
[0.008363286902018069, -0.015237767054441465]
[0.11670543736817071, -0.10597388454445644]
{'fraction_non_alphanumeric': 0.11297584936553418, 'fraction_numerical': 0.07204257060990585, 'mean_word_length': 4.336244541484716, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '630710', 'license': 'MIT', 'n_tokens_mistral': 884, 'n_tokens_neox': 789, 'n_words': 308, 'path': '1. Monday (Python Crash Course)/polygonCovering.ipynb', 'repo_name': 'ArianNadjim/Tripods', 'size': '2443'}