Computational geometry

Computational geometry is a branch of computer science that studies algorithms that can be stated in terms of geometry. It is particularly important in the fields of computer graphics and manufacturing where it focuses on solving computational complexity. Among others, it has a few practical applications in computer games, generative art and integrated circuit design.

Polygons #

A polygon that doesn't intersect itself and is hole-free is called a simple polygon.

A rectilinear polygon is a polygon with all of its sides meeting at the angles 90 and 270. Alternatively, it is defined as a polygon with all sides being parallel to the axes of Cartesian coordinates.

The problem of decomposing a rectilinear polygon into a union simpler shapes is called Polygon covering. Depending on the shape and whether the polygon is hole-free or not, it can be an NP-hard problem.