Exploring Algorithms in Python: Working with Polygons
Computing the Intersection of Two Polygons
Learn how to make your Python code more efficient by using specific algorithms to solve computational problems for data sets in two dimensions or geometric shapes in GUI applications. George Heineman will show you to how to determine whether two polygons intersect. He'll demonstrate examples in real time, narrating key concepts and steps along the way. By the end of this course, you'll know how to construct and use both simple and convex polygons efficiently.
This twohour course uses a mix of lectures, exercises, and Q&A sessions.
What you'll learnand 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 thirdparty Python libraries.
This training course is for you because...
 You work with Python and are interested in modeling twodimensional information
 You're a programmer with a keen interest in algorithms
 You are a data scientist looking for additional insights into twodimensional 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:
Intermediate Python: Introduction
GitHub Repository
There are several algorithms to compute the convex hull for a twodimensional 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
About your instructor

George T. Heineman is an Associate Professor of Computer Science at WPI. His research interests are in Software Engineering and modularity. He is coauthor 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 righttriangle 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 twodimensional data set
 Exercise: Apply to arbitrary data, using AklToussaint heuristic
 Bruteforce algorithm for computing intersection of two polygons
 Exercise: Evaluate performance
 Algorithm for computing intersection of convex polygons
 Exercise: Evaluate performance