[CP] Approaching Geometry Problems

This week, I will be hosting a session on Geometry at the IIIT-H programming club, where I plan to discuss a few techniques and problems.

At first sight, computational geometry might seem very hard and intimidating. But once you familiarize yourself with some basic tools and tricks, you’ll become a geometry expert! Let’s break the myth “geometry is hard” together!

§ Basics

Suggestions

It is very important to have a clean, well-tested geometry library/template. It is very easy to make minor errors when coding up geometry solutions - precision issues, edge cases, division by zero etc. So a easy-to-use, modular library helps a lot in writing quick and painless solutions.

You do not have to make your own library from scratch. You can just use an existing one (I just use KACTL, with few tweaks), or you can modify them to adapt to your style, add more primitives etc.

Also, using vector geometry makes life a lot simpler, compared to co-ordinate geometry. Dot and cross products etc. make your derivations super simple and clean.

Resources:

KACTL - easy to use, well documented, well tested geometry library.
CF Blog by Al.Cash - A very nice tutorial on getting started with geometry problems.

Ideas & Tips:

Consider transforming the input
- moving the origin
- rotating the axes (change of basis)
- scaling (be careful of changes to distances!)
- circles to points (and vice-versa)
Look for invariants and properties
- like the shoelace formula
Standard techniques
- sweep lines
- convex hull
- angle sweep
Utilize existing primitives in your library
- circle-circle intersection?
- line-circle intersection?
- polygon-line intersection?
Outline a slow/brute force solution, and look for optimizations.