# Space filling between random 2D lines

Note that I had asked this question in GIS forum, although it has gotten many up-votes, still has not received any answer. Hope you can break the silence, some collaboration :)

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.

For the first case i.e., horizontally/vertically aligned squares, our proposal as a solution is:
1- rasterising input lines into bitmap (matrix) using e.g., Bresenham's algorithm
2- searching nearby cells for each cell of desired colour (i.e., the same colour) with an objective function to maximize the associated area i.e., the number of pixels.

We assumed that the reader is familiar with the concept of space-filling-tiling. You may follow this link for inspiration. However, note that our problem is different. As we do not fill the empty space randomly and we do not choose the size of filler shapes randomly. The solution should be iterative, starting from largest to smallest permitted. The size boundary can be defined, for example, according to our explanation below for a particular study (our interest). 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 discretised 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.

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.

- Application:
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 and so on.

-- Details:
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.

Size Constrains:
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.

• Please integrate your "updates" to form one cohesive post; that will make it more accessible and thus more likely to receive an answer. – Raphael Apr 14 '13 at 10:34
• @Raphael Updates were merged into the body. – Developer Apr 14 '13 at 22:08