Live Online training

# Exploring Algorithms in Python: Working with Polygons

## What you'll learn-and how you can apply it

### By the end of this live, online course, you’ll understand:

• The properties of polygons and their intersections
• How to determine polygon and convex polygon intersection
• How to find the actual polygon from the intersection of two polygons

### And you’ll be able to:

• Model polygons in Python and perform a range of fundamental operations necessary for detecting intersections.
• Use algorithms for computing the convex hull for a data set.
• Compute the intersection of two convex polygons without relying on complicated third-party Python libraries.

## This training course is for you because...

• You work with Python and are interested in modeling two-dimensional information
• You're a programmer with a keen interest in algorithms
• You are a data scientist looking for additional insights into two-dimensional data sets
• You want to design and implement dynamic graphical user interfaces

Prerequisites

• Knowledge of Python
• Rudimentary knowledge of polygons and geometrical shapes
• Install Python 3

The Python code is written for Python 3, and you should be sure to use this version to avoid any frustrations in using the code

Install Python 3

The Python code is written for Python 3, and you should be sure to use this version to avoid any frustrations in using the code.

Recommended Preparation:

Introduction to Python

Intermediate Python: Introduction

GitHub Repository

There are several algorithms to compute the convex hull for a two-dimensional data set. These algorithms will be included “as is” in the repository and will not be presented during this session. You are encouraged to run the sample applications for constructing convex hulls. Some sample small data sets will be included and used in the presentation. ----> GitHub Repo

• George T. Heineman is an Associate Professor of Computer Science at WPI. His research interests are in Software Engineering and modularity. He is co-author of Algorithms in a Nutshell, 2nd Edition and the video course Working with Algorithms in Python. Aside from his professional pursuits, George is an avid puzzler. He invented Sujiken®, a Sudoku variation played on a right-triangle arrangement of cells in which numbers cannot repeat in a horizontal row, vertical column or diagonal in any direction.

## Schedule

The timeframes are only estimates and may vary according to how the class is progressing

Activities:

• Choosing a representation for Polygons
• Exercise: GUI Application to construct polygons
• Computing convex hull for two-dimensional data set
• Exercise: Apply to arbitrary data, using Akl-Toussaint heuristic
• Brute-force algorithm for computing intersection of two polygons
• Exercise: Evaluate performance
• Algorithm for computing intersection of convex polygons
• Exercise: Evaluate performance