Space filling between random 2D lines

Question

Consider a region (2D) filled with lines randomly (following Figure). We are interested in filling the empty spaces between lines including four boundary edges in a way:

0- maximizing the size of parcels;
1- shape of filling parcels is square aligned horizontally or vertically;
2- shape of filling parcels is square, i.e., relaxed alignment;
3- shape of filling parcels is any quadrangle. our original question

So for now there are three different scenarios.
Note that the lines are of the form [x1,y1,x2,y2] point set, real numbers.

[* * *] Ideas of possible solutions/algorithms/code snippets/etc are more than welcome.

---

Update 1: We could manage a solution for the first case:

Steps are:
1- lines
2- rasterizing lines into a bitmap
3- searching nearby cells for each cell of desired color (i.e., the same color) with an objective function to maximize the area i.e., the number of cells.

It works well however it covers only the first scenario and it is also slow.

---

Update 2:
We assumed that the reader is familiar with the concept of space-filling-tiling. You may follow the link for inspiration. However note that our problem is different. As we do not fill the empty space randomly and we do not chose the size randomly. The solution should be iterative. For all the cases, there is no limit on the number of parcel being fitted. Indeed, it is up to user to limit the iteration number, by choosing a minimum area for parcels, for example. This is obvious in the example given above in which we discretized lines into pixels with specified size. That is, the procedure should run until entire empty area is filled respecting the criterion e.g., the maximum area of parcels.

---

Update 3:
summary:
One application is to find out the distribution of extractable intact 'rock' blocks in a heavily fractured 'mine'. This could be very helpful for many aspects including drilling design, financial evaluation etc.
description:
For a mine of decorative rock (stone) the products which are the blocks of intact rocks cut as rectangular cubes the price is closely dependent to the size of the block. Extraction of a block from a suitable area i.e., with no major fracture will be desired if the amount of remaining parts is small as possible. Usually, the small pieces of rocks have no economic value relatively and are considered so as waste.
The question in this post investigates solutions for this kind of problem.

A mathematical view for the problem can be stated as follows:
2D: Find all rectangles that could be extracted from a given 2D region with some lines optimized for larger rectangle size as possible.
3D: Find all rectangular cubes that could be extracted from a given 3D region with some sub-planes (better: polygons) optimized for larger block size as possible.

---

Since this is part of an on-going research, some of the questions asked in the comments below do not have certain answers that we can provide. We believe that the provided information here so far is indeed enough to get the overall picture of the problem. Nevertheless, we provide some details as we can for community benefits.
You may put some restrictions on the solution for the ultimate question, although, we believe it is always possible to add more later. For example, follow these: {2D case}
The best size of a block (economically optimum rectangle) to be extracted under the conditions mentioned above, is 1x1 m given 10x10 m for the region in the example. This is one constraint defined based on economical value. The minimum workable size for cutting etc, let be 0.15x0.15 m; so this the second size limit.

The figure above shows the economic value function depending to the block size. So for this particular case every rock piece smaller than 0.15x0.15 m is just waste. There will be no block size larger than 1.7x1.7 m due to operation limits.

Answer 1

I have an idea how you you iteratively work from large blocks down to smaller blocks using FME (by Safe Software.) For the record I don't work for them but seem to praise their tool enough...

1. Use "BoundingBoxReplacer" on the area of interest.
2. Reproject it to a local coordinate system (for later when you need to "tile" in feet/meters.)
3. Buffer the lines with "Bufferer" transformer. You only need an arbitrary size, say .01 ft/meters. What we are looking for here is a polygon of the line for the next step.
4. Add a "Tiler" Transformer. Specify a large (estimated or otherwise) Tile Size in Feet or Meters. What we are doing here is tiling the area of interest into square blocks. Depending on the dataset start large to really get the large outliers.
5. Add a "Clipper" transformer. What we are doing here is essentially slicing up the dataset to see which tiles are good/bad. On the output, tiles that are "Inside" are too big. However, tiles that are "Outside" are large enough and ready for cutting...
6. Here's where it get's complex, but not hard... We're going to loop the transformer so that we re-use the original BoundingBox, but clip out areas that are already ready for cutting. So, add a clipper and route the Clipper as the "Output" tiles on the earlier clipper output. Now we have a single polygon that is ready to work again.
7. Use the tiler again, this time specifying a smaller tile. For example if you used 100 meter tiles earlier, try 90 meters.
8. Add another clipper, with the input clipper being the buffered lines, and the input clippee being the smaller tiles as input.

Rinse and repeat as many times as necessary using smaller tiles each time. I've attached the start of a workbench I would use as one approach.

Based on your (nicely detailed) description, it will only work with your option 1 for now. Without devoting too much time just yet.

Anyways, this is just one approach I would start with to at least filter the wheat from the chaff.