Counting Number of Closed Spaces Formed in a Shape upon Cutting along Known Line

Question

Given a 2-D Shape and the positions of the vertices, or the nature, of this 2-D Shape, on which $n$ cuts are made, and given the equations for these $n$ lines, and the size of the 2-D shape,

How would you algorithmically find the number of closed spaces inside the 2-D Shape, or, in other words, the number of individual slices formed by the $n$ lines.

How would algorithmically you do this, starting from the simplest triangle to more complex shapes such as toruses?

Example of three lines forming 6 slices on a circle

Example of four lines forming 8 slices on a more complex shape

And if possible, what would the time complexity of this algorithm be?

Answer 1

By inspection, it looks like for a convex shape (like a circular boundary), the number of additional regions a line passing through creates is equal to the total number of intersection points it creates (including boundary and any lines already inside boundary) minus 1. If your collection of shapes has $n$ objects (lines and boundary), then if we add an additional line, a naive approach would be to solve $n+1$ 2x2 systems and check each one for an intersection. You also need to check if intersection point is inside the boundary (e.g. ray tracing). Count total valid intersections, and subtract 1. Each system solve is O(1). So, naive time complexity might be $$\sum_{n}^{N} n+1 \sim O(N^2).$$

For a non-convex shape like your second example .. I'm not sure. You might need to apply an approach like this multiple times on different parts of the shape.