I decided to share my implementations for the basic polygon algorithms. I see almost no problems on this topic and I hope this will change in the future.
First, let's remind the definitions we will use:
Polygon is a plane figure that is bounded by a finite chain of straight line segments closing in a loop to form a closed chain or circuit. These segments are called its edges or sides, and the points where two edges meet are the polygon's vertices or corners (wiki).
Polygon is convex if a line segment connecting any two points on its boundary lies inside the polygon. Equivalently, all its interior angles are less than or equal to 180 degrees.
Polygon is strictly convex if in addition no three vertices lie on the same line. Equivalently, all its interior angles are less than 180 degrees.
Polygon is simple if its boundary doesn't cross itself.
I will present two algorithms for each problem: one for arbitrary simple polygon, and one for strictly convex polygon, that has better complexity. The priorities in implementation design were as follows:
- handle all the corner cases, except for degenerate polygons with zero area;
- perform all computations in integers;
- optimize performance;
- write as concise and clear code as possible.
Please, let me know if you find a way to improve on any of these goals in any algorithm listed.