Get grids info (number and edges) given splitting line segments on a rectanglar page?

Question

I am facing a problem of finding the grids info (number and edges) given splitting line segments on a rectangle page. Given the following image as an example, all splitting line segments are shown with both end points as red circles, the number here will be 7 as annotated in the image.

Assumptions:

1. The line segments form a valid split of the rectangle page.
2. All final grids are quadrilaterals.
3. No crossing line segments (i.e. regard there is an extra end point right on the cross).
4. No line segment lies within another.

Current solution:

1. Random pick a point (not labelled before) within the page.

2. Traverse all points within current area until touching the borders or splitting lines and also label them. Current area is a valid grid.

3. Loop step 1-2 until all points are labelled.

Note: here I also assume that the whole page can be discrete to uniform points (just like pixels in an image).

Problem & question:

Problem of the above solution is that I have to traverse all points within the page in order to get all the grids. Is there any simpler solution to this?

Answer 1

I finally found a simple approach to do this by divide-and-conquer.

Theory based-on: Add a line segment will split current area into two grids.

Based on above, the number should be quite straight forward, i.e. number_line_segments+1.

---

To determine the edges of every grid, we further need to know which area is split when a new line segment is added.

Then, the problem is transformed to: how to determine a valid adding sequence (not unique) of all the line segments. Here, "valid" means when adding a new line segment, it will split current area into two grids.

To determine a valid adding sequence of all the line segments, all I need to do is to determine the order for any two, which can be determined as follows:

order_for_two_line_segments(LineSeg LineSeg_A, LineSeg LineSeg_B)
{
    if (one of LineSeg_A's end points is on LineSeg_B)
        LineSeg_B should come before LineSeg_A;
    else if (one of LineSeg_B's end points is on LineSeg_A)
        LineSeg_A should come before LineSeg_B;
    else // neither end points of them are on the other one
        they can be in any order;
}

For example, in the following image (all lines are labelled as L1-L6), L1 should come before L2 because one of L2's end point is on L1, without which L2 cannot form a valid split. And any order can be possible between L2 and L6 as neither end points of them are on the other one, which makes any one of them (without the other) can still form a valid split.

And a valid adding sequence can be L3 > L1 > L2 > L5 > L4 > L6.

---

Edit: The above approach should also work for general cases where the grids can be any shape.