{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Introduction\n\nVoronoi diagram is a special way to partition a plane that has applications in many fields. In the competition NFL Big Data Bowl of 2018, some users used this diagram to understand how each player in a american football influences the game by the amount of space that it potentially controls.\n\n<center><img src=\"https://upload.wikimedia.org/wikipedia/commons/5/54/Euclidean_Voronoi_diagram.svg\" alt=\"drawing\" width=\"300\"/></center>\n\nAs we can see above, the Voronoi diagram is made of points (aka seeds) and regions (aka cells). Each region has only one point, which is called the generator point of the region. To determine the size of the regions, we have to follow a simple property. All points in a Voronoi region are closer to their generator point than to any other generator point in the Voronoi diagram.\n\nBut what that actually means? Let's make an example. Suppose the seeds are Rocket League players with the same speed and no acceleration. The Voronoi region of a player is the area in which it can reach faster than any other player.\n\nOf course, in real life the players would have different speeds, accelerations and diretions, so that their actual space influece could be very different from the one calculated in the Voronoi diagram. But, this diagram is a great simplification and it proved to be useful in 2018. \n\nNow, let's use the data from out competition to visualize some examples. I will be using a lib called shapely to make the diagrams.\n\n# Examples from the competition","metadata":{}},{"cell_type":"code","source":"from itertools import chain\n\nimport pandas as pd\nimport numpy as np\nimport matplotlib.pyplot as plt\n\nfrom shapely.geometry import Point, Polygon, MultiPoint, box, GeometryCollection\nfrom shapely.ops import voronoi_diagram\nfrom shapely.strtree import STRtree","metadata":{"execution":{"iopub.status.busy":"2022-10-23T20:17:17.081181Z","iopub.execute_input":"2022-10-23T20:17:17.081628Z","iopub.status.idle":"2022-10-23T20:17:17.088808Z","shell.execute_reply.started":"2022-10-23T20:17:17.081594Z","shell.execute_reply":"2022-10-23T20:17:17.087234Z"},"_kg_hide-input":false,"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"players_pos_cols = [\n    ['p0_pos_x', 'p0_pos_y'],\n    ['p1_pos_x', 'p1_pos_y'],\n    ['p2_pos_x', 'p2_pos_y'],\n    ['p3_pos_x', 'p3_pos_y'],\n    ['p4_pos_x', 'p4_pos_y'],\n    ['p5_pos_x', 'p5_pos_y']\n]\n\nball_pos_cols = ['ball_pos_x', 'ball_pos_y']","metadata":{"execution":{"iopub.status.busy":"2022-10-23T19:27:17.816009Z","iopub.execute_input":"2022-10-23T19:27:17.816437Z","iopub.status.idle":"2022-10-23T19:27:17.822643Z","shell.execute_reply.started":"2022-10-23T19:27:17.816401Z","shell.execute_reply":"2022-10-23T19:27:17.821355Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"df = pd.read_csv(\n    '../input/tabular-playground-series-oct-2022/train_0.csv',\n    usecols = ball_pos_cols + list(chain.from_iterable(players_pos_cols)), nrows = 40000\n)","metadata":{"execution":{"iopub.status.busy":"2022-10-23T19:31:55.214766Z","iopub.execute_input":"2022-10-23T19:31:55.215187Z","iopub.status.idle":"2022-10-23T19:31:55.487309Z","shell.execute_reply.started":"2022-10-23T19:31:55.215141Z","shell.execute_reply":"2022-10-23T19:31:55.485853Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"df.head()","metadata":{"execution":{"iopub.status.busy":"2022-10-23T19:31:58.379547Z","iopub.execute_input":"2022-10-23T19:31:58.379950Z","iopub.status.idle":"2022-10-23T19:31:58.402438Z","shell.execute_reply.started":"2022-10-23T19:31:58.379900Z","shell.execute_reply":"2022-10-23T19:31:58.401440Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"def make_voronoi_plot(sample_row):\n    voronoi_seeds = []\n    for cols in players_pos_cols:\n        voronoi_seeds.append(sample_row[cols].tolist())\n    ball_pos = tuple(sample_row[ball_pos_cols].tolist())\n\n    points = MultiPoint(voronoi_seeds)\n    regions = voronoi_diagram(points)\n    tree_map = STRtree(regions.geoms)\n    ordered_diagram = GeometryCollection([tree_map.nearest(point) for point in points.geoms])\n    \n    fig, ax = plt.subplots(1)\n    for idx, region in enumerate(ordered_diagram.geoms):\n        x, y = region.exterior.xy\n        ax.plot(x,y, color='black') # plot lines\n        if(idx < 3):\n            ax.fill(x, y, color=\"cornflowerblue\") # fill region A\n        else:\n            ax.fill(x, y, color=\"lightcoral\") # fill region B\n\n    ax.scatter(*ball_pos, marker='.', c='green', s=500, label='Ball') # plot the ball\n\n    ax.scatter( # plot players A\n        [p.x for p in list(points.geoms)[:3]], \n        [p.y for p in list(points.geoms)[:3]], \n        marker = '.',\n        s=500,\n        label='Team A',\n        c='royalblue'\n    )\n\n    ax.scatter( # plot players B\n        [p.x for p in list(points.geoms)[3:]], \n        [p.y for p in list(points.geoms)[3:]], \n        marker = '.', \n        s=500,\n        c='maroon',\n        label='Team B'\n    )\n\n    # adjust limits\n    minx, miny, maxx, maxy = points.envelope.buffer(15).bounds\n    ax.set_xlim(minx, maxx)\n    ax.set_ylim(miny, maxy)\n\n    plt.legend(loc='best')\n    plt.show()","metadata":{"execution":{"iopub.status.busy":"2022-10-23T20:43:36.089092Z","iopub.execute_input":"2022-10-23T20:43:36.089542Z","iopub.status.idle":"2022-10-23T20:43:36.104538Z","shell.execute_reply.started":"2022-10-23T20:43:36.089498Z","shell.execute_reply":"2022-10-23T20:43:36.103348Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"make_voronoi_plot(df.sample(1, random_state = 42).iloc[0])","metadata":{"execution":{"iopub.status.busy":"2022-10-23T20:44:21.293749Z","iopub.execute_input":"2022-10-23T20:44:21.294614Z","iopub.status.idle":"2022-10-23T20:44:21.592826Z","shell.execute_reply.started":"2022-10-23T20:44:21.294517Z","shell.execute_reply":"2022-10-23T20:44:21.591488Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"In the situation above we can see that the ball is very close to 4 players, 2 for each team. By the coordenates we can understand that this play is happening in the middle of the field (remember that the goals are in y = 103 and y = -103). Despite having the control of the ball, team A is weaker because they control less area than team B.","metadata":{}},{"cell_type":"code","source":"make_voronoi_plot(df.sample(1, random_state = 38).iloc[0])","metadata":{"execution":{"iopub.status.busy":"2022-10-23T20:44:45.659788Z","iopub.execute_input":"2022-10-23T20:44:45.660212Z","iopub.status.idle":"2022-10-23T20:44:45.941134Z","shell.execute_reply.started":"2022-10-23T20:44:45.660177Z","shell.execute_reply":"2022-10-23T20:44:45.939815Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"make_voronoi_plot(df.sample(1, random_state = 4782).iloc[0])","metadata":{"execution":{"iopub.status.busy":"2022-10-23T20:44:58.860958Z","iopub.execute_input":"2022-10-23T20:44:58.861522Z","iopub.status.idle":"2022-10-23T20:44:59.120266Z","shell.execute_reply.started":"2022-10-23T20:44:58.861474Z","shell.execute_reply":"2022-10-23T20:44:59.118958Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Features\n\nThese examples help us to understand the game dynamics. It would be great we could somehow consider in the analysis the speeds and directions of each play. But, after all, what can we do with these diagrams? [This thread](https://www.kaggle.com/c/nfl-big-data-bowl-2020/discussion/119361) and I gives us some ideas of features that we can extract:\n\n- In which region (A or B) is the ball located.\n- Percentage of the area near the ball controled by each team.\n- Perimeter of the region that contains the ball\n- Proportion of the perimeter of the region containing the ball that touches regions of the opposite team.\n\nAlso, if we use the ball as a seed we could have more ideas of features.\n\n# Conclusion\n\nUsing the package shapely to make diagrams was good, but I'm not sure if it is the faster lib to make the calculations and the features. Probably not, so if became interested in this you should check out these packs: scipy or freud.","metadata":{}},{"cell_type":"code","source":"","metadata":{},"execution_count":null,"outputs":[]}]}