O'Reilly logo
live online training icon Live Online training

Exploring Algorithms in Python: Working with Polygons

Computing the Intersection of Two Polygons

George Heineman

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 two-hour course uses a mix of lectures, exercises, and Q&A sessions.

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

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 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